漸化式の基本３｜数学的帰納法はイメージは「ドミノ倒し」！

[数学的帰納法]は高校数学で学ぶ重要な証明法の１つで，「任意の自然数$n$に対して，〜が成り立つことを示せ．」という問題に対して威力を発揮します．

実際に[数学的帰納法]は[背理法]と並んで，大学受験では超頻出です．

初めて[数学的帰納法]を学んだとき，多くの人は「なんか不思議な論法やなあ」と思うようで，実際に問題を解くにつれて腑に落ちてくる人は多いようです．

この記事では，[数学的帰納法]のイメージを最初に説明し，その後に実際に数学的帰納法を用いて例題を考えます．

一連の記事はこちら

【漸化式の基本１｜漸化式とは？漸化式の考え方を例から解説！】
【漸化式の基本２｜等差数列，等比数列の漸化式】
【漸化式の基本３｜数学的帰納法はイメージは「ドミノ倒し」！】←今の記事

背理法の記事はこちら

【背理法１｜背理法はこう考える！仕組みを具体例から理解する】
【背理法２｜背理法が有効な証明の２つのタイプと例】

数学的帰納法の仕組み
数学的帰納法の例

数学的帰納法の仕組み

「任意の自然数$n$に対して，〜が成り立つことを示せ．」という問題に[数学的帰納法]が有効であることは冒頭に述べた通りです．

[数学的帰納法]は，次のような論法の証明です．

$n=1$のときに成り立つことを示す．
「$n=k$のときに成り立つ」とし，それを利用して$n=k+1$のときに成り立つことを示す．

さて，この[数学的帰納法]は「ドミノ倒し」に例えることができます．

1は「最初のピースを倒す」
2は「$k$個目のピースが倒れると，$k+1$個目のピースも倒れる」

ということに相当します．

もし1が欠けていると「最初のピースが倒せない」し，2が欠けていると「$k$個目が倒れても，$k+1$個目が倒れてくれないかもしれない」ので，1,2のどちらが欠けても[数学的帰納法]は成り立ちませんね．

これが「数学的帰納法」のイメージです．

1,2が証明できれば，

1より$n=1$のときが成り立つ．
$n=1$が成り立つから，2より$n=2$のときが成り立つ．
$n=2$が成り立つから，2より$n=3$のときが成り立つ．
$n=3$が成り立つから，2より$n=4$のときが成り立つ．
……

と続いていくので，任意の自然数$n$に対して成り立つことが証明できたことになるわけです．

注意ですが，問題によっては「3以上の任意の自然数$n$に対して，〜を示せ．」などとなっている場合がありますが，このときは

$n=3$のときに成り立つことを示す．
「$n=k$のときに成り立つ」とし，それを利用して$n=k+1$のときに成り立つことを示す．

とすれば良いことは，以上の話から分かるでしょう．

数学的帰納法は「最初の場合に成り立つこと」を示し，「$n=k$で成り立つとき，$n=k+1$でも成り立つこと」を示すのが基本的な数学的帰納法の王道パターンである．

数学的帰納法の例

それでは，数学的帰納法で証明できる問題を考えます．

以下の問題を数学的帰納法を用いて解け．

任意の自然数$n$に対して，等式$(*):1+3+5+\dots+(2n-1)=n^2$が成り立つことを示せ．
2以上の任意の自然数$n$に対して，不等式$(*):3^n>4n$が成り立つことを示せ．
漸化式$a_1=1,a_{n+1}=\dfrac{a_n}{1+a_n}$を満たす数列$\{a_n\}$の一般項を求めよ．

例１

任意の自然数$n$に対して，等式$(*):1+3+5+\dots+(2n-1)=n^2$が成り立つことを数学的帰納法により示しましょう．

[1]　$n=1$のとき

$((*)の左辺)=1=1^2=((*)の右辺)$となって，等式$(*)$が成り立つことが分かります．

[2]　「$n=k$のとき$(*)$が成り立つ」とし，$n=k+1$のとき$(*)$が成り立つことを示します．すなわち，「$1+3+5+\dots+(2k-1)=k^2$が成り立つ」とし，$1+3+5+\dots+\{2(k+1)-1\}=(k+1)^2$が成り立つことを示します．

$1+3+5+\dots+(2k-1)=k^2$が成り立つから，

$\begin{align*} &1+3+5+\dots+\{2(k+1)-1\} \\=&\{1+3+5+\dots+(2k-1)\}+\{2(k+1)-1\} \\=&k^2+2k+1 \\=&(k+1)^2 \end{align*}$

となって，$n=k+1$の場合にも等式$(*)$が成り立つことが分かりました．

[1], [2]より，$(*)$が示されました．

例２

2以上の任意の自然数$n$に対して，不等式$(*):3^n>4n$が成り立つことを数学的帰納法により示します．

[1]　$n=2$のとき

$((*)の左辺)=3^2=9>8=4\times2=((*)の右辺)$となって，不等式$(*)$が成り立つことが分かります．

[2]　「$n=k$ $(k\ge2)$のとき$(*)$が成り立つ」とし，$n=k+1$のとき不等式$(*)$が成り立つことを示します．すなわち，「$3^k>4k$が成り立つ」とし，$3^{k+1}>4(k+1)$が成り立つことを示します．

$3k>k+1$であることに注意すると，$3^k>4k$が成り立つから，

$\begin{align*} 3^{k+1}=3\times3^{k}>3\times4k=4\times3k>4\times(k+1) \end{align*}$

となって，$n=k+1$の場合にも不等式$(*)$が成り立つことが分かりました．

[1], [2]より，$(*)$が示されました．

例３

$a_1=1$, $a_{n+1}=\dfrac{a_n}{1+a_n}$だから，数列$\{a_n\}$を初項から順に求めると，

$\begin{align*} &a_1=1, \\&a_2=\frac{a_1}{1+a_1}=\frac{1}{1+1}=\dfrac{1}{2}, \\&a_3=\frac{a_2}{1+a_2}=\frac{\frac{1}{2}}{1+\frac{1}{2}}=\frac{1}{2+1}=\dfrac{1}{3}, \\&a_4=\frac{a_3}{1+a_3}=\frac{\frac{1}{3}}{1+\frac{1}{3}}=\frac{1}{3+1}=\dfrac{1}{4} \end{align*}$