数学的帰納法　基本と応用

上野竜生です。数学的帰納法はほぼワンパターンで解けます。ただし応用もあるのでここで紹介しようと思います。

基本パターン

n=1のときに成立することは1から言えます。
n=2のときは2)よりn=1で成立ならばn=2で成立が言え，n=1での成立はすでに示されているので成立です。
n=3のときは2)よりn=2で成立ならばn=3で成立が言え，n=2での成立はすでに示されているので成立です。

この感じですべての自然数で成立が言えます。

数学的帰納法を使う問題では，普通2)の部分がきちんといえるかが勝負になってきます。（ごくまれに１）のほうがしんどいときもありますが・・・）

ただし，1)も絶対必要な記述なので明らかな場合でも「n=1は明らか」ぐらいは書きましょう。

例題

数学的帰納法で示す。

n=1のとき4を3で割った余りが1であることは明らか

n=kで成立すると仮定する。つまり\( 4^k=3M+1 \)と書けるとする

n=k+1のとき

\( 4^{k+1}=4\cdot 4^k=4(3M+1)=12M+4=3(4M+1)+1\)

4M+1は整数だから\( 4^{k+1} \)は3で割ると1余るのでn=k+1のときも成立

よって数学的帰納法よりすべての自然数nに対し\( 4^n \)は3で割ると1余る

例題２

n=1のとき（左辺）＝2　（右辺）＝6なので成立

n=kで成立すると仮定する。つまり

\( \displaystyle \sum_{i=1}^{k} i(i+1) < (k+2)!\)とする。n=k+1のとき

（左辺）＝\( \displaystyle \sum_{i=1}^{k+1} i(i+1)
\\ = \left( \displaystyle \sum_{i=1}^{k} i(i+1) \right) + (k+1)(k+2)
\\ < (k+2)! + (k+1)(k+2)
\\ <(k+3)!=((k+1)+2)!\)
=(右辺)

（下から2行目は帰納法の仮定より成立。1番下の不等式は次を示せばよい）

\( (n+2)!+(n+1)(n+2)<(n+3)! \)

この式の右辺ー左辺を計算すると
\( (n+3)!-(n+2)!-(n+1)(n+2)
\\= (n+2)(n+2)!-(n+1)(n+2)
\\> (n+2)(n+1)-(n+1)(n+2)
\\=0\)
よりこの不等式は成立

よりn=k+1のときも成立

よって数学的帰納法よりすべての自然数nに対して題意は成立。

応用例１：n=kとn=k+1での成立を仮定してn=k+2で証明する

n=1のときa+b=6

n=2のとき\( a^2+b^2=17+12\sqrt{2} + 17-12\sqrt{2}=34\)

となりn=1,2のとき成立。

n=k,n=k+1での成立を仮定する。つまり，
\(a^k+b^k=N , a^{k+1}+b^{k+1}=M \)（N,Mは整数）とすると

\( a^{k+2}+b^{k+2}
\\=(a^{k+1}+b^{k+1})(a+b)-ab(a^k+b^k)
\\=6M-N　(∵ab=1)\)

となりn=k+2のときも成立。

よって数学的帰納法よりすべての自然数nに対して成立。

応用例２：k以下のすべての整数で仮定しn=k+1のときに示す

出題頻度は高くないです。主に漸化式の解き方のページに載っていない特殊な漸化式を解くときに使います。

n=1,2,3・・・を代入して一般項を予想し，帰納法で証明します。ただし，漸化式の中にa₁からa_nまで全部入っている場合は1つ手前に戻るだけでは不十分（通常の帰納法の仮定だけでは足りない）のでa₁からa_kまですべてを仮定する必要があります。