数学的帰納法の原理と応用

数学的帰納法

次のような漸化式の一般項 $a_n$ を求めてみます。
\[\begin{cases}&a_1=1\\[6pt]&a_{n+1}=2\,a_n+1\quad(n=1,2,\:\cdots)\end{cases}\]
漸化式の解き方を知っている人にとっては簡単な問題ですが、今はそれを知らないとして、とりあえず $a_n$ をいくつか書き下してみることにします。
\[\begin{align*}a_1&=1\\[6pt]a_2&=2\,a_1+1=3\\[6pt]a_3&=2\,a_2+1=7\\[6pt]a_4&=2\,a_3+1=15\\[6pt]a_5&=2\,a_4+1=31\\[6pt]&\qquad\vdots\end{align*}\]
これをじっと眺めてみると、勘の良い人は
\[\begin{align*}a_1&=2^1-1\\[6pt]a_2&=2^2-1\\[6pt]a_3&=2^3-1\\[6pt]a_4&=2^4-1\\[6pt]a_5&=2^5-1\\[6pt]&\qquad\vdots\end{align*}\]
という形になっていることに気づくかもしれません。「もしかすると一般項は
\[a_n=2^n-1\]
のようになっているのではないかな？」と予測できます。しかし、これはあくまで予測に過ぎませんから、きちんとした形で証明しなくてはなりません。そこで、ある $k$ について
\[a_k=2^k-1\]
が成り立っていると仮定して、その次の $a_{k+1}$ はどうなるのだろうと考えてみます。漸化式にしたがって計算してみると
\[a_{k+1}=2\,a_k+1=2(2^k-1)-1=2^{k+1}-1\]
となって、$n=k+1$ でも成り立っていることがわかります。さて、つい先ほど $n=1$ について
\[a_1=2^1-1\]
が成り立っていることを確認したので、次の $n=2$ でも成り立つことになります。$n=2$ でも成り立てば、$n=3$ でも成り立ちます。さらにこれを繰り返して $n=4,\:5,\:6,\:\cdots$ というように無限の $n$ について成り立つことがわかります。したがって、任意の $n$ について
\[a_n=2^n-1\]
が成り立つことが証明されました。このような証明法を数学的帰納法（mathematical induction）とよびます。数学的帰納法は数列のみならず、数学の様々な定理の証明に用いられる、とても強力で使い勝手の良い証明法です。数学的帰納法の一般的な定義をまとめると

よく知られた自然数の和の公式
\[1+2+3+\:\cdots\:+n=\frac{n\,(n+1)}{2}\]
を数学的帰納法で証明してみましょう。

(1) $n=1$ のときは両辺ともに $1$ なので等式は成立しています。
(2) $n=k$ のときに
\[1+2+3+\:\cdots\:+k=\frac{k\,(k+1)}{2}\]
が成り立っていると仮定すると、$n=k+1$ のときの和は
\[\begin{align*}\frac{k\,(k+1)}{2}+k+1&=\frac{k\,(k+1)}{2}+\frac{1}{2}\,2\,(k+1)\\[6pt]&=\frac{1}{2}\,(k+1)(k+2)\end{align*}\]
となって、やはり等式は成立します。(1), (2) より、
\[1+2+3+\:\cdots\:+n=\frac{n\,(n+1)}{2}\]
は任意の自然数 $n$ で成立します。

最後に数学的帰納法の不等式への適用例をみてみましょう。命題
\[n\geq 4\quad\Longrightarrow\quad 2^n\lt n!\]
を証明してみます。$n\geq 4$ という条件ですから、まず最初に $n=4$ の場合をチェックします。
(1) $n=4$ のとき、$2^4=16,\:4!=24$ なので、命題は成立しています。
(2) $n=k\,(k\geq 4)$ のとき
\[2^k\lt k!\]
が成り立つと仮定すると、$n=k+1$ のとき
\[2^{k+1}=2\cdot\,2^k\lt 2\cdot\,k!\lt (k+1)k!=(k+1)!\]
となって、これも成立しています。(1), (2) より、の $n\geq 4$ の自然数について $2^n\lt n!$ が成立することが証明されました。