東大塾長の山田です。
このページでは、数学Bの「数学的帰納法」について解説します。
今回は数学的帰納法の考え方・解き方を，大学受験で頻出の問題（等式・倍数・不等式・漸化式）を通して具体的に超わかりやすく解説していきます。
ぜひ勉強の参考にしてください！
1. 数学的帰納法とは？超わかりやすく説明
漸化式では
［1］\( a_1 = 1 \)
［2］\( a_{n+1} = a_n + n \)（\( n = 1, 2, 3, \cdots \)）
［1］をもとにして，［2］において \( n = 1, 2, 3, \cdots \) とすると
\( a_2 = a_1 + 1 = 1 + 1 = 2 \)
\( a_3 = a_2 + 2 = 2 + 2 = 4 \)
\( a_4 = a_3 + 3 = 4 + 3 = 7 \)
\( \cdots \cdots \cdots\)
となり，\( a_1, \ a_2, \cdots, a_n, \cdots \) の値が1通りに定まります。
つまり，「初項 \( a_1 \)」と「\( a_k \) から \( a_{k+1} \) を求める規則」が与えられれば，すべての自然数 \( n \) について，\( a_n \) を定めることができます。
これと同じような考え方で，
自然数 \( n \) に関する命題 \( P \) がすべての自然数 \( n \) について成り立つことを証明したいときに
［1］\( n = 1 \) のとき \( P \) が成り立つ。
［2］\( n = k \) のとき \( P \) が成り立つと仮定すると，\( n = k+1 \) のときにも \( P \) が成り立つ。
この［1］，［2］を示すことによって
- ［1］から \( n=1 \) のとき \( P \) は成り立つ。
- ①と［2］から \( n = 1+1=2 \) のときも \( P \) は成り立つ。
- さらに，②と［2］から \( n = 2+1=3 \) のときも \( P \) は成り立つ。
- 同様に \( n = 4, 5, 6, \cdots \) のときにも \( P \) は成り立ち，結局すべての自然数 \( n \) について \( P \) は成り立つ。
ことがいえます。
このような証明法を 数学的帰納法 といいます。
まだピンときていなくても，問題を見ていけばイメージが湧くはずです！
さっそくいってみましょう！
2. 数学的帰納法の等式の証明問題
まずは1番スタンダードな「等式の証明問題」です。
\( n \) が自然数のとき，数学的帰納法を用いて次の等式を証明せよ。
\( \displaystyle 1^2 + 2^2 + 3^2 + \cdots + n^2 \\
\displaystyle \ \ \ \ \ \ \ = \frac{1}{6} n (n+1) (2n+1) \cdots ① \)
【証明】
［1］\( n = 1 \) のとき
\( \displaystyle (左辺) = 1^1 = 1 \)
\( \displaystyle (右辺) = \frac{1}{6} \cdot 1 \cdot (1+1) (2 \cdot 1 + 1) = 1 \)
よって，\( n = 1 \) のとき①は成り立つ。
［2］\( n = k \) のとき，①が成り立つと仮定すると
\( \displaystyle \color{magenta}{ 1^2 + 2^2 + 3^2 + \cdots + k^2 } \\
\displaystyle \ \ \ \ \ \ \ = \color{magenta}{ \frac{1}{6} k (k+1) (2k+1) } \cdots ② \)
\( n = k+1 \) のときを考えると，②から
\( \begin{align}
\displaystyle & \color{magenta}{ 1^2 + 2^2 + 3^2 + \cdots + k^2 } + (k+1)^2 \\
\\
& = \color{magenta}{ \frac{1}{6} k (k+1) (2k+1) } + (k+1)^2 \\
\\
& = \frac{1}{6} (k+1) \left\{ k (2k+1) + 6 (k+1) \right\} \\
\\
& = \frac{1}{6} (k+1) (2k^2 + 7k + 6) \\
\\
& = \frac{1}{6} (k+1) (k+2) (2k+3) \\
\\
& = \frac{1}{6} (k+1) \left\{ (k+1) + 1 \right\} \left\{ 2 (k+1) + 1 \right\}
\end{align} \)
よって，\( n = k+1 \) のときにも①は成り立つ。
［1］，［2］から，すべての自然数 \( n \) について①は成り立つ。
- ［1］\( n = 1 \) のときを証明する。
- ［2］\( n = k \) のときを仮定し，\( n = k+1 \) のときを証明する。
［2］の証明では，\( n = k \) のとき成り立つと仮定した式を使って，\( n = k+1 \) のときの式変形をしていくのが定石です。
また，上の解答の赤字部分は，数学的帰納法の決まり文句です。答案はこの通りにつくっていけばOKです！
3. 数学的帰納法の倍数の証明問題
次は「▲の倍数であることを証明」する問題です。
\( n \) を自然数とするとき，\( \displaystyle 7^n – 2n – 1 \) が4の倍数であることを証明せよ。
「\( N \) が▲の倍数である」ことを証明するときは，「\( N = ▲m \)（\( m \) は整数）」とおく。
そこから，「\( N \) が \( n = k+1 \) のときも ▲×(整数)」となることを証明していきます。
【証明】
「\( \displaystyle 7^n – 2n – 1 \) が4の倍数である」を①とする。
［1］\( n = 1 \) のとき
\( \displaystyle 7^1 – 2 \cdot 1 – 1 = 4 \)
よって，①は成り立つ。
［2］\( n = k \) のとき，①が成り立つと仮定すると
\( \displaystyle \color{magenta}{ 7^k – 2k – 1 = 4m（mは整数）} \cdots ② \)
\( n = k+1 \) のときを考えると，②から
\( \begin{align}
& \color{red}{ 7^{k+1} – 2(k+1) – 1 } \\
\\
& = 7 \cdot \color{magenta}{ 7^k } – 2(k+1) – 1 \\
\\
& = 7 ( \color{magenta}{ 4m + 2k + 1 } ) – 2(k+1) – 1 \\
\\
& = 28m + 12k + 4 \\
\\
& = \color{red}{ 4 ( 7m + 3k + 1 ) }
\end{align} \)
\( 7m + 3k + 1 \) は整数だから，\( 4 ( 7m + 3k + 1 ) \) は4の倍数である。
よって，\( n = k+1 \) のときにも①は成り立つ。
以上［1］，［2］から，題意は示された。
4. 数学的帰納法の不等式の証明問題（入試問題）
続いて「不等式の証明問題」です。これは入試でも頻出です！
今回は2次関数とも絡めた入試実践レベルの問題を解説します。
\( n≧5 \) を満たす自然数 \( n \) に対して，次の不等式が成り立つことを証明せよ。
\( n^2 < 2^n \cdots ① \)
[2010 津田塾大]
今回の問題のような大小関係 「\( N > M \) を証明する問題」では，差をつくり「\( N – M > 0 \)」を示せばよい。
【証明】
［1］\( n = 5 \) のとき
\( \displaystyle (左辺) = 5^2 = 25 \)
\( \displaystyle (右辺) = 2^5 = 32 \)
よって，①は成り立つ。
［2］\( n = k （k≧5） \) のとき，①が成り立つと仮定すると
\( \color{magenta}{ k^2 < 2^k } \cdots ② \)
\( n = k+1 \) のときを考えると，②から
\( \begin{align}
2^{k+1} – (k+1)^2 & = 2 \cdot \color{magenta}{ 2^k } – (k+1)^2 \\
\\
& > 2 \cdot \color{magenta}{ k^2 } – (k+1)^2 \\
\\
& = k^2 – 2k – 1
\end{align} \)
（\( (k+1)^2 < 2^{k+1} \)\( \ \Leftrightarrow \ 2^{k+1} – (k+1)^2 > k^2 – 2k – 1 > 0 \) を示したい。）
ここで
\( \begin{align}
y & = k^2 – 2k – 1 （k≧5） \\
& = (k-1)^2 – 2（k≧5）
\end{align} \)
として考えると
上図より，\( k ≧ 5 \) のとき
\( k^2 – 2k – 1 ≧ 14 > 0 \)
よって
\( 2^{k+1} – (k+1)^2 > k^2 – 2k – 1 > 0 \)
\( ∴ \ 2^{k+1} > (k+1)^2 \)
よって，\( n = k+1 \) のときにも①は成り立つ。
［1］，［2］から，\( n≧5 \) を満たすすべての自然数 \( n \) について①は成り立つ。
5. 数学的帰納法の漸化式の問題（入試問題）
さいごは，「漸化式から一般項を推測」→「数学的帰納法で証明する」問題です。
このパターンの問題はセンター試験でも頻出の重要な問題です！
数列 \( \left\{ a_n \right\} \) を，\( a_1 = 1 \)，\( \displaystyle a_{n+1} = \frac{a_n}{1 + 3a_n} （n = 1, 2, 3, \cdots）\) により定める。
(1) \( a_2, \ a_3, \ a_4 \) をそれぞれ求めよ。
(2) 一般項 \( a_n \) を推測し，その推測が正しいことを数学的帰納法によって証明せよ。
[2012 愛知大]
【解答】
(1) \( \displaystyle \color{red}{ a_2 } = \frac{a_1}{1 + 3a_1} = \frac{1}{1 + 3 \cdot 1} \color{red}{ = \frac{1}{4} } \)
\( \displaystyle \color{red}{ a_3 } = \frac{a_2}{1 + 3a_2} = \frac{\frac{1}{4}}{1 + 3 \cdot \frac{1}{4}} = \frac{1}{4 + 3} \color{red}{ = \frac{1}{7} } \)
\( \displaystyle \color{red}{ a_4 } = \frac{a_3}{1 + 3a_3} = \frac{\frac{1}{7}}{1 + 3 \cdot \frac{1}{7}} = \frac{1}{7 + 3} \color{red}{ = \frac{1}{10} } \)
(2) \( \displaystyle \left\{ a_n \right\}：\frac{1}{1}, \ \frac{1}{4}, \ \frac{1}{7}, \ \frac{1}{10}, \cdots \)
より，分子は1，分母が初項1，公差3の等差数列となっているので
\( \displaystyle a_n = \frac{1}{1 + 3(n-1)} = \frac{1}{3n – 2} \cdots ① \)
と推測できる。
［1］\( n = 1 \) のとき
\( \displaystyle a_1 = \frac{1}{3 \cdot 1 – 2} = 1 \) より，①は成り立つ。
［2］\( n = k \) のとき，①が成り立つと仮定すると
\( \displaystyle \color{magenta}{ a_k = \frac{1}{3k – 2} } \cdots ② \)
\( n = k+1 \) のときを考えると，②から
\( \begin{align}
\displaystyle \color{red}{ a_{k+1} } & = \frac{\color{magenta}{ a_k }}{1 + 3 \color{magenta}{ a_k }} \\
\\
& = \frac{\color{magenta}{ \frac{1}{3k – 2} }}{1 + 3 \cdot \color{magenta}{ \frac{1}{3k – 2} }} \\
\\
& = \frac{1}{(3k-2) + 3} \\
\\
& \color{red}{ = \frac{1}{3 (k+1) – 2} }
\end{align} \)
よって，\( n = k+1 \) のときにも①は成り立つ。
［1］，［2］から，すべての自然数 \( n \) について①は成り立つ。
6. さいごに
以上が数学的帰納法の解説です。
数学的帰納法は
［1］\( n = 1 \) のとき \( P \) が成り立つ。
［2］\( n = k \) のとき命題 \( P \) が成り立つと仮定すると，\( n = k+1 \) のときにも命題 \( P \) が成り立つ。
この流れをおさえてしまえば簡単です！
今回解説した問題はどれも入試で頻出の問題ですので，必ずマスターして数学的帰納法の問題を得点源しましょう！
例題3の >2］=（≧5） のとき，①が成り立つと仮定すると
^22⋅^2–(+1)^2=^2–2–1
の、>2⋅^2–(+1)^2はどのように導きだしましたか？
急に出てきた感じがしてわかりませんでした。
若輩者ですみませんが、ここの説明をお願い致します。
②より,k²<2 ᵏだからです。