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

数学的帰納法

 次のような漸化式の一般項 $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) とよびます。数学的帰納法は数列のみならず、数学の様々な定理の証明に用いられる、とても強力で使い勝手の良い証明法です。数学的帰納法の一般的な定義をまとめると

 自然数 $n$ を含んだ命題 $P(n)$ について

 (1) $P(1)$ が正しい。
 (2) $P(k)$ が正しいと仮定すると $P(k+1)$ も正しい。

 という2つの事柄を満たせば、命題 $P(n)$ は成立しています。

 よく知られた自然数の和の公式
 
\[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!$ が成立することが証明されました。

エクセルや数学に関するコメントをお寄せください