数学的帰納法の応用例

数学的帰納法のさまざまな応用例を見ていく。

例題1：不等式の証明

$n\ge 1$ のとき $2^n>n$ を証明せよ。

基底：$n=1$ のとき、$2^1=2>1$。成立。

帰納：$n=k$ で $2^k>k$ を仮定。

$$2^{k+1}=2\cdot 2^k>2k\ge k+1(\because k\ge 1)$$

よって $n=k+1$ でも成立。

例題2：整除性の証明

$n^3-n$ は6の倍数であることを証明せよ。

基底：$n=1$ のとき、$1-1=0$ は6の倍数。成立。

帰納：$n=k$ で $k^3-k$ が6の倍数と仮定。

$$(k+1{)}^3-(k+1)=k^3+3k^2+3k+1-k-1=(k^3-k)+3k^2+3k$$

$k^3-k$ は仮定より6の倍数。$3k^2+3k=3k(k+1)$ は連続2整数の積に3を掛けたもので6の倍数。よって和も6の倍数。

例題3：漸化式で定義された数列

$a_1=2$, $a_{n+1}=2a_n-1$ のとき、$a_n=2^{n-1}+1$ を証明せよ。

基底：$n=1$ のとき、$a_1=2^0+1=2$。成立。

帰納：$n=k$ で $a_k=2^{k-1}+1$ を仮定。

$$a_{k+1}=2a_k-1=2(2^{k-1}+1)-1=2^k+1$$

これは $n=k+1$ での式に一致。

強い帰納法

$P(1),P(2),\dots ,P(k)$ がすべて成り立つと仮定して $P(k+1)$ を示す方法。フィボナッチ数列の一般項の証明などで使う。