- 目次
- 理解
- 事例
- まとめ
【理解】数学的帰納法とは
「数学的帰納法」とは
自然数に関する命題が、すべての自然数について成り立つことを証明するための手法のこと。
数学的帰納法について
数学的帰納法
すべての自然数 $n$ に対して, 命題 $P(n)$ が真であることを証明する方法。
詳細はこちら
自然数 $n$ に関する命題を $P(n)$ とする。次の2つの条件が満たされるとき, すべての自然数 $n$ について $P(n)$ は真である。
$P(1)$ が真である。
ある自然数 $k$ に対して「$P(k)$ が真である」と仮定すると, 「$P(k+1)$ も真である」ことが導かれる。
極限について
数学的帰納法は $\displaystyle \lim_{n \to \infty}P(n)$ での真偽は証明できない。
詳細はこちら
数学的帰納法は全ての $n$ で $P(n)$ が真であることを示すが, 極限での真偽は言及できない.
(例) $\frac{n+1}{n} > 1$ は任意の自然数 $n$ で真だが, $n \to \infty$ では偽である.
帰納法のパラドックスについて
禿げ頭のパラドックス
何本毛が生えていてもハゲである。
詳細はこちら
髪の毛が1本もない頭はハゲである。
ハゲ頭に一本毛が増えてもハゲである。
ゆえに、何本毛が生えていてもハゲである。
砂山のパラドックス
大量の砂は砂山である。
詳細はこちら
砂山から1粒取り除いても砂山である。
ゆえに、どれだけ砂を取り除いても砂山である。
【事例】数学的帰納法の例題集
数学的帰納法で証明できることの例題を集めました。自分でも証明してみましょう！
数列の和に関する帰納的証明について
<帰納法>Σ公式①
$\displaystyle \sum_{k=1}^n k= \frac{1}{2}n(n+1)$
証明はこちら
$1$ から $n$ までの自然数の総和は, 次の式で表される。 $$ \sum_{k=1}^n k= \frac{1}{2}n(n+1) $$
すべての自然数 $n$ について, 次の等式が成り立つことを証明する。 $$ \sum_{k=1}^n k = \frac{1}{2}n(n+1) \quad \cdots (\text{＊}) $$
左辺は $1$, 右辺は $\frac{1}{2}\cdot 1 \cdot (1+1) = 1$ である。
ゆえに, $n=1$ のとき等式(＊)は成り立つ。
$n=\ell \geqq 1$ のとき, 等式(＊)が成り立つと仮定する。すなわち, $$ \sum_{k=1}^{\ell} k = \frac{1}{2}\ell(\ell+1) $$ が成り立つと仮定する。
$n=\ell+1$ のとき, (＊)の左辺を計算すると： $$ \begin{aligned} \sum_{k=1}^{\ell+1} k &= (1 + 2 + \cdots + \ell) + (\ell + 1) \\ &= \frac{1}{2}\ell(\ell+1) + (\ell+1) \\ &= \frac{1}{2}(\ell+1)(\ell + 2) \\ &= \frac{1}{2}(\ell+1)\{(\ell+1)+1\} \end{aligned} $$ となり, $n=\ell+1$ のときの(＊)の右辺に一致する。
$n=\ell$ のときに等式(＊)が成り立つと仮定すると $n=\ell+1$ のときも成り立つことが示された。
ゆえに, 数学的帰納法により, すべての自然数 $n$ について
$$ \sum_{k=1}^n k = \frac{1}{2}n(n+1) $$
は成り立つ。
<帰納法>Σ公式⓶
$\displaystyle \sum_{k=1}^n k^2= \frac{1}{6}n(n+1)(2n+1)$
証明はこちら
$1$ から $n$ までの自然数の2乗の和は, 次の式で表される。 $$ \sum_{k=1}^n k^2 = \frac{1}{6}n(n+1)(2n+1) $$
任意の自然数 $n$ について, 次の等式が成り立つことを証明する。 $$ \sum_{k=1}^n k^2 = \frac{1}{6}n(n+1)(2n+1) \quad \cdots (\text{＊}) $$
左辺は $1^2=1$, 右辺は $\frac{1}{6}\cdot 1 \cdot (1+1)(2\cdot 1 + 1) = 1$ である。
ゆえに, $n=1$ のとき等式(＊)は成り立つ。
$n=\ell \geqq 1$ のとき, 等式(＊)が成り立つと仮定する。すなわち, $$ \sum_{k=1}^{\ell} k^2 = \frac{1}{6}\ell(\ell+1)(2\ell+1) $$ が成り立つと仮定する。
$n=\ell+1$ のとき, (＊)の左辺を計算する： $$ \begin{aligned} \sum_{k=1}^{\ell+1} k^2 &= 1^2 + \cdots + \ell^2 + (\ell + 1)^2 \\ &= \frac{1}{6} \ell (\ell + 1)(2\ell + 1) + (\ell + 1)^2 \\ &= \frac{\ell+1}{6} \{ \ell(2\ell+1) + 6(\ell+1) \} \\ &= \frac{\ell+1}{6} ( 2\ell^2 + 7\ell + 6 ) \\ &= \frac{\ell+1}{6} (\ell+2)(2\ell+3) \\ &= \frac{1}{6} (\ell+1)(\ell+2) \{ 2(\ell+1)+1 \} \end{aligned} $$ この式は $n=\ell + 1$ のときの等式(＊)の右辺に一致する。
$n=\ell$ のとき等式(＊)が成り立つと仮定すると, $n=\ell+1$ のときも成り立つことが示された。
数学的帰納法により, すべての自然数 $n$ について
$$ \sum_{k=1}^n k^2 = \frac{1}{6}n(n+1)(2n+1) $$
は正しい。
<帰納法>Σ公式③
$\displaystyle \sum_{k=1}^n k^3= \left\{\frac{1}{2}n(n+1)\right\}^2$
証明はこちら
$1$ から $n$ までの自然数の3乗の和は, 次の式で表される。 $$ \sum_{k=1}^n k^3 = \left\{ \frac{1}{2}n(n+1) \right\}^2 $$
自然数 $n$ に関する次の式を証明する。 $$ \sum_{k=1}^n k^3 = \left\{ \frac{1}{2}n(n+1) \right\}^2 $$ この式を(＊)とする。
左辺は $1^3=1$, 右辺は $\left\{ \frac{1}{2}\cdot 1 \cdot (1+1) \right\}^2=1$ である。
ゆえに, $n=1$ のとき等式(＊)は成り立つ。
$n=\ell \geqq 1$ のとき, 等式(＊)が成り立つと仮定する。すなわち, $$ \sum_{k=1}^{\ell} k^3 = \left\{ \frac{1}{2}\ell(\ell+1) \right\}^2 $$ と仮定する。
$n=\ell+1$ のとき, (＊)の左辺を計算する： $$ \begin{aligned} &\sum_{k=1}^{\ell+1} k^3 \\ &= 1^3 + \cdots + \ell^3 + (\ell + 1)^3 \\ &= \left\{ \frac{1}{2}\ell(\ell+1) \right\}^2 + (\ell+1)^3 \\ &= \frac{1}{4}(\ell+1)^2 \left\{ \ell^2 + 4(\ell+1) \right\} \\ &= \frac{1}{4}(\ell+1)^2 (\ell^2 + 4\ell + 4) \\ &= \frac{1}{4}(\ell+1)^2 (\ell+2)^2 \\ &= \left\{ \frac{1}{2}(\ell+1)((\ell+1)+1) \right\}^2 \end{aligned} $$ この式は $n=\ell + 1$ のときの等式(＊)の右辺に一致する。
$n=\ell$ のときに等式(＊)が成り立つと仮定すると $n=\ell+1$ のときも成り立つことが示された。
ゆえに, 数学的帰納法により, すべての自然数 $n$ について
$$ \sum_{k=1}^n k^3=\left\{ \frac{1}{2}n(n+1) \right\}^2 $$
が成り立つ。
<帰納法>Σ公式④
$\displaystyle \sum_{k=1}^n ar^{k-1} = \frac{a(r^n-1)}{r-1}$
証明はこちら
初項 $a$, 公比 $r$ ($r \neq 1$), 項数 $n$ の等比数列の和は, 次の式で表される。 $$ \sum_{k=1}^n ar^{k-1} = \frac{a(r^n - 1)}{r - 1} $$
$r \neq 1$ とするとき, すべての自然数 $n$ について次の等式(＊)が成り立つことを証明する。 $$ \sum_{k=1}^n ar^{k-1} = \frac{a(r^n-1)}{r-1}$$
左辺は $ar^{1-1} = a$ である。
右辺は $\frac{a(r^1-1)}{r-1} = a$ である。
ゆえに, $n=1$ のとき等式(＊)は成り立つ。
$n=\ell$ のとき, 等式(＊)が成り立つと仮定する。すなわち, $$ \sum_{k=1}^\ell ar^{k-1} = \frac{a(r^\ell-1)}{r-1} $$ が成り立つとする。
$n=\ell+1$ のときの左辺を計算し, 仮定の式を代入して整理する。 $$ \begin{aligned} &\sum_{k=1}^{\ell+1} ar^{k-1} \\ &= \left( \sum_{k=1}^\ell ar^{k-1} \right) + ar^\ell \\[8pt] &= \frac{a(r^\ell-1)}{r-1} + ar^\ell \\ &= \frac{a(r^\ell-1) + ar^\ell(r-1)}{r-1} \\[8pt] &= \frac{a \{ r^\ell - 1 + r \cdot r^\ell - r^\ell \}}{r-1} \\[8pt] &= \frac{a(r^{\ell+1}-1)}{r-1} \end{aligned} $$ となり, $n=\ell+1$ のときも等式(＊)は成り立つ。
以上より, 数学的帰納法によって, すべての自然数 $n$ について $$ \sum_{k=1}^n ar^{k-1} = \frac{a(r^n-1)}{r-1} $$ が成り立つ。
フィボナッチ数列に関する帰納的証明について
<帰納法>フィボナッチ数列の一般項
$\displaystyle F_n = \frac{\phi^n - (-\phi^{-1})^n}{\sqrt{5}}$
証明はこちら
フィボナッチ数列 $\{F_n\}$ （ただし $F_1=F_2=1$）の一般項は, 次の式で表される。 $$ F_n = \frac{1}{\sqrt{5}} \left\{ \left(\frac{1+\sqrt{5}}{2} \right)^n - \left(\frac{1-\sqrt{5}}{2} \right)^n \right\} $$
フィボナッチ数列の一般項が次の式で表されることを, 数学的帰納法を用いて証明する。 $$ F_n = \frac{1}{\sqrt{5}} ( \alpha^n - \beta^n ) \quad \cdots (\text{＊}) $$ ただし, $\alpha = \frac{1+\sqrt{5}}{2}, \beta = \frac{1-\sqrt{5}}{2}$ とする。これらは $x^2 - x - 1 = 0$ の解であり, $\alpha^2 = \alpha+1, \beta^2 = \beta+1$ を満たす。
$n=1$ のとき：右辺 $= \frac{1}{\sqrt{5}}(\alpha - \beta) = \frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2} - \frac{1-\sqrt{5}}{2} \right) = 1 = F_1$
$n=2$ のとき：右辺 $= \frac{1}{\sqrt{5}}(\alpha^2 - \beta^2) = \frac{1}{\sqrt{5}}\{(\alpha+1) - (\beta+1)\} = \frac{\alpha-\beta}{\sqrt{5}} = 1 = F_2$
よって, $n=1, 2$ のとき等式(＊)は成り立つ。
$n \leqq k$ ($k \geqq 2$) のすべての自然数 $n$ について等式(＊)が成り立つと仮定する。 このとき, $n=k$ および $n=k-1$ において $$ F_k = \frac{1}{\sqrt{5}}(\alpha^k - \beta^k), \quad F_{k-1} = \frac{1}{\sqrt{5}}(\alpha^{k-1} - \beta^{k-1}) $$ が成り立つ。
漸化式 $F_{k+1} = F_k + F_{k-1}$ より $$ \begin{aligned} F_{k+1} &= \frac{1}{\sqrt{5}}(\alpha^k - \beta^k) + \frac{1}{\sqrt{5}}(\alpha^{k-1} - \beta^{k-1}) \\ &= \frac{1}{\sqrt{5}} \{ (\alpha^k + \alpha^{k-1}) - (\beta^k + \beta^{k-1}) \} \\ &= \frac{1}{\sqrt{5}} \{ \alpha^{k-1}(\alpha + 1) - \beta^{k-1}(\beta + 1) \} \\ &= \frac{1}{\sqrt{5}} \{ \alpha^{k-1} \cdot \alpha^2 - \beta^{k-1} \cdot \beta^2 \} \\ &= \frac{1}{\sqrt{5}} ( \alpha^{k+1} - \beta^{k+1} ) \end{aligned} $$ となり, $n=k+1$ のときも等式(＊)は成り立つ。
ゆえに, 数学的帰納法によってすべての自然数 $n$ について $$ F_n = \frac{1}{\sqrt{5}} \left\{ \left(\frac{1+\sqrt{5}}{2} \right)^n - \left(\frac{1-\sqrt{5}}{2} \right)^n \right\} $$ が成り立つ。
e.g. 証明のポイント
$\alpha = \frac{1 + \sqrt{5}}{2}$ は $\alpha^2 = \alpha+1$ を満たす。
$\beta = \frac{1 - \sqrt{5}}{2}$ も $\beta^2 = \beta + 1$ を満たす。
$n=5$ のときの式を, $n=4, 3$ のときの式から作ります。
$F_{5} = F_4 + F_3$
① $F_4=\frac{1}{\sqrt{5}}(\alpha^4- \beta^4)$
② $F_3=\frac{1}{\sqrt{5}}(\alpha^3- \beta^3)$
①+②をします。
$\alpha$ のところは,
$\frac{1}{\sqrt{5}} (\alpha^4 + \alpha^3)$ $= \frac{1}{\sqrt{5}} (\alpha + 1)\alpha^3$ $= \frac{1}{\sqrt{5}} \alpha^2 \cdot \alpha^3$ $= \frac{1}{\sqrt{5}} \alpha^5$
になる。
同様に, $\beta$ のところも,
$-\frac{1}{\sqrt{5}} \beta^5$
になる。
だから,
$F_5 = \frac{1}{\sqrt{5}}(\alpha^5- \beta^5)$
ができる。
<帰納法>フィボナッチ数列の和
$F_1 + \ldots+F_n=F_{n+2}-1$
証明はこちら
フィボナッチ数列 $\{F_n\}$ に対して, 任意の正の整数 $n$ について次が成り立つ。 $$ F_1 + \cdots + F_n = F_{n+2} - 1 $$
数学的帰納法によって示す。
$n=1$ のとき, 左辺は $F_1 = 1$ である。 右辺は $F_3 - 1 = 2 - 1 = 1$ である。
ゆえに, $n=1$ のとき, 示すべき等式は成り立つ。
$n = k \in \mathbb{N}$ のとき, $$ F_1 + \ldots + F_k = F_{k+2} - 1 $$ が成り立つと仮定する。
$n = k+1$ のときについて考える。
$$ \begin{aligned} F_{n+2} - 1 &= F_{(k+1)+2} - 1 \\ &= F_{k+3} - 1 \\ &= F_{k+2} + F_{k+1} - 1 \\ &= F_{k+1} + (F_{k+2} - 1) \\ &= F_{k+1} + (F_k + \ldots + F_1) \\ &= F_{k+1} + \ldots + F_1 \end{aligned} $$
したがって, $n = k+1$ のときも, $$ F_1 + \ldots + F_n = F_{n+2} - 1 $$ が成り立つ。
以上から, 数学的帰納法によって, 任意の自然数 $n$ について $$ F_1 + \ldots + F_n = F_{n+2} - 1 $$ が成り立つ。
① $F_1 + F_2 + F_3$
② $F_5 - 1$
が同じ値になる理由を観察する。 まず, $F_5$ を分解すると $$ \begin{aligned} F_5 &= F_3 + F_4 \\ &= F_3 + (F_2 + F_3) \\ &= F_3 + F_2 + (F_1 + F_2) \\ &= F_3 + F_2 + F_1 + 1 \end{aligned} $$ よって,
①' $F_5$
②' $F_3 + F_2 + F_1 + 1$
から, それぞれ $1$ を引けば, ① $F_1 + F_2 + F_3$ と ② $F_5 - 1$ が得られる。
したがって, $n=3$ のとき, $$ F_1 + F_2 + F_3 = F_5 - 1 $$ が確かに成り立つことが分かる。
<帰納法>平方の和
$F_1^2 + \ldots+F_{n}^2=F_nF_{n+1}$
証明はこちら
フィボナッチ数列 $\{F_n\}$ に対して， 任意の自然数 $n$ について, $$ F_1^2 + F_2^2 + \cdots + F_n^2 = F_n F_{n+1} $$ が成り立つ。
フィボナッチ数列 $\{F_n\}$ を $F_1 =F_2= 1$ かつ $$F_{n+2}=F_{n+1}+F_n$$ によって定める。 これに対し, $$F_1^2+\cdots+F_n^2 = F_nF_{n+1}$$ が成り立つことを数学的帰納法によって示す。
$n=1$ のとき, 左辺は $F_1^2 = 1$ である。一方, 右辺は $$F_1F_2 = 1\cdot 1 = 1$$ である。よって, $n=1$ のとき, 示すべき等式は成り立つ。
$n=k \in \mathbb{N}$ のとき, $$F_1^2+\cdots+F_k^2 = F_kF_{k+1}$$ が成り立つと仮定する。
$n=k+1$ のときについて考える。 フィボナッチ数列の定義より $$F_{k+2}=F_{k+1}+F_k$$ が成り立つから,
$$\begin{aligned} F_{k+1}F_{k+2} &= F_{k+1}(F_{k+1}+F_k) \\ &= F_{k+1}^2 + F_kF_{k+1} \\ &= F_{k+1}^2 + (F_k^2+\cdots+F_1^2) \\ &= F_{k+1}^2+\cdots+F_1^2 \end{aligned}$$
よって, $n=k+1$ のときも, 示すべき等式は成り立つ。
以上より, 数学的帰納法によって, 任意の自然数 $n$ について $$F_1^2+\cdots+F_n^2 = F_nF_{n+1}$$ が成り立つ。
① $F_1^2 + F_2^2 + F_3^2$
② $F_3 F_4$
が等しくなる理由を観察します。
②について考えると， $$ F_3 F_4 = F_3 (F_3 + F_2) = F_3^2 + F_2 F_3 $$ です。
ここで， $$ F_2 F_3 = F_2 (F_2 + F_1) = F_2^2 + F_2 F_1 $$ となります。
さらに，$F_2 = F_1$ であるから， $F_2 F_1 = F_1^2$ です。
以上より， $$ F_3 F_4 = F_3^2 + F_2^2 + F_1^2 $$ となり，①と②は等しいことが分かります。
<帰納法>奇数番目の和
$F_1 + \ldots+F_{2n-1}=F_{2n}$
証明はこちら
フィボナッチ数列 $\{F_n\}$ （ただし $F_1=F_2=1$）について, 次が成り立つ。 $$ \sum_{k=1}^n F_{2k-1} = F_{2n} $$
任意の自然数 $n$ について, 次の等式(＊)が成り立つことを数学的帰納法で証明する。 $$ F_1 + F_3 + \cdots + F_{2n-1} = F_{2n}$$
左辺は $F_1 = 1$, 右辺は $F_{2 \cdot 1} = F_2 = 1$ である。
ゆえに, $n=1$ のとき等式(＊)は成り立つ。
$n=k$ のとき, 等式(＊)が成り立つと仮定する。すなわち, $$ F_1 + F_3 + \cdots + F_{2k-1} = F_{2k} $$ が成り立つと仮定する。
$n=k+1$ のとき, (＊)の左辺の和を計算すると：
$$
\begin{aligned}
&(F_1 + \cdots + F_{2k-1}) + F_{2k+1} \\
&= F_{2k} + F_{2k+1}\\
&= F_{2k+2} \\
&= F_{2(k+1)}
\end{aligned}
$$
となり, $n=k+1$ のときの右辺に一致する。
※ ここでフィボナッチ数列の定義 $F_{2k+2} = F_{2k+1} + F_{2k}$ を用いた。
よって, $n=k$ のとき等式が成り立つと仮定すると, $n=k+1$ のときも成り立つことが示された。
数学的帰納法により, すべての自然数 $n$ について
$$ F_1 + F_3 + \cdots + F_{2n-1} = F_{2n} $$
は成り立つ。
$F_1$ は $F_2$ と等しく, $F_3$ は $F_4 - F_2$ と等しく, $F_5$ は $F_6- F_4$ と等しいです。 これらの和は $F_6$ になり, ②と一致します。
<帰納法>偶数番目の和
$F_2 + \ldots+F_{2n}=F_{2n+1}-1$
証明はこちら
フィボナッチ数列 $\{F_n\}$ (ただし $F_1=F_2=1$) について, 次が成り立つ。 $$\sum_{k=1}^n F_{2k} = F_{2n+1} - 1$$
すべての自然数 $n$ について, 次の等式(＊)が成り立つことを数学的帰納法で証明する。 $$ F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1$$
左辺は $F_2 = 1$ である。
右辺は $F_{2 \cdot 1 + 1} - 1 = F_3 - 1 = 2 - 1 = 1$ である。
ゆえに, $n=1$ のとき等式(＊)は成り立つ。
$n=k$ のとき, 等式(＊)が成り立つと仮定する。すなわち, $$ F_2 + F_4 + \cdots + F_{2k} = F_{2k+1} - 1 $$ が成り立つとする。
$n=k+1$ のとき, 左辺の和を計算すると次のようになる。 $$ \begin{aligned} &(F_2 + F_4 + \cdots + F_{2k}) + F_{2k+2} \\[5pt] &= (F_{2k+1} - 1) + F_{2k+2} \\[5pt] &= (F_{2k+2} + F_{2k+1}) - 1 \\[5pt] &= F_{2k+3} - 1 \\[5pt] &= F_{2(k+1)+1} - 1 \end{aligned} $$ となり, $n=k+1$ のときも等式(＊)は成り立つ。
以上より, 数学的帰納法によって, すべての自然数 $n$ について $$ F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1 $$ が成り立つ。
①について $F_2 = F_3 - F_1$, $F_4 = F_5 - F_3$, $F_6 = F_7- F_5$ と変形して和をとると, $F_7 -F_1$ となる。 $F_1=1$ だから, ①と②は同じ値と分かる。
整数の性質の帰納的証明について
<帰納法>倍数命題の証明
$5^n-1$ が $4$ の倍数である
証明はこちら
すべての自然数 $n$ について, $5^n - 1$ は $4$ の倍数である。
証明のポイント
$5^{n+1}-1= 5(5^n-1) +4$ なので, $5^n-1$ が $4$ の倍数ならば, $5^{n+1}-1$ のときも $4$ の倍数になります。
すべての自然数 $n$ について, 「$5^n-1$ は $4$ の倍数である」という命題を $P(n)$ とする。
$5^1 - 1 = 4$ となり, これは $4$ の倍数である。
よって, $n=1$ のとき命題 $P(1)$ は真である。
$n=\ell$ のとき $P(\ell)$ が真であると仮定する。すなわち, ある整数 $k$ を用いて次のように表せる。 $$ 5^\ell - 1 = 4k $$
$n=\ell+1$ のとき, $5^{\ell+1}-1$ を計算して仮定を代入する。
$$
\begin{aligned}
5^{\ell+1} - 1 &= 5 \cdot 5^\ell - 1 \\[5pt]
&= 5(4k + 1) - 1 \\[5pt]
&= 20k + 5 - 1 \\[5pt]
&= 20k + 4 \\[5pt]
&= 4(5k + 1)
\end{aligned}
$$
$5k+1$ は整数であるから, $4(5k+1)$ は $4$ の倍数である。
したがって, $n=\ell+1$ のときも命題 $P(\ell+1)$ は真である。
ゆえに, 数学的帰納法によって, すべての自然数 $n$ について $5^n-1$ は $4$ の倍数である。
不等式の帰納的証明について
<帰納法>不等式の証明①
$n \geqq 2$ ならば $3^n > 4n$
証明はこちら
$2$ 以上のすべての自然数 $n$ について, $3^n > 4n$ が成り立つ。
$n \geqq 2$ の自然数について, 不等式 $3^n > 4n \cdots (\text{＊})$ が成り立つことを数学的帰納法で証明する。
(左辺) $= 3^2 = 9$
(右辺) $= 4 \cdot 2 = 8$
$9 > 8$ より, $n=2$ のとき(＊)は成り立つ。
$n=k$ ($k \geqq 2$) のとき, (＊)が成り立つと仮定する。すなわち, $$ 3^k > 4k $$ が成り立つと仮定する。
$n=k+1$ のとき, (左辺) $-$ (右辺) の差を計算する。 $$ \begin{aligned} & 3^{k+1} - 4(k+1) \\ &= 3 \cdot 3^k - 4(k+1) \\[5pt] &> 3 \cdot 4k - 4(k+1) \\[5pt] &= 12k - 4k - 4 \\[5pt] &= 8k - 4 \\[5pt] &= 4(2k - 1) \end{aligned} $$ ここで $k \geqq 2$ より, $2k - 1 > 0$ であるから, $$ 4(2k - 1) > 0 $$ が成り立つ。よって, $n=k+1$ のときも(＊)は成り立つ。
ゆえに, 数学的帰納法によって, $n \geqq 2$ のすべての自然数について $$ 3^n > 4n $$ が成り立つ。
<帰納法>不等式の証明②
$n \geqq 4$ ならば $2^n > n^2 - n+2$
証明はこちら
$4$ 以上のすべての自然数 $n$ について, 次の不等式が成り立つ。 $$ 2^n > n^2 - n + 2 $$
$n \geqq 4$ の自然数について, 不等式 $2^n > n^2 - n + 2 \cdots (\text{＊})$ が成り立つことを数学的帰納法で証明する。
(左辺) $= 2^4 = 16$
(右辺) $= 4^2 - 4 + 2 = 14$
$16 > 14$ より, $n=4$ のとき(＊)は成り立つ。
$n=k$ ($k \geqq 4$) のとき, (＊)が成り立つと仮定する。すなわち, $$ 2^k > k^2 - k + 2 $$ が成り立つと仮定する。
$n=k+1$ のとき, (左辺) $-$ (右辺) の差を計算する。 $$ \begin{aligned} &2^{k+1} - \{ (k+1)^2 - (k+1) + 2 \} \\[5pt] &= 2 \cdot 2^k - (k^2 + k + 2) \\[5pt] &> 2(k^2 - k + 2) - (k^2 + k + 2) \\[5pt] &= 2k^2 - 2k + 4 - k^2 - k - 2 \\[5pt] &= k^2 - 3k + 2 \\[5pt] &= (k-1)(k-2) \end{aligned} $$ ここで $k \geqq 4$ より, $k-1 > 0$ かつ $k-2 > 0$ であるから, $$ (k-1)(k-2) > 0 $$ が成り立つ。よって, $n=k+1$ のときも(＊)は成り立つ。
以上より, 数学的帰納法によって, $n \geqq 4$ のすべての自然数について $$ 2^n > n^2 - n + 2 $$ が成り立つ。
対称式 $a^n+b^n$ の変形を使う証明について
<公式>対称式の漸化式
$a^n+b^n$ $= (a+b)(a^{n-1}+b^{n-1})$ $- ab(a^{n-2}+b^{n-2})$
証明はこちら
任意の数 $a, b$ および自然数 $n$ について, 次の等式が成り立つ。 $$ a^{n+2} + b^{n+2} = (a+b)(a^{n+1}+b^{n+1}) - ab(a^n + b^n) $$
右辺を展開して整理し, 左辺 $a^{n+2} + b^{n+2}$ を導く。
まず, 右辺の第1項を展開すると次のようになる。 $$ \begin{aligned} &(a+b)(a^{n+1} + b^{n+1}) \\ & \quad= a \cdot a^{n+1} + a \cdot b^{n+1} + b \cdot a^{n+1} + b \cdot b^{n+1} \\[5pt] & \quad = a^{n+2} + ab^{n+1} + ba^{n+1} + b^{n+2} \end{aligned} $$ 次に, 右辺の第2項を展開すると次のようになる。 $$ -ab(a^n + b^n) = -ba^{n+1} - ab^{n+1} $$
これらを足し合わせると, $ab^{n+1}$ と $ba^{n+1}$ の項が相殺される。 $$ \begin{aligned} &\phantom{=} (a^{n+2} + \underline{ab^{n+1} + ba^{n+1}} + b^{n+2}) + (\underline{-ba^{n+1} - ab^{n+1}}) \\[8pt] &= a^{n+2} + b^{n+2} \end{aligned} $$
計算の結果, 右辺と左辺が一致したため, 次の等式が成り立つ。 $$ a^{n+2} + b^{n+2} = (a+b)(a^{n+1} + b^{n+1}) - ab(a^n + b^n) $$
基本対称式の漸化式を使う問題
<帰納法>証明例①
$\displaystyle \frac{a^n+b^n}{2} \geqq \left(\frac{a+b}{2}\right)^n$
証明はこちら
$a>0, b>0$ とするとき, 任意の自然数 $n$ について次の不等式が成り立つ。 $$ \frac{a^n + b^n}{2} \geqq \left( \frac{a+b}{2} \right)^n $$ 等号成立は, $a=b$ のときである. ただし, $n=1$ のときは任意の $a$ と $b$ について, 等号が成立する.
$A(n) = \frac{a^n+b^n}{2}$, $B(n) = \left(\frac{a+b}{2}\right)^n$ とおき, すべての自然数 $n$ について $A(n) \geqq B(n) \cdots (\text{＊})$ が成り立つことを証明する。
$A(1) = \frac{a+b}{2}$, $B(1) = \frac{a+b}{2}$ より, $A(1) = B(1)$ となり(＊)は成り立つ。
$n=k$ のとき(＊)が成り立つ, すなわち $A(k) \geqq B(k)$ と仮定する。
$f(k+1) = A(k+1) - B(k+1)$ の正負を調べる。ここで $A(k+1)$ に関する隣接3項間の関係式を利用すると： $$ \begin{aligned} &f(k+1) \\ &= \underbrace{(a+b)A(k) - abA(k-1)}_{A(k+1)} \\ & \phantom{aaaa} - B(k+1) \\[8pt] &= \frac{a+b}{2}A(k) - abA(k-1) \\ &\phantom{aaaa} + \frac{a+b}{2}A(k) - \frac{a+b}{2}B(k)\\ & \phantom{aaaaaa} (\because B(k+1) = \frac{a+b}{2}B(k)) \\[8pt] &= \left\{ \frac{a+b}{2}A(k) - abA(k-1) \right\} \\ & \phantom{aaaa} + \frac{a+b}{2}(A(k) - B(k)) \end{aligned} $$ 第1中括弧の中身を計算すると： $$ \begin{aligned} &\frac{a+b}{2} \cdot \frac{a^k+b^k}{2} - ab \cdot \frac{a^{k-1}+b^{k-1}}{2} \\ & \quad = \frac{(a-b)(a^k-b^k)}{4} \end{aligned} $$ となる。よって, $$\begin{aligned} &f(k+1) \\ & \quad = \frac{(a-b)(a^k-b^k)}{4} \\ & \quad + \frac{a+b}{2}(A(k) - B(k)) \end{aligned}$$
1. $(a-b)$ と $(a^k-b^k)$ は常に同符号（または一方が0）であるから, 第1項 $\geqq 0$。
2. 帰納法の仮定より $A(k)-B(k) \geqq 0$ であるから, 第2項 $\geqq 0$。
したがって $f(k+1) \geqq 0$ が示され, $n=k+1$ のときも(＊)は成り立つ。
等号成立は, $n \geqq 2$ においては $a=b$ のときに限られる。
以上より, 数学的帰納法によりすべての自然数 $n$ について $$ \frac{a^n+b^n}{2} \geqq \left(\frac{a+b}{2} \right)^n $$ が成り立つ。
<帰納法>証明例②
$(1+\sqrt{x})^n+(1-\sqrt{x})^n \in \mathbb{N}$
証明はこちら
$x$ を自然数とするとき, すべての自然数 $n$ について $$ (1+\sqrt{x})^n + (1-\sqrt{x})^n $$ は自然数となる。
$A_x(n) = (1+\sqrt{x})^n + (1-\sqrt{x})^n$ とおき, これがすべての自然数 $n$ について自然数であることを証明する。
$n=1$ のとき：
$A_x(1) = (1+\sqrt{x}) + (1-\sqrt{x}) = 2$ （自然数）
$n=2$ のとき：
$A_x(2) = (1+2\sqrt{x}+x) + (1-2\sqrt{x}+x) = 2(1+x)$ （自然数）
よって, $n=1, 2$ のとき主張は正しい。
$n=1, 2, \dots, k$ ($k \geqq 2$) のとき, $A_x(n)$ がすべて自然数であると仮定する。
$a = 1+\sqrt{x}$, $b = 1-\sqrt{x}$ とおくと, $a+b=2$, $ab=1-x$ である。
これより, $A_x(n)$ は次の漸化式を満たす：
$$
\begin{aligned}
&A_x(k+1) \\
& \quad = (a+b)A_x(k) - abA_x(k-1) \\[5pt]
& \quad = 2A_x(k) - (1-x)A_x(k-1) \\[5pt]
& \quad = 2A_x(k) + (x-1)A_x(k-1) \quad \cdots (\ast)
\end{aligned}
$$
帰納法の仮定より $A_x(k), A_x(k-1)$ は自然数であり, $x$ は自然数なので $x-1$ は $0$ 以上の整数である。
したがって, $(\ast)$ より $A_x(k+1)$ も自然数となる。
以上より, 数学的帰納法によって, すべての自然数 $n$ について $(1+\sqrt{x})^n + (1-\sqrt{x})^n$ は自然数である。
様々な証明について
<帰納法>証明例①
$(p + \sqrt{q})^n=a_n + b_n\sqrt{q}$ $\Leftrightarrow (p - \sqrt{q})^n=a_n - b_n\sqrt{q}$
証明はこちら
$p$ と $q$ を正の定数とし, $n$ を自然数とする。 $$ (p+\sqrt{q})^n = a_n + b_n \sqrt{q} $$ と表されるとき（ただし $a_n, b_n$ は有理数）, 次の等式が成り立つ。 $$ (p-\sqrt{q})^n = a_n - b_n \sqrt{q} $$
任意の自然数 $n$ について, $(p+\sqrt{q})^n = a_n + b_n \sqrt{q}$ ならば $(p-\sqrt{q})^n = a_n - b_n \sqrt{q}$ であることを証明する。
$(p+\sqrt{q})^1 = p + 1 \cdot \sqrt{q}$ より, $a_1 = p, b_1 = 1$ である。
一方で $(p-\sqrt{q})^1 = p - 1 \cdot \sqrt{q}$ となり, 係数が一致するため $n=1$ のとき主張は成り立つ。
$n=k$ のとき主張が成り立つと仮定する。すなわち, $ (p+\sqrt{q})^k = a_k + b_k \sqrt{q}$ ならば $(p-\sqrt{q})^k = a_k - b_k \sqrt{q}$ が成り立つと仮定する。
まず, $(p+\sqrt{q})^{k+1}$ を展開して $a_{k+1}, b_{k+1}$ を求める。 $$ \begin{aligned} &(p+\sqrt{q})^{k+1} \\ &\quad = (p+\sqrt{q})(a_k + b_k \sqrt{q}) \\[5pt] &\quad = pa_k + pb_k\sqrt{q} + a_k\sqrt{q} + qb_k \\[5pt] &\quad = (pa_k + qb_k) + (a_k + pb_k)\sqrt{q} \end{aligned} $$ よって, $a_{k+1} = pa_k + qb_k$, $b_{k+1} = a_k + pb_k$ である。
次に, $(p-\sqrt{q})^{k+1}$ を展開する。 $$ \begin{aligned} &(p-\sqrt{q})^{k+1} \\ &\quad = (p-\sqrt{q})(a_k - b_k \sqrt{q}) \\[5pt] &\quad = pa_k - pb_k\sqrt{q} - a_k\sqrt{q} + qb_k \\[5pt] &\quad = (pa_k + qb_k) - (a_k + pb_k)\sqrt{q} \\[5pt] &\quad = a_{k+1} - b_{k+1}\sqrt{q} \end{aligned} $$ となり, $n=k+1$ のときも主張は成り立つ。
以上より, 数学的帰納法によってすべての自然数 $n$ について主張が成り立つ。
$n=1$ のとき $1+\sqrt{2}$,
$n=2$ のとき $3 + 2\sqrt{2}$,
$n=3$ のとき $7+5\sqrt{2}$
です。一方で, $(1-\sqrt{2})^n$ について,
$n=1$ のとき $1-\sqrt{2}$,
$n=2$ のとき $3 - 2\sqrt{2}$,
$n=3$ のとき $7-5\sqrt{2}$
です。どちらも正負以外は一致しており,
$a_1=1$, $b_1=1$, $a_2=3$, $b_2=2$, $a_3=7$, $b_3=5$ となっています。
<帰納法>証明例②
$1$, $2$, $2^2$, $\cdots$, $2^{n-1}$ を使って $1$ から $2^{n}-1$ までの自然数をすべて作れること
証明はこちら
任意の自然数 $n$ について, $1$ から $2^{n}-1$ までのすべての自然数は, $$ 1, 2, 2^2, \cdots, 2^{n-1} $$ の中から重複を許さずいくつか選んだ数の和で一意的に表せる。
$A_n = \{1, 2, 2^2, \cdots, 2^{n-1}\}$ とおく。集合 $A_n$ の要素をいくつか選んだ和として, $1$ から $2^n-1$ までの自然数が表せることを数学的帰納法で示す。
$2^1 - 1 = 1$ である。$A_1 = \{1\}$ より, 要素 $1$ を選ぶことで $1$ を表すことができ, 主張は成り立つ。
$1 \leqq k \leqq 2^n - 1$ を満たすすべての自然数 $k$ が, $A_n$ の要素の和で表せると仮定する。
$1$ から $2^{n+1}-1$ までの数を, 以下の3つの範囲に分けて考える。
- (i) $1 \leqq k \leqq 2^n - 1$ のとき：
帰納法の仮定より, $A_n$（すなわち $A_{n+1}$ の部分集合）の要素の和で表せる。 - (ii) $k = 2^n$ のとき：
$2^n \in A_{n+1}$ であるため, 単独の要素として表せる。 - (iii) $2^n + 1 \leqq k \leqq 2^{n+1} - 1$ のとき：
この範囲の数は $2^n + m$ （ただし $1 \leqq m \leqq 2^n - 1$）と書ける。仮定より $m$ は $A_n$ の要素の和で表せ, かつ $2^n \notin A_n$ であるため, 重複なく $A_{n+1}$ の要素の和として表せる。
よって, $n+1$ のときも主張は正しい。
$A_n$ の各要素について「選ぶ・選ばない」の2通りがあるため, 選び方の総数は $2^n$ 通りである。ここから「何も選ばない（和が0）」場合を除くと, 有効な和の作り方は全部で $2^n - 1$ 通りとなる。
表すべき自然数の個数（$1$ から $2^n-1$ まで）も $2^n-1$ 個であり, 選び方の総数と一致する。すべての自然数が少なくとも1通りで表せることは既に示したため, 各自然数に対する選び方は一意的である。
$1$, $2$, $3=1+2$, $4$, $5=1+4$, $6=2+4$, $7=1+2+4$
で $1$ から $2^3-1$ までの数をすべて和で表すことができました。
まとめノート
「数学的帰納法」とは
自然数に関する命題が、すべての自然数について成り立つことを証明するための手法のこと。
準備
自然数 $n$ に関する命題を $P(n)$ とする
A. 数学的帰納法
以下が成り立つならば, 任意の $n \in \mathbb{N}$ について, $P(n)$ が真である;
- $P(1)$ が真である
- $n \in \mathbb{N}$ について, $P(n)$ が真ならば, $P(n+1)$ も真である
B. 完全帰納法
以下が成り立つならば, 任意の $n \in \mathbb{N}$ について, $P(n)$ が真である;
- $P(1)$ が真である
- $n \in \mathbb{N}$ について, $P(1)$, $\cdots$, $P(n)$ がすべて真ならば, $P(n+1)$ も真である
C. ペアノの公理の第五公準
ペアノの公理の第五公準は, 集合 $\mathbb{N}$ と 数 $0$, 関数 $S$ について, $\forall E \subset \mathbb{N}$, $\forall n \in \mathbb{N}$; '$0 \in E$' $\land$ '$n \in E$ $\Rightarrow$ $S(n) \in E$' $\Rightarrow E = \mathbb{N}$.
ポイント解説
例
$\displaystyle P(n): \sum_{a=1}^n a = \frac{1}{2}n(n+1)$
- $n=1$ のとき, $1=1$ より, $P(1)$ は真である
- $n=k$ のとき $P(k)$ が真であると仮定する. $n=k+1$ のとき
$\sum_{a=1}^n a = 1+\cdots + n$
$=1+\cdots + k + (k+1)$ $=\frac{1}{2}k(k+1) + (k+1)$ $=\frac{1}{2}n(n+1)$
であり, $P(k+1)$ も真である. - 数学的帰納法により, すべての自然数 $n$ について, $P(n)$ は真である
C
ペアノの公理は数学的帰納法を保証する:
$E = \{ n \in \mathbb{N} \mid P(n) =\top \}$
,
$S(n) = n+1$
とすると, 第五公準はA(2)と一致する.
発展
整列集合 $(S, \leq )$では数学的帰納法をより一般化した超限帰納法が成り立つ:
- $P(\min M)$ が真である
- 任意の $\lambda < \mu$ $(\lambda \in S)$ について, $P(\lambda)$ が真ならば, $P(\mu)$ も真である
このとき, $\forall \mu \in M$; $P(\mu) = \top$ である.
