【数B】数学的帰納法を用いた証明問題（考え方の基礎を分かりやすく解説）

今回は数学的帰納法とは何かを徹底解説していきます。

突然ですが、皆さんは数学的帰納法とは何かを説明できますか？

$\small n=k$を仮定して$\small n=k+1$でも成り立つことを示すやつ、不等式の証明問題で使うやつ、ドミノ倒し…など、いろいろなイメージは浮かんでくると思いますが、そもそも何なんのかと問われると答えに詰まってしまう人も多いと思います。

そこで本記事では、数学的帰納法とは何かについて、考え方の基礎から徹底解説していきます。さらに、数学的帰納法を利用した証明問題についても、数学的帰納法を使う問題の見極めポイントや数学的帰納法を使って問題を解くときの考え方のコツを分かりやすく解説していきますので、是非最後まで確認してみてください！

　本記事はこんな人におすすめ

数学的帰納法の考え方について知りたい人
数学的帰納法を使った問題の解き方のコツを知りたい人
数学的帰納法を使う問題の見極め方を知りたい人
定期テスト対策・大学入試対策として数学的帰納法の入試問題を解きたい人

　本記事のレベル

重要度

低

1

2

3

4

高
難易度

易しい

1

2

3

4

難しい
暗記/理解

暗記重視

1

2

3

4

理解重視

【徹底解説】数学的帰納法の基礎
1. 【講義1】数学的帰納法とは？
2. 【講義2】数学的帰納法を用いた証明の流れ
【問題＆解説】数学的帰納法を用いた証明問題
本記事のまとめ

【徹底解説】数学的帰納法の基礎

【講義1】数学的帰納法とは？

数学的帰納法のポイントとなる考え方からおさらいしましょう！

数学的帰納法の基礎

① 最初が正しいことを証明する
② 次が正しいことを証明する
　→すると全部が正しいことが証明できる、という証明方法。

すべての自然数（1,2,3,…）で成り立つことを証明するためには、$\small n=1$で成り立つ、$\small n=2$で成り立つ…、と一つ一つを順番に確認しなくても、実は2つのことが証明できればOKなのです。

それが、『$\small n=1$（一番最初）が成り立つこと』と『次が成り立つこと』です。

なぜならば、『$\small n=1$（一番最初）が成り立つ』ことが分かると、『次が成り立つ』ことから$\small n=2$も正しいことが分かります。さらに、$\small n=2$が正しいことが分かると、『次が成り立つ』ことから$\small n=3$も正しいことが分かります。あとはこれを永遠に繰り返すことで、すべての自然数$\small n$に対して正しいということが言えるというわけです。

このように、芋づる式に次から次へと証明できることから、数学的帰納法は全体が成り立つことをドミノ倒し的に示す証明方法であるとよく言われます。

【講義2】数学的帰納法を用いた証明の流れ

数学的帰納法の考え方が理解できたところで、次は数学的帰納法を使って証明をする流れについて解説していきます。

イメージしやすいように具体例で流れを確認してきましょう。

（問題）
『太陽は東から昇る』ことを数学的帰納法で証明せよ。
ただし、太陽が常に同じ方角から昇ることは経験的に分かっているとするものとする。

（解答）
観測開始の1日目（$\small k=1$）に太陽が東から昇っていることを確認したとします。

すると、太陽が常に同じ方角から昇ることから、2日目も、3日目も、4日目も…、太陽は東から昇ることになるので、すべての日に対して『太陽は東から昇る』ことが分かります。

赤字部分を数学的帰納法っぽく言い換えると
ある日（$\small k$日目）に太陽が東から昇ったと仮定すると、太陽は同じ方角から昇るので次の日（$\small k+1$日目）も太陽は東から昇ることになる（$\small n=k$が成り立つならば$\small n=k+1$も成り立つ）
となります。

ここが数学的帰納法のポイントで、次もそうなることを証明してしまえば、いちいち何日目がどうかを書かなくても全部そうなるよね、ということが一気に説明できてしまうわけです。

よって、数学的帰納法からすべての日に対して『太陽は東から昇る』ことが証明できます。

このように、講義1で学んだ2ステップで証明ができることが分かります。この流れはどんな問題でも同じなので、しっかり頭に叩き込んでしまいましょう。

Point：数学的帰納法を用いた証明手順

STEP1：最初が成り立つことを確認する
STEP2：次が成り立つことを確認する
　　　　（$\small n=k$で成り立つならば、$\small n=k+1$でも成り立つ）

【問題＆解説】数学的帰納法を用いた証明問題

【問題1】階乗やべき乗を含む不等式証明

問題1：階乗やべき乗を含む不等式証明（難易度：★☆☆）

$\small n > 3$のとき、不等式 $\small n! > 2^n$が成り立つことを示せ。
[富山県立大]

問題解決のKey

・不等式証明の基本方針は『（大）$\small -$（小）$\small >0$』を示すこと。
・自然数に関する不等式証明は、数学的帰納法を視野に入れる。
　※$\small n!$があることから、$\small n$は自然数と考えてOK。
　実数の不等式証明であれば、関数とみなして解く方針になるが、自然数の場合
　連続的ではないので、$\small n=1、2、3、\cdots$の場合と順々に示す方針がとれるので
　数学的帰納法が利用できることは覚えておくとよい。
　

　解説

不等式に階乗が含まれることから、$\small n$は自然数と考えてよい。すべての自然数で不等式が成り立つ問題なので、数学的帰納法を利用することで証明を試みる。

STEP

最初が成り立つことを確認する

$\small n>3$の範囲で最小の自然数は$\small n=4$である。

$\small n=4$のとき、問題の不等式は

\begin{cases}
\small (左辺)=4!=24\\
\small (右辺)=2^4=16\\
\end{cases}

より、$\small n!>2^n$が成り立つ。

●補足
数学的帰納法では、$\small n=1$のときに不等式が成立することを証明するのが基本パターンだが、本問のように、そもそも不等式が成り立つ$\small n $の値が1よりも大きい場合は、不等式が成り立つときの最小の$\small n$のときに成り立つかを示せばよい。
数学的帰納法を用いた証明手順に、あえて『最初が成り立つことを確認する』と書いたのは必ずしも$\small n=1$とは限らないからである。

STEP

次が成り立つことを確認する

$\small n=k$（$\small k>3$）のとき、問題の不等式 $\small k!>2^k$ …①が成り立つと仮定する。このとき、$\small n=k+1$で $\small (k+1)!>2^{k+1}$が成り立つことを示せばよい（次が成り立つことを示す）。

方針としては、不等式証明の基本方針『（大）$\small -$（小）$\small >0$』を示す方針で考える。

\begin{split}
\small (k+1)!-2^{k+1} & \small =(k+1)\color{red}{k!}-2\cdot2^k\\
& \small \color{red}>(k+1)\color{red}{2^k}-2\cdot2^k \quad \color{#ef5350}{◀①の不等式を利用 [*1]}\\
& \small =\{(k+1)-2\}2^k\\
& \small =(k-1)2^k \color{red}{>0}\\
\end{split}

最後は、$\small k>3$なので$\small k-1>0$、$\small 2^k$ももちろん正なので、正の値同士をかけ算した値ももちろん正であることを利用した。

$\small *1$：①は仮定した式なのに利用してもいいの？
数学的帰納法では$\small n=k$で不等式が成り立つことを仮定して、$\small n=k+1$でも成り立つのかを確認します。そのため、$\small n=k$で成り立つか分からないのに正しいと仮定しちゃっていいの？と疑問に思うかもしれません。
結論、問題ありません。実はこの仮定ができるように最初が成り立つかを確認しています。本問であれば、$\small n=4$で不等式が成り立つことが分かっているので、$\small k=4$では少なくとも不等式が成り立つことが確認できています。なので、$\small k>3$のとある$\small k$で成り立つと仮定してよいわけです。
数学的帰納法の問題では、$\small n=k$のときに成り立つと仮定した関係式を活用して$\small n=k+1$の場合の確認をしていくことになるので、$\small n=k$の関係式の形を作り出して積極的に利用していきましょう。

よって、$\small (k+1)!-2^{k+1}>0\space \Leftrightarrow \space \color{red}{(k+1)!>2^{k+1}}$が示せたが、これは問題の不等式で$\small n=k+1$の場合を表していることから、$\small n=k+1$の場合にも成立する。

ゆえに、$\small n>3$の自然数に対して、$\small n! > 2^n$が成り立つ（証明終）。

【問題2】数列の和を含む不等式証明

問題2：数列の和を含む不等式証明（難易度：★☆☆）

$\small n ≧ 2$のすべての自然数$\small n$に対して、
$$\small \displaystyle 1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n} > \frac{2n}{n+1}$$ が成り立つことを示せ。

問題解決のKey

・本問のように計算できない数列の和を含む不等式証明は、数学的帰納法の典型パターン。
・問題1と同様に不等式が$\small n=k$で成り立つと仮定して、$\small n=k+1$の場合でも成り立つことを示せればよい。

　解説

$\small n≧2$のすべての自然数に対して問題の不等式が成り立つことの証明なので、数学的帰納法を用いて証明する。

$\small n=2$のとき、不等式の左辺は

$$\small 1+\frac{1}{2}=\frac{3}{2}=1.5$$

右辺は、

$$\small \left. \frac{2n}{n+1}\right |_{n=2}=\frac{4}{3}=1.33\cdots$$

なので、（左辺）>（右辺）となり、問題の不等式が成り立つ【最初が成り立つ】。

ここで、$\small n=k$のときに

$$\small \displaystyle 1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{k} > \frac{2k}{k+1}\space \cdots(*)$$

が成り立つと仮定した場合に、$\small n=k+1$で

\begin{split}
\small \displaystyle \left(1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{k}+\frac{1}{k+1}\right) – \frac{2(k+1)}{(k+1)+1}\color{red}{>0}
\end{split}

が成り立つことを示せればよい。

\begin{split}
&\small \displaystyle \left(1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{k}+\frac{1}{k+1}\right) – \frac{2(k+1)}{(k+1)+1}\\
& \quad \small \displaystyle =\color{red}{1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{k}}+\frac{1}{k+1}- \frac{2k+2}{k+2}\\
& \quad \small \displaystyle \color{red}{> \frac{2k}{k+1}}+\frac{1}{k+1}- \frac{2k+2}{k+2} \quad \color{red}{◀(*)を利用}\\
& \quad \small \displaystyle = \frac{2k+1}{k+1}- \frac{2k+2}{k+2}\\
& \quad \small \displaystyle = \frac{(2k+1)(k+2)-(2k+2)(k+1)}{(k+1)(k+2)}\\
& \quad \small \displaystyle = \color{red}{\frac{k}{(k+1)(k+2)}>0}\quad (∵\space k≧2)\\
\end{split}

よって、

\begin{split}
\small \displaystyle 1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{k}+\frac{1}{k+1} > \frac{2(k+1)}{(k+1)+1}
\end{split}

が成り立つことから、問題の不等式は$\small n=k+1$でも成り立つ【次も成り立つ】。

ゆえに、すべての自然数$\small n$に対して問題の不等式が成り立つ（証明終）。

【問題3】整数に関する証明

問題3：整数に関する証明（難易度：★★☆）

$\small n$が自然数のとき、$\small 11^{n+1}+12^{2n-1}$は19で割り切れることを証明せよ。
[学習院大]

問題解決のKey

・$\small 11^{n+1}+12^{2n-1}$が19で割り切れるということは、19の倍数であることなので、$\small 11^{n+1}+12^{2n-1}=19m$（$\small m$は整数）と表せることを示せればよい。

　解説

$\small 11^{n+1}+12^{2n-1}$が19の倍数であるということは、すべての自然数$\small n$に対して、

$$\small 11^{n+1}+12^{2n-1}=19m \quad (m\mathbf{は整数})$$

が成り立つことを示せればよい。上記の等式が成り立つことを数学的帰納法で示す。

まず、$\small n=1$のとき、$\small 11^{n+1}+12^{2n-1}$は

\begin{split}
\small 11^2+12 &\small =133\\
&\small =19 \times 7\\
\end{split}

より、133は19の倍数なので19で割り切れる【最初が成り立つ】。

ここで、$\small n=k$のときに

$$\small 11^{k+1}+12^{2k-1}=19m \space (m\mathbf{は整数}) \quad \cdots (*)$$

が成り立つと仮定する。

●補足
このあとは、$\small n=k+1$の式
$$\small 11^{k+2}+12^{2k+1}=19×\mathbf{整数}$$
が成り立つことを示せればよい（左辺を計算していって、『19×整数』（右辺）になることが示せればよい）。

このとき、

\begin{split}
\small 11^{k+2}+12^{2k+1} &\small =11 \cdot \color{red}{11^{k+1}} +12^{2k+1}\\
&\small =11 \cdot (\color{red}{19m -12^{2k-1}}) +12^{2k+1} \quad \color{red}{◀(*)を代入}\\
&\small =11 \cdot 19m – 11 \cdot 12^{2k-1} +12^2 \cdot 12^{2k-1}\\
&\small =11 \cdot 19m +(144-11)\cdot 12^{2k-1}\\
&\small =11 \cdot 19m +133\cdot 12^{2k-1}\\
&\small =19 \color{red}{(11m +7\cdot 12^{2k-1})}\\
\end{split}

最後の式の赤字部分 $\small 11m +7\cdot 12^{2k-1}$は整数 [*1]なので、19×整数の形となることから、

\begin{split}
\small 11^{k+2}+12^{2k+1}=\color{red}{19\times\mathbf{整数}}
\end{split}

が成り立つので、$\small n=k+1$の場合でも$\small 11^{k+2}+12^{2k+1}$は19の倍数である【次も成り立つ】。

よって題意は示された（証明終）。

*1：19×整数について
$\small 11m +7\cdot 12^{2k-1}$と非常に複雑な式だが、$\small m$と$\small k$に適当な整数を入れて計算すると（莫大な数になるが…）必ず整数になるので、19×整数の形になっている。19の倍数であることを示すには、19という共通因数をうまく括りだすことがポイント。

【問題4】工夫が必要な不等式証明

問題4：工夫が必要な不等式証明（難易度：★★★）

数学的帰納法によって、$\small \displaystyle \left(\frac{n+1}{2}\right)^n > n!$を証明せよ。ここに、$\small n$は2以上の整数とする。
[京都大]

問題解決のKey

・本問は問題1の不等式証明と形は似ているが、問題1は$\small 2^{k+1}=2\cdot 2^k$と分離して$\small 2^k$の形を作り出せたのに対して、本問はべき乗の底にも$\small n$が含まれるため、$\small n=k+1$の不等式のままだと$\small n=k$の関係式をうまく適用できない点が問題1と大きく異なるポイント。
・$\small n=k+1$で
\begin{split}
\small \left(\frac{k+2}{2}\right)^{k+1} > (k+1)!
\end{split}
が成り立つことを示すにあたって、$\small n=k$での関係式の形である$\small \displaystyle \left(\frac{k+1}{2}\right)^{k}$の形を無理やり作り出す[$\small *1$]ことが基本方針。
・本問では、
\begin{split}
\small \left(\frac{k+2}{2}\right)^{k+1} &\small =\left(\color{red}{\frac{k+1}{2}}+\frac{1}{2}\right)^{k+1} \\
&\small =\left(\frac{k+1}{2}\right)^{k+1} +{}_{k+1} C_{1}\left(\frac{k+1}{2}\right)^{k}\cdot \frac{1}{2} + \cdots \\
\end{split}
　のように二項定理で展開することで、$\small \displaystyle \left(\frac{k+1}{2}\right)^{k}$の形を作る。

$\small *1$：$\small \displaystyle \left(\frac{k+1}{2}\right)^{k}$の形を作り出す方針の検討
一番最初に思いつくのが、明らかに$\small \displaystyle \frac{k+2}{2}>\frac{k+1}{2}$が成り立つことから、
\begin{split}
&\small \color{red}{\left(\frac{k+2}{2}\right)^{k+1}}- (k+1)!\\
&\small \quad \color{red}{>\left(\frac{k+1}{2}\right)^{k+1}}- (k+1)!\\
\end{split}
のように、べき乗の底を $\small \displaystyle \frac{k+2}{2}$ → $\small \displaystyle \frac{k+1}{2}$に丸ごと置き換える方針だろう。

この方針で計算を進めていくと、
\begin{split}
&\small \left(\frac{k+1}{2}\right)^{k+1}- (k+1)!\\
&\small \quad =\left(\frac{k+1}{2}\right)\cdot \color{red}{\left(\frac{k+1}{2}\right)^{k}}- (k+1)!\\
&\small \quad \color{red}>\left(\frac{k+1}{2}\right)\cdot \color{red}{k!}- (k+1)\cdot k! \quad ◀ \space n=kの不等式を適用\\
&\small \quad =-\left(\frac{k+1}{2}\right)\cdot k!\\
\end{split}
となり、『（大）-（小）＞0』を目指していたが、計算結果が負になってしまいうまくいかない。これは、べき乗の底を丸ごと置き換える方針だと雑すぎたということなので、もう少し丁寧に評価しないといけないことを意味する。

そこで、問題解決のKeyに記載したようにべき乗の底を$\small　\displaystyle \left(\frac{k+1}{2}+●\right)^{k+1}$の形と捉えて二項展開してみようという発想に至る。

　解説

$\small n=2$のとき、

\begin{split}
\small （左辺）&\small =\left. \left(\frac{n+1}{2}\right)^{n}\right|_{n=2}\\
& \small =\left(\frac{3}{2}\right)^2=\frac{9}{4}
\end{split}

\begin{split}
\small （右辺）=n!|_{n=2} =2\left(=\frac{8}{4}\right)
\end{split}

より、（左辺）>（右辺）が成り立つ【最初が成り立つ】。

$\small n=k$で

\begin{split}
\small \left(\frac{k+1}{2}\right)^{k} > k! \quad \cdots①
\end{split}

が成り立つと仮定すると、$\small n=k+1$の場合に

\begin{split}
\small \left(\frac{k+2}{2}\right)^{k+1} > (k+1)!
\end{split}

が成り立つことが示せればよい。

ここで、

\begin{split}
&\small \left(\frac{k+2}{2}\right)^{k+1} – (k+1)!\\
&\small \quad =\left(\frac{k+1}{2}+\frac{1}{2}\right)^{k+1} – (k+1)!\\
\end{split}

と考えると、第1項目について二項定理[$\small *2$]より

\begin{split}
&\small \left(\frac{k+1}{2}+\frac{1}{2}\right)^{k+1} \\
&\small \quad =\left(\frac{k+1}{2}\right)^{k+1} +{}_{k+1} C_{1}\left(\frac{k+1}{2}\right)^{k}\cdot \frac{1}{2} + \cdots +\left(\frac{1}{2}\right)^{k+1} \\
&\small \quad \color{red}>\left(\frac{k+1}{2}\right)^{k+1} +\frac{k+1}{2}\cdot \left(\frac{k+1}{2}\right)^{k} \quad \color{red}{◀第2項目までで打ち切り}\\
&\small \quad =2\left(\frac{k+1}{2}\right)^{k+1}\\
\end{split}

$\small *2$：二項定理
\begin{split}
\small (a+b)^n &\small =a^n+{}_n C_{1}a^{n-1}b+{}_n C_{2}a^{n-2}b^2\\
&\small \quad +\cdots+{}_n C_{n-1}ab^{n-1}+b^{n}\\\
\end{split}
≪$\small n=3$の場合の具体例≫
・$\small (a+b)^3=a^3+3a^2b+3ab^2+b^3$

となることから、

\begin{split}
&\small \left(\frac{k+1}{2}+\frac{1}{2}\right)^{k+1} >2\left(\frac{k+1}{2}\right)^{k+1} \quad \cdots②\\
\end{split}

が成り立つ。

よって、

\begin{split}
&\small \color{#009505}{\left(\frac{k+1}{2}+\frac{1}{2}\right)^{k+1}} – (k+1)!\\
&\small \quad >\color{#009505}{2\left(\frac{k+1}{2}\right)^{k+1}} – (k+1)! \quad \color{#009505}{◀②の利用}\\
&\small \quad >2\cdot\frac{k+1}{2}\color{red}{\left(\frac{k+1}{2}\right)^{k}} – (k+1)!\\
&\small \quad >(k+1)\color{red}{k!} – (k+1)! \quad \color{red}{◀①の利用}\\
&\small \quad =(k+1)! – (k+1)! \\
&\small \quad =0 \\
\end{split}

ゆえに、

\begin{split}
&\small \left(\frac{k+2}{2}\right)^{k+1} – (k+1)!>0\\
\end{split}

が成り立つ。これは、問題の不等式で$\small n=k+1$の場合を表している【次も成り立つ】。

よって、題意は示された（証明終）。

【問題5】一般項の推測と証明

問題5：一般項の推測と証明（難易度：★☆☆）

数列$\small \{a_{n}\}$を$\small \displaystyle a_1=2、a_{n+1}=1+\frac{1}{na_n}\space (n=1,2,3,\cdots)$で定める。
このとき、一般項$\small a_n$を推測し、数学的帰納法で証明せよ。

問題解決のKey

・推測した内容がすべての自然数に対して成り立つことを示すときにも数学的帰納法が使える。
・本問では、推測した一般項が$\small a_k$で成り立つと仮定した後に、漸化式
$$\small a_{n+1}=1+\frac{1}{na_n}$$
　を利用して$\small a_{k+1}$の場合にも成り立つことを示す方針で考える。

　解説

最初の数項を具体的に計算することで、一般項の形を推測する。

\begin{split}
&\small a_2=1+\frac{1}{1\cdot a_1}=\frac{3}{2}\\
&\small a_3=1+\frac{1}{2\cdot a_2}=\frac{4}{3}\\
&\small a_4=1+\frac{1}{3\cdot a_3}=\frac{5}{4}\\
\end{split}

この結果を見ると、分母と分子が連続する数になっていることから、一般項は、

\begin{split}
&\small a_n=\frac{n+1}{n} \quad \cdots (*)
\end{split}

と推測できる。これが正しいことを数学的帰納法で示す。

$\small n=1$のとき、$\small (*)$に代入することで

\begin{split}
&\small a_{1}=\frac{1+1}{1}=2
\end{split}

より、確かに数列の第1項目と一致する【最初が成り立つ】。

$\small (*)$が$\small n=k$のときに成り立つ、すなわち

\begin{split}
&\small a_{k}=\frac{k+1}{k}
\end{split}

が成り立つと仮定すると、数列$\small \{a_n\}$が満たす漸化式から

\begin{split}
\small a_{k+1} &\small =1+\frac{1}{k\color{red}{a_k}}\\
&\small =1+\frac{1}{k\cdot \color{red}{\dfrac{k+1}{k}}}\\
&\small =1+\frac{1}{k+1}\\
&\small =\frac{k+2}{k+1}\\
&\small =\frac{(k+1)+1}{k+1}\\
\end{split}

これは、$\small (*)$で$\small n=k+1$とした式であることから、$\small n=k+1$の場合にも成り立つ【次も成り立つ】。

よって、すべての自然数に対して$\small (*)$が成り立つことから、一般項は

\begin{split}
&\small a_n=\frac{n+1}{n}
\end{split}

で表せることが証明された。

本記事のまとめ

今回は数学的帰納法の基本的な考え方と数学的帰納法を利用した典型問題について解説しました。最後に、今回の重要ポイントをおさらいしておきましょう。

☆重要Point☆
#数学的帰納法の基本的考え方
・最初が成り立つことを確認する（最小の$\small n$で成り立つか？）
・次が成り立つことを確認する（$\small n=k$で成り立つならば$\small n=k+1$でも成り立つか？）

#数学的帰納法を使う証明の見極めポイント
・すべての自然数（または●以上の自然数）に対して成り立つことを証明する問題で利用する
　※実数になると$\small n=k$の次（$\small n=k+1$）が成り立つことを示したところで間の値で成り立つことが証明できないので使えない…

#数学的帰納法で証明するときのコツ
・$\small n=k+1$の証明では、$\small n=k$の関係式の形を作り出して代入しよう！