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

数学的帰納法

次のような漸化式の一般項 $a_n$ を求めてみます。
$$\{\begin{array}{ll}& a_1=1\\ & a_{n+1}=2a_n+1(n=1,2,\cdots )\end{array}$$
漸化式の解き方を知っている人にとっては簡単な問題ですが、今はそれを知らないとして、とりあえず $a_n$ をいくつか書き下してみることにします。
$$\begin{array}{rl}{a}_1& =1\\ a_2& =2a_1+1=3\\ a_3& =2a_2+1=7\\ a_4& =2a_3+1=15\\ a_5& =2a_4+1=31\\ & ⋮\end{array}$$
これをじっと眺めてみると、勘の良い人は
$$\begin{array}{rl}{a}_1& =2^1-1\\ a_2& =2^2-1\\ a_3& =2^3-1\\ a_4& =2^4-1\\ a_5& =2^5-1\\ & ⋮\end{array}$$
という形になっていることに気づくかもしれません。「もしかすると一般項は
$$a_n=2^n-1$$
のようになっているのではないかな？」と予測できます。しかし、これはあくまで予測に過ぎませんから、きちんとした形で証明しなくてはなりません。そこで、ある $k$ について
$$a_k=2^k-1$$
が成り立っていると仮定して、その次の $a_{k+1}$ はどうなるのだろうと考えてみます。漸化式にしたがって計算してみると
$$a_{k+1}=2a_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{array}{rl}\frac{k(k+1)}{2}+k+1& =\frac{k(k+1)}{2}+\frac{1}{2}2(k+1)\\ & =\frac{1}{2}(k+1)(k+2)\end{array}$$
となって、やはり等式は成立します。(1), (2) より、
$$1+2+3+\cdots +n=\frac{n(n+1)}{2}$$
は任意の自然数 $n$ で成立します。

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