【導入】数学的帰納法

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

数学的帰納法の考え方

【基本】漸化式などで、漸化式について見てきました。典型的な問題は、\[ 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$ のとき」を考えるというのは、冒頭で見た「初項」と「漸化式」の関係によく似ていますね。

数学的帰納法とドミノ倒し

数学的帰納法は、よく「ドミノ倒し」で例えられます。

ドミノはどうやって倒れていくかというと、まず最初に1枚目のドミノを倒すところから始まります。1枚目が倒れると、その影響で2枚目が倒れ、倒れた2枚目が3枚目を倒し、倒れた3枚目がさらに4枚目を倒し、…と続いていきます。こうして、すべてのドミノが倒れていきます。

これが、「 $n=1$ のとき」と「 $n=k$ のときと $n=k+1$ のとき」を証明することで、すべての自然数で成り立つことを証明する数学的帰納法に似ている、ということなんですね。

この2つのどちらが欠けていてもダメです。つまり、「 $n=1$ のとき」の証明が抜けていてもダメだし、「 $n=k$ のときと $n=k+1$ のとき」の証明がきちんとできていないのもダメです。特に、慣れてくると「 $n=1$ のとき」の証明がおろそかになってしまうので、注意が必要です。

おわりに

ここでは、数学的帰納法の考え方の紹介を行いました。具体的な使い方、証明の仕方は別のところで詳しく見ていくことにしましょう。