数学的帰納法

カテゴリ：数列

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

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

　すべての自然数 $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$ の場合は示しているので

$n=1$ の場合に成り立つ
$n=1$ が成り立つので、 $n=1+1=2$ も成り立つ
$n=2$ が成り立つので、 $n=2+1=3$ も成り立つ
$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$ でも成り立つことを示しています。

まとめ

以上のことがら

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

と数学的帰納法により

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

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

著者：安井真人(やすい　まさと)
@yasui_masatoさんをフォロー

前の記事数列