(テンプレートあり)数学的帰納法の仕組みと使い方、押さえるべきポイント２つの解説

数学的帰納法について扱います。数学的帰納法はいくつかある証明方法の中でも最も重要な手法です。仕組みをよく理解して使いこなせるようになりましょう。

数学的帰納法の仕組み

数学的帰納法とは

大丈夫ですか？大丈夫じゃないですよね？
具体的なお話で，イメージを掴み，仕組みを理解しましょう。

数学的帰納法の仕組み

あなたは「もややの国」の国民です。この国には現在休日が存在しません。この国を治めるもややは国民全員がすべての日が休日となるように，１月１日に突然ある法律を作りました。

すごい法律です！この法律に従うのであれば，今日が休日だったら明日も休日です。そして，明日が休日ならあさっても休日です。さらに，あさってが休日なら…と，ずぅーっと休日が続きますね。もややは満足げに去って行きました。

翌日１月２日，もややは国を見学しに来ました。当然，国民全員が休んでると思っていましたが，なんと国民はこれまで通り働いています。そして，この翌日もさらに翌日も国民はこれまで通り働いており，もややは諦めて，さっきの法律を撤回しました。

翌年の１月１日，もややは国民全員がすべての日が休日となるように，法律を作りました。

国民「……。」
このままでは，１年前と同じ道を歩むことになりますね。ここで，あなたにお願いがあります。残念なもややに代わって，すべての日が休日となるように，もう１つ法律を追加してください。ただし「すべての日が休日である」はダメです(笑)
どんな法律を追加しますか？
はい，もう分かりますね。

この２つがそろえば，まず１月１日が休日です。そして，１月１日が休日なので次の日１月２日も休日になります。さらに，１月２日が休日なので次の日１月３日も休日，…，12月30日が休日なので次の日12月31日も休日，…。これで，すべての日が休日になりましたね。

これが数学的帰納法の仕組みです。
すべての日を休日とするためには，
まず１日目の１月１日を休日にする必要があります。これが，
(ア) $n=1$ のとき (☆) が成り立つ
の部分ですね。まず，最初の自然数で成り立つことを言うということですね。

そして，休日の次の日は休日という仕組みを用意します。これが，
(イ) $n=k$ のとき (☆) が成り立つと仮定すると，
　　$n=k+1$ のときも(☆) が成り立つ
の部分です。ある自然数で成り立てば，次の自然数でも成り立つという仕組みですね。

(ア) と (イ) が成り立つことが言えれば，
(ア) より $n=1$ のとき成り立つ
(イ) より 次の自然数 $n=2$ のとき成り立つ
(イ) より 次の自然数 $n=3$ のとき成り立つ
　　…
(イ) より 次の自然数 $n=100$ のとき成り立つ
(イ) より 次の自然数 $n=101$ のとき成り立つ
　　…
(イ) より 次の自然数 $n=10000$ のとき成り立つ
　　…
結局，すべての自然数 $n$ で成り立つことが言えたことになりますね。

数学的帰納法で難しいのは(イ)の部分です。
言っていることは「休日の次の日は休日」と同じで，
「ある自然数 $k$ で成り立てば次の自然数 $k+1$ でも成り立つ」という仕組みを表現しているだけです。しっかり意味を理解しておきましょう。

ちなみに，問題によってはすべての自然数ではなく「 $3$ 以上のすべての自然数で成り立つことを証明せよ」と言われる場合もありますが，どうすれば良いか分かりますか？
もし「１月３日以降すべての日が休日」としたかったら，法律をどのように変更しますか？
「１月１日は休日とする」を「１月３日は休日とする」と開始を変更すれば良いですね。
つまり，「 $3$ 以上のすべての自然数で成り立つ」であれば，(ア) の「$n=1$ のとき成り立つ」を「$n=3$ のとき成り立つ」に変更すれば良いだけです。仕組みを理解していれば，少し変わっても問題なく対応できますね。

数学的帰納法のテンプレート

数学的帰納法は，仕組みを理解した上で使うことが重要ですが，慣れるまで書き方が分からないと思います。そして，ただなんとなく書いていると数学的帰納法のメリットが生かせません。メリットとは何かというと「すべての証明問題が同じ流れで証明できる」ということです。同じ流れで証明できるということを意識できるように，慣れるまでは，以下のテンプレートに沿って証明してみてください。
テンプレートのダウンロードはこちら

（証明）緑の枠内以外は，基本的に変わらない

数学的帰納法による不等式の証明

問題

解説授業

すべての自然数についての証明は数学的帰納法を選択しましょう。証明したい不等式を確認します。$$n!≧2^{n-1} \enspace \cdots \text{(☆)}$$
このように，(☆)などとおいておくのも，細かい部分ですが大事ですよ。
それでは，テンプレートに沿って証明していきましょう。

(あとは，なんとかして②を証明できれば終わりですが，数学的帰納法はここが最も難しい部分です。②を示すとき，①を必ず使うことを意識しておくと，かなり証明しやすくなります。)

(ア)，(イ) より，すべての自然数 $n$ について (☆) が成り立つ。（証明終了）

いくつか，補足説明をしておきます。
(☆) に $n=k+1$ を代入して$$(k+1)!≧2^{(k+1)-1} \enspace$$という式を書きましたが，これが，本来示すべき式です。しかし，今回，これを整理して，$$(k+1)!≧2^{k} \enspace \cdots \text{②}$$として，②を示す方針で進めています。
これが，数学的帰納法においてかなり重要で，ほとんどの問題集の解答や参考書では記述していないものになります。メリットを挙げておきます。

示すものが簡単になるとはどういうことでしょうか。
問題集などでは，(イ)は以下のような記述をします。(①を書くところまでは同じ。)

$(k+1)!=(k+1)\cdot k!$
　 　　　 $≧(k+1)\cdot2^{k-1}$
　 　　　 $≧2\cdot2^{k-1}$
　 　　　 $=2^k$
　 　　　 $=2^{(k+1)-1}$
よって，$n=k+1$ のときも(☆)が成り立つ。

違いは分かりますか？②を記述していない場合，示すべき式は(☆) に $n=k+1$ を代入した$$(k+1)!≧2^{(k+1)-1} \enspace$$でした。つまり，最終的に，右辺を $2^{(k+1)-1}$ としなくてはなりません。これを事前に整理しておくことで，$$(k+1)!≧2^{k} \enspace \cdots \text{②}$$となるので，右辺は $2^{k}$ を目指せばよくなるのです。今回の問題では大きな差はないかもしれませんが，難しい問題になってくると，先に整理したかどうかで証明すべき式の難易度が大きく変わってきます。数学的帰納法が苦手という人は，②を書くことを意識するだけでも，苦手意識がかなり減るはずですよ。

次に，②の証明をするとき，$(k+1)!$ を $(k+1)!=(k+1)\cdot k!$ とした理由は説明できますか？これをなんとなくで行っていては数学的帰納法は使いこなせません。分かりますか？
今回，$n=k$ のとき(☆)が成り立つと仮定して，代入して$$k!≧2^{k-1} \enspace \cdots \text{①}$$という式が得られています。これは「使える式」という解釈ではダメです。「(なんとかして)使うべき式」です。つまり，$k!$ を作り出すことが最優先事項ということになるのです。だから　$(k+1)!$ $=$ $(k+1)$ $\cdot$ $k!$ としたんです。ここも，難しい問題になればなるほど重要になります。

普段から，(☆) に $n=k+1$ を代入して整理した式②を書くこと，②を証明するとき(☆) に $n=k$ を代入した式①を必ず使うことを意識してるかどうかが，実践問題で大きな差になります。意識してなかった人，これから学習する人は，必ずこの $2$ 点を意識して取り組んでください。

答案

(証明)$$n!≧2^{n-1} \enspace \cdots \text{(☆)}$$とする。

(ア) $n=1$ のとき
$(\text{左辺})=1!=1$，$(\text{右辺})=2^0=1$
よって，(☆)が成り立つ。

(イ) $n=k$ のとき (☆) が成り立つと仮定すると$$k!≧2^{k-1} \enspace \cdots \text{①}$$

$n=k+1$ のとき $(k+1)!≧2^{(k+1)-1} \enspace$
すなわち $(k+1)!≧2^{k} \enspace \cdots \text{②}$ が成り立つことを示す。
$(k+1)!$ $=$ $(k+1)$ $\cdot$ $k!$
　　　 　$≧$ $(k+1)$ $\cdot$ $2^{k-1}$ (∵①より)
　　　 　$≧$ $(1+1)$ $\cdot$ $2^{k-1}$
　　　 　$=$ $2$ $\cdot$ $2^{k-1}$
　　　 　$=$ $2^{k}$
よって，$n=k+1$ のときも (☆) が成り立つ。

(ア)，(イ) より，すべての自然数 $n$ について (☆) が成り立つ。（証明終了）

数学的帰納法による一般項（推測型の一般項）

問題

解説授業

$a_{n+1}=a_{n}^{\enspace2}+2na_n-2$

見たことのない型の漸化式ですね。こういう場合はパターンとして一般項を求めることができないため，$n=1，2，3，\cdots$ と代入して $a_2$，$a_3$，$a_4$，… を具体的に求めて規則がないか調べましょう。今回は (1) でそれをさせてきていますが，よく分からない数列は具体的に求めることを癖にしておきましょう。
(1) $n=1，2，3$ と順に代入して，

$\begin{split}
a_2 &= a_{1}^{\enspace2}+2 \cdot 1 \cdot a_1-2 \\
&= (-1)^2+2\cdot (-1)-2 \\
&=-3
\end{split}$

$\begin{split}
a_3 &= a_{2}^{\enspace2}+2 \cdot 2 \cdot a_2-2 \\
&= (-3)^2+4\cdot (-3)-2 \\
&=-5
\end{split}$

$\begin{split}
a_4 &= a_{3}^{\enspace2}+2 \cdot 3 \cdot a_3-2 \\
&= (-5)^2+6\cdot (-5)-2 \\
&=-7
\end{split}$

これは簡単ですね。強いて言えば，右辺の $n$ に代入する値を間違えないようにしましょう。
例えば $a_2$ を求めるとき，右辺の $n$ に $2$ を代入しないように気を付けてください。

(2) ここからが本題です。
$a_1=-1$，$a_2=-3$，$a_3=-5$，$a_4=-7$
という結果を見て何か気付きますか？
これは，すぐに気づけると思います。
$2$ ずつ減っている。つまり等差数列になっていますね。
初項 $-1$，公差 $-2$ の等差数列より，
$a_n=-1+(n-1)\cdot (-2)$
よって，
$a_n=-2n+1$
と，推測できます。
ここで気を付けて欲しいのは，これはあくまで予想であって合っているかは分かりません。
ちなみに，(1) と同様にして続きを求めてみると，
$a_5=-9$，$a_6=-11$，$a_7=-13$
となり，合っていそうな気がします。
でも，$n=100$ や $n=100000$，そしてさらにその先も合っているという保証はありません。すべての自然数 $n$ を代入して成り立つことを確かめればいいのですが，自然数は無限にあるのでそんなことはできませんね。
ここで登場するのが，数学的帰納法です。
数学的帰納法により，すべての自然数で $n$ で $a_n=-2n+1$ が成り立つことを証明できれば，一般項は $a_n=-2n+1$ と答えることができますね。
証明の流れは (1) と全く変わらないので，答案で確認してください。

答案

$a_1=-1$，$a_{n+1}=a_{n}^{\enspace2}+2na_n-2$

(1) $a_2=-3$，$a_3=-5$，$a_4=-7$ (答)

(2) (1)より $a_n=-2n+1$ と推測できる。これが正しいことを数学的帰納法により証明する。$$a_n=-2n+1 \enspace \cdots \text{(☆)}$$とする。

(ア) $n=1$ のとき
$a_1=-2\cdot1+1=-1$
よって，(☆)が成り立つ。

(イ) $n=k$ のとき (☆) が成り立つと仮定すると$$a_k=-2k+1 \enspace \cdots \text{①}$$

$n=k+1$ のとき $a_{k+1}=-2(k+1)+1$
すなわち $a_{k+1}=-2k-1 \enspace \cdots \text{②}$ が成り立つことを示す。

もとの漸化式より
$a_{k+1}=a_{k}^{\enspace2}+2ka_k-2$
①より，
$a_{k+1}$ $=$ $(-2k+1)^{2}$ $+$ $2k$$(-2k+1)$ $-$ $2$
　$\enspace\enspace\enspace=4k^2-4k+1-4k^2+2k-2$
　$\enspace\enspace\enspace$$=$ $-2k-1$
よって，$n=k+1$ のときも (☆) が成り立つ。

(ア)，(イ) より，すべての自然数 $n$ について (☆) が成り立つ。

以上より，求める一般項は，$$a_n=-2n+1\enspace\enspace (\text{答})$$

数学的帰納法による証明問題がこれで「解ける！」