数学的帰納法
着眼点「n=1 で成立」「n=k で成立を仮定 → n=k+1 で成立」の2段。仮定の式をどこで使ったかが見える答案にする。
- [I] n=1（不等式などで n\ge2 なら n=2）のとき成り立つことを示す
- [II] n=k のとき成り立つと仮定し、それを使って n=k+1 のときを示す
- [I][II] より、すべての自然数 n で成り立つ
例題
1
すべての自然数 n について、n^3+2n は 3 の倍数であることを証明せよ。
解答
[I] n=1：1+2=3 で成立。
[II] n=k で k^3+2k=3m（m は整数）と仮定する。 (k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2=(k^3+2k)+3(k^2+k+1)=3(m+k^2+k+1) よって n=k+1 でも 3 の倍数。
[I][II] よりすべての自然数 n で成り立つ。（証明終）
[II] n=k で k^3+2k=3m（m は整数）と仮定する。 (k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2=(k^3+2k)+3(k^2+k+1)=3(m+k^2+k+1) よって n=k+1 でも 3 の倍数。
[I][II] よりすべての自然数 n で成り立つ。（証明終）
2
n\ge2 の自然数について、3^n>2n+1 を証明せよ。
解答
[I] n=2：9>5 で成立。
[II] k\ge2 で 3^k>2k+1 と仮定する。 3^{k+1}=3\cdot3^k>3(2k+1)=6k+3 (6k+3)-(2k+3)=4k>0 より 3^{k+1}>2(k+1)+1。
[I][II] より n\ge2 で成り立つ。（証明終）
[II] k\ge2 で 3^k>2k+1 と仮定する。 3^{k+1}=3\cdot3^k>3(2k+1)=6k+3 (6k+3)-(2k+3)=4k>0 より 3^{k+1}>2(k+1)+1。
[I][II] より n\ge2 で成り立つ。（証明終）
ポイント漸化式で a_1,a_2,a_3 を計算して一般項を推測 → 帰納法で証明、という流れでも使う。
注意[II] で、示したい n=k+1 の式を最初から正しいものとして変形しない。仮定の式から出発する。