数学的帰納法

数学的帰納法

 みなさんはドミノ倒しをやったことがあるでしょうか?わたしは子供の頃、将棋のコマを並べてドミノ倒しをしていました。将棋のコマを立てて並べて、一番はじめのコマを倒すと連動して次のコマが倒れていきます。数学にもこのドミノ倒しの原理により証明する手法があります。それが数学的帰納法です。ここでは、数学的帰納法による証明方法について解説します。

どのような場合に数学的帰納法を使えるか

 すべての自然数nに対して事柄P(n)が成り立つことを証明する際に、数学的帰納法を使います。例えば、

 \displaystyle 1+2+3+\cdots+n=\frac{1}{2}n(n+1)

であることの証明に使えます。この場合の事柄P

 \displaystyle 1+2+3+\cdots+n=\frac{1}{2}n(n+1)

であることです。

数学的帰納法による証明

実際に数学的帰納法を使って見たほうが理解が進みます。そこで、実際に数学的帰納法を用いて

 \displaystyle 1+2+3+\cdots+n=\frac{1}{2}n(n+1)

を証明していきます。

n=1の場合に成立することを示す

数学的帰納法では、まず、n=1のときを証明します。ドミノでいう最初のコマです。今回の証明では

(左辺)=1

(右辺)=\displaystyle\frac{1}{2}1(1+1)=1

となります。ゆえにn=1のときは成り立ちます。

n=kが成り立つならn=k+1が成り立つ

 次に、n=kが成り立つ場合にn=k+1が成り立つことを示します。これはk番目のドミノが倒れたら、k+1番目のドミノが倒れることを意味します。このことを示せば、n=1の場合は示しているので

  1. n=1の場合に成り立つ
  2. n=1が成り立つので、n=1+1=2も成り立つ
  3. n=2が成り立つので、n=2+1=3も成り立つ
  4. n=3が成り立つので、n=3+1=4も成り立つ

となります。これによりすべての自然数nで成り立つことになりますね。

 ではn=kが成り立つ場合にn=k+1が成り立つことを示します。n=kの場合が成り立つとすれば

 \displaystyle 1+2+\cdots+k=\frac{1}{2}k(k+1)

が使えるので

 \displaystyle 1+2+\cdots+k+(k+1)=\frac{1}{2}k(k+1)+(k+1)=\frac{1}{2}(k+1)(k+2)

が得られます。これはn=k+1でも成り立つことを示しています。

まとめ

以上のことがら

  1. n=1のときに成り立つ
  2. n=kのときに成り立つとすれば、n=k+1でも成り立つ

と数学的帰納法により

 \displaystyle 1+2+3+\cdots+n=\frac{1}{2}n(n+1)

が成り立つことが証明されました。

著者:安井 真人(やすい まさと)