【導入】数学的帰納法

🕒 2018/03/24 🔄 2023/05/01

ここでは、数学的帰納法の考え方の紹介をしていきます。

📘 目次

数学的帰納法の考え方

【基本】漸化式などで、漸化式について見てきました。典型的な問題は、\[ a_1=1,\ a_{n+1}=2a_n+1 \ (n=1,2,3,\cdots ) \]という式から、この数列の一般項を求める、というものでした。この2つ目の式のように、「それ以前の項を決めれば、次の項がただ1通りに決める規則を表した式」を漸化式というのでしたね。

上の例では、初項を決めているから、まず第1項が決まります。また、第1項と漸化式を使えば、第2項が決まります。第2項と漸化式から、第3項が決まります。こうして、次々と項が定まり、すべての自然数 $n$ に対して、第n項が決まる、という仕組みになっています。

これと似た考えを利用して、すべての自然数で成り立つ命題を証明する方法があります。それが、数学的帰納法(mathematical induction) と呼ばれるものです。

名前は重々しいですが、かなり便利な証明方法です。どういう使い方をするか、具体的な話は別のところで詳しく見ていきますが、ここでは、概要だけを書いていきます。

例えば、「すべての自然数 n について、○○が成り立つ」ことを証明したい、とします。こういう場合、今までは条件から言えることを考えたり、条件式を変形をして証明するしかありませんでした。

数学的帰納法では、次のようなアプローチで証明していきます。

$n=1$ のときに成り立つことを証明する
$n=k$ のときに成り立てば、 $n=k+1$ のときにも成り立つことを証明する

この2ステップです。これでおしまいです。

1つ目を証明することで、 $n=1$ のときが証明できます。これと2つ目の証明から、 $n=2$ のときにも成り立つことがわかります。また、 $n=2$ のときに成り立つことと2つ目の証明から、 $n=3$ のときにも成り立つことがわかります。こうして、次々といろんな自然数で成り立つことがわかるので、すべての自然数 $n$ に対して、○○が成り立つ、ということが証明できるわけなんですね。

「 $n=1$ のとき」と「 $n=k$ のときと $n=k+1$ のとき」を考えるというのは、冒頭で見た「初項」と「漸化式」の関係によく似ていますね。