- 表紙
- 解説
- 例題
- MEMO
- まとめ
数学的帰納法の解説
数学的帰納法とは
数学的帰納法の証明手順
数学的帰納法
自然数 $n$ に関する命題を $P(n)$ とする.
以下が成り立つならば, 任意の $n \in \mathbb{N}$ について, $P(n)$ が真である;
- $P(1)$ が真である
- $n \in \mathbb{N}$ について, $P(n)$ が真ならば, $P(n+1)$ も真である
例えば, $P(n): n +1 \in \mathbb{N}$ は
- $P(1): 2 \in \mathbb{N}$ は真です。
- $P(n): n+1 \in \mathbb{N}$ が真と仮定します。命題 $P(n+1)$ について, $(n+1)+1$ は $n+1 \in \mathbb{N}$ かつ $1 \in \mathbb{N}$ が言えるから, $(n+1)+1 = n+2 \in \mathbb{N}$ が真と言えます。
数学的帰納法によって, 全ての自然数 $n$ について命題 $P(n)$ は真です！
数学的帰納法の例題集
数学的帰納法で証明できることの例題を集めました。自分でも証明してみましょう！
数列の和の公式の証明例
$\displaystyle \sum_{k=1}^n k$ の公式の証明例
詳しい解説はこちら
公式
$$\displaystyle \sum_{k=1}^n k = \frac{1}{2}n(n+1)$$
$\displaystyle \sum_{k=1}^n k = 1+2+\cdots +n$ が $\displaystyle \frac{1}{2}n(n+1)$ であることを数学的帰納法で証明してみよう。
例えば, $1+2+3 =\frac{1}{2}\cdot 3 \cdot (1+3)$ の両辺に4を加えてみると, 左辺は1から4の和になり, 右辺は $\frac{1}{2} \cdot 3 \cdot 4 + 4$ について $\frac{1}{2}$ と $4$ でくくると $$\frac{1}{2} \cdot 4 \cdot (3+2) = \frac{1}{2} \cdot 4 \cdot 5$$ となり, これは $n=4$ のときの等式に一致します！
証明のイメージ
$$\begin{aligned}
&\frac{1}{2} n (n+1) + (n+1) \\
& = \frac{1}{2}n(n+1) + \frac{1}{2} (n+1)\cdot 2 \\
& = \frac{1}{2}(n+1)(n+2) \\
& = \frac{1}{2}(n+1)((n+1)+1) \\
\end{aligned}$$
公式. $\displaystyle \sum_{k=1}^nk=\frac{1}{2}n(n+1)$.
等式 $\displaystyle \sum_{k=1}^n k = \frac{1}{2}n(n+1)$ の両辺が, 任意の自然数 $n$ について等しいことを数学的帰納法によって証明する.
$n=1$ のとき, 左辺は $1$ であり, 右辺は $\frac{1}{2}\cdot 1 \cdot (1+1)=1$ である. ゆえに, $n=1$ のとき等式は成り立つ.
$n=\ell \geqq 1$ のとき, $\displaystyle \sum_{k=1}^{\ell} k = \frac{1}{2}\ell(\ell+1)$ と仮定する.
$n=\ell+1$ のとき, 等式の左辺 $\displaystyle \sum_{k=1}^{\ell+1} k$ を計算して, 右辺である $\displaystyle \frac{1}{2}(\ell+1)\{(\ell+1)+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$ のとき等式が成り立つと仮定すると, $n=\ell+1$ のときも等式が成り立つことが示せた.
数学的帰納法により, すべての自然数 $n$ について, 等式 $\displaystyle \sum_{k=1}^n k = \frac{1}{2}n(n+1)$ は成り立つ.
$\displaystyle \sum_{k=1}^n k^2$ の証明
詳しい解説はこちら
公式
$$\displaystyle \sum_{k=1}^n k^2 = \frac{1}{6}n(n+1)(2n+1)$$
$\displaystyle \sum_{k=1}^n k^2 = 1^2+2^2+\cdots +n^2$ が $\displaystyle \frac{1}{6}n(n+1)(2n+1)$ であることを数学的帰納法で証明してみよう。
証明のイメージ
$$\begin{aligned}
&\frac{1}{6} n (n+1)(2n+1) + (n+1)^2 \\
& = \frac{n+1}{6}\{n(2n+1) + 6(n+1)\} \\
& = \frac{n+1}{6}\{2n^2 + 7n +6 \} \\
& = \frac{n+1}{6}(n+2)(2n+3) \\
& = \frac{1}{6}(n+1)(n+2)(2(n+1)+1)
\end{aligned}$$
公式. $\displaystyle \sum_{k=1}^nk^2=\frac{1}{6}n(n+1)(2n+1)$.
任意の自然数 $n$ について, 等式 $\displaystyle \sum_{k=1}^n k^2 = \frac{1}{6}n(n+1)(2n+1)$ が正しいことを数学的帰納法によって証明する.
$n=1$ のとき, 左辺は $1^2=1$ であり, 右辺は $\frac{1}{6}\cdot 1 \cdot (1+1)(2\cdot 1 +1)=1$ である. ゆえに, $n=1$ のとき等式は成り立つ.
$n=\ell \geqq 1$ のとき, $\displaystyle \sum_{k=1}^{\ell} k^2 = \frac{1}{6}\ell(\ell+1)(2\ell +1)$ と仮定する.
$n=\ell+1$ のとき, 等式の左辺 $\displaystyle \sum_{k=1}^{\ell+1} k^2$ を計算していく.
$$\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$ について, 等式 $$\displaystyle \sum_{k=1}^n k^2 = \frac{1}{6}n(n+1)(2n+1)$$ は正しい.
$\displaystyle \sum_{k=1}^n k^3$ の証明
詳しい解説はこちら
公式
$$\displaystyle \sum_{k=1}^n k^3=\left\{ \frac{1}{2}n(n+1) \right\}^2$$
$\displaystyle \sum_{k=1}^n k^3 = 1^3+2^3+\cdots +n^3$ が $\displaystyle \left\{ \frac{1}{2}n(n+1) \right\}^2$ であることを数学的帰納法で証明してみよう。
証明のイメージ
$$\begin{aligned}
&\left\{ \frac{1}{2}n(n+1) \right\}^2 + (n+1)^3 \\
& = \frac{1}{2^2}(n+1)^2 \left\{ n^2 + 4(n+1) \right\} \\
& = \frac{1}{2^2}(n+1)^2 (n+2)^2 \\
& = \left\{ \frac{1}{2}(n+1)((n+1)+1) \right\}^2
\end{aligned}$$
公式. $\displaystyle \sum_{k=1}^nk^3 =\left\{ \frac{1}{2}n(n+1) \right\}^2$.
任意の自然数 $n$ について, 等式 $\displaystyle \sum_{k=1}^n k^3=\left\{ \frac{1}{2}n(n+1) \right\}^2$ が正しいことを数学的帰納法によって証明する.
$n=1$ のとき, 左辺は $1^3=1$ であり, 右辺は $\left\{ \frac{1}{2}\cdot 1 \cdot (1+1) \right\}^2=1$ である. ゆえに, $n=1$ のとき等式は成り立つ.
$n=\ell \geqq 1$ のとき, $\displaystyle \sum_{k=1}^n \ell^3=\left\{ \frac{1}{2}\ell(\ell+1) \right\}^2$ と仮定する.
$n=\ell+1$ のとき, 等式の左辺 $\displaystyle \sum_{k=1}^{\ell+1} k^3$ を計算していく.
$$\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}{2^2}(\ell+1)^2 \left\{ \ell^2 + 4(\ell+1) \right\} \\
& = \frac{1}{2^2}(\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$ について, 等式 $$\displaystyle \sum_{k=1}^n k^3=\left\{ \frac{1}{2}n(n+1) \right\}^2$$ は正しい.
$\displaystyle \sum_{k=1}^n ar^{k-1}$ の証明
詳しい解説はこちら
公式
$$\sum_{k=1}^n ar^{k-1}= \frac{a(r^n-1)}{r-1}$$
ただし, $r\neq1$ とする.
等比数列の和 $\sum_{k=1}^n ar^{k-1} =a + ar + \cdots + ar^{n-1}$ についての和の公式を数学的帰納法で証明してみよう。
証明のイメージ
$$\begin{aligned}
& \frac{a(r^n-1)}{r-1} + ar^n \\
&=\frac{a(r^n-1)}{r-1} +\frac{ar^n(r-1)}{r-1} \\
&=\frac{a \{ (r^n-1)+(r-1)r^n \}}{r-1} \\
&=\frac{a \{ r^n+(r-1)r^n -1\}}{r-1} \\
&=\frac{a \{ r \cdot r^n -1\}}{r-1} \\
&=\frac{a (r^{n+1} -1)}{r-1}
\end{aligned}$$
公式. $r \neq 1$, $a$ を定数とする. $\displaystyle \sum_{k=1}^n ar^{k-1}= \frac{a(r^n-1)}{r-1}$ である.
等式 $\displaystyle \sum_{k=1}^n ar^{k-1}= \frac{a(r^n-1)}{r-1}$ の両辺が, 任意の自然数 $n$ について等しいことを数学的帰納法によって証明する.
$n=1$ のとき, 左辺は $a$ であり, 右辺は $\frac{a(r-1)}{r-1}=a$ である. ゆえに, $n=1$ のとき等式は成り立つ.
$n=\ell \geqq 1$ のとき, $\displaystyle \sum_{k=1}^\ell ar^{k-1}= \frac{a(r^\ell-1)}{r-1}$ と仮定する.
$n=\ell+1$ のとき, 等式の左辺 $\displaystyle \sum_{k=1}^{\ell+1} ar^{k-1}$ を計算して, 右辺である $\displaystyle \frac{a(r^{\ell+1}-1)}{r-1}$ に変形する.
$$\begin{aligned}
\sum_{k=1}^{\ell+1} ar^{k-1} & = a + ar + \cdots + ar^{\ell-1} + ar^\ell \\
&=\frac{a(r^\ell-1)}{r-1} + ar^\ell \\
&=\frac{a(r^\ell-1)}{r-1} +\frac{ar^\ell(r-1)}{r-1} \\
&=\frac{a \{ (r^\ell-1)+(r-1)r^\ell \}}{r-1} \\
&=\frac{a \{ r^\ell+(r-1)r^\ell -1\}}{r-1} \\
&=\frac{a \{ r \cdot r^\ell -1\}}{r-1} \\
&=\frac{a (r^{\ell+1} -1)}{r-1}
\end{aligned}$$
よって, $n=\ell$ のとき等式が成り立つと仮定すると, $n=\ell+1$ のときも等式が成り立つことが示せた.
数学的帰納法により, すべての自然数 $n$ について, 等式 $\displaystyle \sum_{k=1}^n ar^{k-1}= \frac{a(r^n-1)}{r-1}$ は成り立つ.
フィボナッチ数列の公式の証明例
フィボナッチ数列の一般項
詳しい解説はこちら
ビネーの公式
フィボナッチ数列 $\{F_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\}$$
フィボナッチ数列の漸化式 $F_{n+2} = F_{n+1} + F_n$, $F_1=F_2=1$ からビネーの公式を数学的帰納法で導いてみよう。
$\alpha = \frac{1 + \sqrt{5}}{2}$ と $\beta = \frac{1 - \sqrt{5}}{2}$ とする。$\alpha^2 = \alpha+1$ かつ $\beta^2 = \beta + 1$ である。
$\begin{aligned}
F_{n+1} &= F_n + F_{n-1} \\
&= \frac{1}{\sqrt{5}}(\alpha^{n}- \beta^{n}) + \frac{1}{\sqrt{5}}(\alpha^{n-1}- \beta^{n-1}) \\
&= \frac{1}{\sqrt{5}}\{ (\alpha^n - \alpha^{n-1}) - (\beta^n - \beta^{n-1} ) \} \\
&= \frac{1}{\sqrt{5}}\{ (\alpha +1) \alpha^{n-1} - (\beta +1) \beta^{n-1} \} \\
&= \frac{1}{\sqrt{5}}\{ \alpha^2 \cdot \alpha^{n-1} - \beta^2 \cdot \beta^{n-1} \} \\
&= \frac{1}{\sqrt{5}}\{ \alpha^{n+1} - \beta^{n+1} \}
. \end{aligned}$
例題. $F_1=F_2=1$, $n\geqq 3$ のとき $F_{n} = F_{n-1} + F_{n-2}$ という漸化式で定義される数列 $\{ F_n \}$ の一般項を数学的帰納法で導きなさい。
次の式を予測し, すべての自然数 $n$ に対して正しいことを数学的帰納法によって示す.
$$\displaystyle F_n = \frac{1}{\sqrt{5}} ( \alpha^n - \beta^n ).$$
ただし, $\alpha = \frac{1+\sqrt{5}}{2}$ と $\beta = \frac{1-\sqrt{5}}{2}$ とする.
$n=1$ のとき, 左辺は $F_1=1$, 右辺は $\frac{1}{\sqrt{5}} ( \alpha - \beta ) = 1$ で式は成り立つ.
$n=2$ のとき, 左辺は $F_2=1$, 右辺は $\frac{1}{\sqrt{5}} ( \alpha^2 - \beta^2 ) = 1$ で式は成り立つ.
$n=3$ のとき, 左辺は $F_3=2$, 右辺は $\frac{1}{\sqrt{5}} ( \alpha^3 - \beta^3 ) = 2$ で式は成り立つ.
以上により, $n=1, \ 2, \ 3$ のとき, 予想の式は正しい.
$n \geqq 3$ とする. $k \leqq n$ の全ての自然数 $k$ で予想の式が正しいと仮定して, $n+1$ のときも式が正しいかを確かめる.
$$\begin{aligned}
F_{n+1} &= F_n + F_{n-1} \\
&= \frac{1}{\sqrt{5}}(\alpha^{n}- \beta^{n}) + \frac{1}{\sqrt{5}}(\alpha^{n-1}- \beta^{n-1}) \\
&= \frac{1}{\sqrt{5}}\{ (\alpha^n - \alpha^{n-1}) - (\beta^n - \beta^{n-1} ) \} \\
&= \frac{1}{\sqrt{5}}\{ (\alpha +1) \alpha^{n-1} - (\beta +1) \beta^{n-1} \} \\
&= \frac{1}{\sqrt{5}}\{ \alpha^2 \cdot \alpha^{n-1} - \beta^2 \cdot \beta^{n-1} \} \\
&= \frac{1}{\sqrt{5}}\{ \alpha^{n+1} - \beta^{n+1} \}
. \end{aligned}$$
$\alpha^2 = \alpha+1$ かつ $\beta^2 = \beta + 1$ を満たす.
したがって, $n+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\}$$ は正しい.
フィボナッチ数列の和の公式
詳しい解説はこちら
公式
フィボナッチ数列 $\{F_n\}$ について $$F_1 + \ldots + F_n = F_{n+2} -1$$
フィボナッチ数列の初項から第 $n$ 項までの和が $F_{n+2}-1$ であることを証明してみよう。
例えば, $F_1 + F_2 + F_3 = F_5 -1$ です。
公式のイメージ
$$\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_n\}$ について $F_1 + \ldots + 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)+1}-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 \\
&=F_n + \ldots + F_1
\end{aligned}$$
である。
ゆえに, $n=k+1$ のときも, 示すべき等式は成り立つ.
フィボナッチ数列 $\{ F_n\}$ は $F_{k+3} = F_{k+2} + F_{k+1}$ を満たす.
以上から, 数学的帰納法によって, 任意の自然数 $n$ について $F_1 + \ldots + F_n = F_{n+2}-1$ が成り立つ.
フィボナッチ数列の偶奇番目の和の公式
奇数番目だけのフィボナッチ数の和、偶数番目だけのフィボナッチ数の和も簡潔な公式で計算することができます。
詳しい解説はこちら
公式
フィボナッチ数列 $\{F_n\}$ について $$F_1 + \ldots + F_n = F_{n+2} -1$$
フィボナッチ数列の初項から第 $n$ 項までの和が $F_{n+2}-1$ であることを証明してみよう。
例えば, $F_1 + F_2 + F_3 = F_5 -1$ です。
公式のイメージ
$$\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_n\}$ について $F_1 + \ldots + 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)+1}-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 \\
&=F_n + \ldots + F_1
\end{aligned}$$
である。
ゆえに, $n=k+1$ のときも, 示すべき等式は成り立つ.
フィボナッチ数列 $\{ F_n\}$ は $F_{k+3} = F_{k+2} + F_{k+1}$ を満たす.
以上から, 数学的帰納法によって, 任意の自然数 $n$ について $F_1 + \ldots + F_n = F_{n+2}-1$ が成り立つ.
詳しい解説はこちら
公式
フィボナッチ数列 $\{F_n\}$ について $$F_2 + F_4 + \ldots + F_{2n} = F_{2n+1}-1$$
偶数番号のフィボナッチ数の和が $F_{2n+1}-1$ であることを証明してみよう。
例えば, $F_2 + F_4 + F_6 =12= F_7 - 1$ です。
公式のイメージ
$$\begin{aligned}
F_2 &= F_3 - F_1 \\
F_4 &= F_5 - F_3 \\
F_6 &= F_7- F_5 \\ \hline
&= F_7 -F_1 \\
&= F_7 -1
\end{aligned}$$
公式. フィボナッチ数列 $\{F_n\}$ について $F_2 + F_4 + \ldots + F_{2n} = F_{2n+1}-1$ が成り立つ.
数学的帰納法によって示す.
$n=1$ のとき, 左辺は $F_2 = 1$ である. 右辺は $F_{2 \cdot 1 +1}-1 = 2-1=1$ である.
ゆえに, $n=1$ のとき, 示すべき等式は成り立つ.
$n=k \in \mathbb{N}$ のとき, $F_2 + F_4 + \ldots + F_{2k} = F_{2k+1}-1 $ が成り立つと仮定する.
$n = k+1$ のときについて,
$$\begin{aligned}
F_{2n+1} -1 &= F_{2(k+1)+1} -1 \\
&= F_{2k+3} -1 \\
&= F_{2k+2} +F_{2k+1}-1 \\
&= F_{2(k+1)} + (F_{2k} + \ldots +F_2) \\
&= F_{2(k+1)} + \ldots + F_2 \\
&= F_{2n} + \ldots + F_2 \\
\end{aligned}$$
である.
ゆえに, $n=k+1$ のときも, 示すべき等式は成り立つ.
フィボナッチ数列 $\{ F_n\}$ は $F_{2k+3} = F_{2k+2} + F_{2k+1}$ を満たす.
以上から, 数学的帰納法によって, 任意の自然数 $n$ について $F_2 + F_4 + \ldots + F_{2n} = F_{2n+1}-1 $ が成り立つ.
フィボナッチ数列の平方和の公式
詳しい解説はこちら
公式
フィボナッチ数列 $\{F_n\}$ について $$F_1^2 + \ldots + F_n^2 = F_nF_{n+1}$$
フィボナッチ数列の初項から第 $n$ 項までの平方和が $F_nF_{n+1}$ であることを証明してみよう。
例えば, $F_1^2 + F_2^2 + F_3^2 = F_3F_4$ です。
公式のイメージ
$$\begin{aligned}
F_3F_4 &= F_3(F_3+F_2) \\
&= F_3^2+ F_2F_3 \\
&= F_3^2+ F_2(F_2+ F_1) \\
&= F_3^2 + F_2^2 + F_2F_1 \\
&= F_3^2 + F_2^2 + F_1^2
\end{aligned}$$
公式. フィボナッチ数列 $\{F_n\}$ について $F_1^2 + \ldots + 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 + \ldots + F_k^2 = F_kF_{k+1}$ が成り立つと仮定する.
$n = k+1$ のときについて,
$$\begin{aligned}
F_{n}F_{n + 1} &= 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 + \ldots + F_1^2) \\
&= F_{k+1}^2 + \ldots + F_1^2 \\
&=F_n^2 + \ldots + F_1^2
\end{aligned}$$
である。
ゆえに, $n=k+1$ のときも, 示すべき等式は成り立つ.
フィボナッチ数列 $\{ F_n\}$ は $F_{k+2} = F_{k+1} + F_{k}$ を満たす.
以上から, 数学的帰納法によって, 任意の自然数 $n$ について $F_1^2 + \ldots + F_n^2 = F_{n}F_{n+1}$ が成り立つ.
さまざまな整数の性質の証明
$4$ の倍数
詳しい解説はこちら
命題
自然数 $n$ について $\displaystyle 5^n-1$ は $4$ の倍数である.
任意の自然数 $n$ について, $5^n - 1$ が $4$ の倍数であることを数学的帰納法で証明してみよう。
例えば, $5^1-1=4$, $5^2-1=24$, $5^3-1=124$ で, すべて $4$ の倍数です！
証明のイメージ
$5^{n+1}-1= 5(5^n-1) +4$ なので, $5^n-1$ が $4$ の倍数ならば, $5^{n+1}-1$ のときも $4$ の倍数になります。
命題.
任意の自然数 $n$ について $5^n-1$ が $4$ の倍数であることを数学的帰納法によって証明する.
$n=1$ のとき, $5^1-1=1$ であり, これは $4$ の倍数である. ゆえに, $n=1$ のとき主張は正しい.
$n=\ell \geqq 1$ のとき, $5^n-1$ が $4$ の倍数であると仮定する. つまり, ある自然数 $k$ によって, $5^\ell-1 = 4k$ と書けるとする.
$n=\ell+1$ のとき, $5^n - 1$ が $4$ の倍数であることを示す.
$$\begin{aligned}
&5^{\ell + 1}-1 \\
&=5 \cdot 5^\ell -1 \\
&= 5(5^\ell - 1 + 1) -1 \\
&= 5(5^\ell - 1) + 5 -1 \\
&= 5(5^\ell - 1) + 4 \\
&= 5(4k) + 4 \\
& = 4(5k+1)
\end{aligned}$$
$5k+1$ は自然数であるから, $4(5k+1)$ は $4$ の倍数であり, $5^{\ell+1}-1$ も $4$ の倍数である.
よって, $n=\ell$ のとき主張が正しいと仮定すると, $n=\ell+1$ のときも主張が正しいことが示せた.
数学的帰納法により, 任意の自然数 $n$ について, $5^n-1$ は $4$ の倍数であることが言える.
さまざまな不等式の証明
$3^n > 4n$
詳しい解説はこちら
命題
$n \geqq2 $ の自然数について $3^n>4n$ が成り立つ.
任意の自然数 $n$ について, $3^n >4n$ が成り立つことを数学的帰納法で証明してみよう。
例えば, $n=1$ のとき $3>4$ で正しくありません。$n=2$ のとき, $9 > 8$, $n=3$ のとき $27>12$ でどちらも正しいです！
命題.
$n \geqq 2$ の任意の自然数について $3^n > 4n$ が成り立つことを数学的帰納法によって証明する.
$n=2$ のとき, 左辺は $3^2=9$, 右辺は $4 \cdot 2 = 8$ であり, 不等式は成り立つ. ゆえに, $n=2$ のとき主張は正しい.
$n=k \geqq 2$ のとき, $3^k>4k$ が成り立つと仮定する.
$n=k+1$ のときにも, $3^n > 4n$ が成り立つことを示す.
$$\begin{aligned}
&3^n -4n \\
& = 3^{k+1}-4(k+1) \\
&=3 \cdot 3^k -4(k+1)\\
&> 3(4k) - 4(k+1) \\
&= 8k - 4\\
&= 4(2k-1) \\
& >0
\end{aligned}$$
$3^n - 4n > 0$ より, $3^n > 4n$ である.
よって, $n=k$ のとき主張が正しいと仮定すると, $n=k+1$ のときも主張が正しいことが示せた.
数学的帰納法により, 任意の自然数 $n \geqq 2$ について, $3^n>4n$ が成り立つことが示せた.
$2^n > n^2 - n+2$
詳しい解説はこちら
命題
$4$ 以上の自然数 $n$ について $2^n>n^2 - n +2$ が成り立つ.
任意の自然数 $n \geqq 4$ について, $2^n>n^2 - n +2$ が成り立つことを数学的帰納法で証明してみよう。
例えば, $n=1$ のとき $2>2$, $n=2$ のとき $4>4$, $n=3$ のとき $8>8$ で正しくありません。$n=4$ のとき, $16 > 14$ で正しいです！
命題.
$n \geqq 4$ の任意の自然数について $2^n > n^2-n+2$ が成り立つことを数学的帰納法によって証明する.
$n=4$ のとき, 左辺は $2^4=16$, 右辺は $4^2 - 4 + 2 = 14$ であり, 不等式は成り立つ. ゆえに, $n=4$ のとき主張は正しい.
$n=k \geqq 2$ のとき, $2^k>k^2 - k + 2$ が成り立つと仮定する.
$n=k+1$ のときにも, $2^n > n^2 - n +2$ が成り立つことを示す.
$$\begin{aligned}
&2^n -(n^2-n+2) \\
& = 2^{k+1} \\
& \phantom{xxx} -\{(k+1)^2-(k+1)+2\} \\
& = 2 \cdot 2^{k} \\
& \phantom{xxx} -\{(k+1)^2-(k+1)+2\} \\
& > 2 (k^2 - k +2) \\
& \phantom{xxx} -\{(k+1)^2-(k+1)+2\} \\
& = k^2 - 3k +2 \\
&=(k-1)(k-2) \\
& >0
\end{aligned}$$
$2^n - (n^2 - n+2) > 0$ より, $2^n > n^2-n+2$ である.
よって, $n=k$ のとき不等式が成り立つと仮定すると, $n=k+1$ のときも不等式が成り立つことが示せた.
数学的帰納法により, 任意の自然数 $n \geqq 4$ について, $2^n>n^2 - n +2$ が成り立つことが示せた.
$a^n+b^n$ の変形を利用する問題
$S(n)=a^n + b^n$ とする. $s(n+2) = (a+b)s(n+1) - abs(n)$ という関係式が成り立ちます。
詳しい解説はこちら
式の変形
$a^{n+2} + b^{n+2}$ $= (a+b)(a^{n+1}+b^{n+1}) - ab(a^{n} + b^{n})$
漸化式
$S(n)=a^{n} + b^{n}$ とすると, 次が成り立つ:
$$S(n+2) = (a+b)S(n+1) - abS(n)$$
$a^{b+2} + b^{n+2}$ を変形する仕方を理解してみよう。
例えば, $a^3 + b^3$ $=(a+b)(a^2+b^2) - ab(a+b)$ という計算です。
解説.
右辺を変形して, 左辺を導く.
右辺の第1項目 $(a+b)(a^{n+1} + b^{n+1})$ を展開すると, $$a^{n+2} + b^{n+2} + ab^{n+1} + ba^{n+1}$$ となる.
右辺の第2項目 $-ab(a^n+b^n)$ を展開すると, $$-ba^{n+1} - ab^{n+1}$$ となる.
これらの和を求めると, $a^{n+2} + b^{n+2}$ となる.
ゆえに,
$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$ のとき, $$\displaystyle \frac{a^n+b^n}{2} \geqq \left(\frac{a+b}{2} \right)^n$$ が成り立つ.
等号成立は, $a=b$ のときである. ただし, $n=1$ のときのみ $a\neq b$ であっても等号は成立する.
任意の自然数 $n$ について, $\displaystyle \frac{a^n+b^n}{2} \geqq \left(\frac{a+b}{2} \right)^n$ が成り立つことを数学的帰納法で証明してみよう。
命題.
任意の自然数 $n$ について $\displaystyle \frac{a^n+b^n}{2} \geqq \left(\frac{a+b}{2} \right)^n$ が成り立つことを数学的帰納法によって証明する.
まず,
$$\begin{aligned} A(n) &=\frac{a^n+b^n}{2} \\ B(n) &=\left(\frac{a+b}{2} \right)^n\end{aligned}$$ と置く.
$n=1$ のとき, 両辺ともに $\displaystyle \frac{a+b}{2}$ となる. したがって, $n=1$ のとき主張は正しい.
$n=k \geqq 1$ のとき, $\displaystyle A(k) \geqq B(k)$ が成り立つと仮定する.
$n=k+1$ のときにも, $\displaystyle A(k+1) \geqq B(k+1)$ が成り立つことを示す. そのために, $f(n) = A(n) - B(n)$ と置き, $f(k+1) \geqq 0$ を示すこととする.
$$f(n)=\displaystyle \frac{a^n+b^n}{2} - \left(\frac{a+b}{2} \right)^n$$
また, 次の関係式が成り立つ.
$$A(k+1) = (a+b)A(k) - abA(k-1)$$
$\displaystyle A(k+1) = \frac{a^{k+1}+b^{k+1}}{2}$ の分子について次の変形をすることで, 該当の等式は得られる.
$$a^{k+1} + b^{k+1} = (a+b)(a^k + b^k) - ab(a^{k-1} + b^{k-1})$$
以上を踏まえて, $f(k+1) \geqq 0$ であることを確かめる.
$$\begin{aligned}
&f(k+1) \\
&=A(k+1) - B(k+1) \\
& =(a+b)A(k) - abA(k-1) - B(k+1)\\
& =\frac{a+b}{2}A(k) - abA(k-1) \\
& \phantom{xx} + \frac{a+b}{2}A(k) - B(k+1)\\
& =\frac{a+b}{2}A(k) - abA(k-1) \\
& \phantom{xx} + \frac{a+b}{2}(A(k) - B(k))
\end{aligned}$$
最後の等号は下の関係を利用している.
$\displaystyle B(k+1)=\frac{a+b}{2} B(k)$
第1項目と第2項目について, $A(k)$ と $A(k-1)$ を元の式に戻して直接計算すると, $(a-b)(a^k-b^k)$ となる.
$a-b$ と $a^k-b^k$ の正負は同じであるから, $$(a-b)(a^k-b^k) \geqq 0$$ である.
第3項目については, 数学的帰納法の仮定より $\displaystyle A(k)-B(k) \geqq 0$ であったから, $$\frac{a+b}{2}(A(k) - B(k)) \geqq 0$$ が言える.
したがって,
$$f(k+1) = (a-b)(a^k - b^k) \phantom{x} +\frac{a+b}{2}(A(k) - B(k))$$
であって, $f(k+1) \geqq 0$ である.
等号成立は, $$(a-b)(a^k-b^k) = 0$$ と仮定すると, $k$ が奇数のときは $a=b$ が必要条件であり, $k$ が偶数のときは $|a| = |b|$ が必要条件である.
これらの条件が, $$\frac{a+b}{2}(A(k) - B(k)) = 0$$ を満足するか検証する.
$k$ が偶数で, かつ $a = -b$ である場合, $A(k)-B(k) =a^n$ である. よって, $a=b=0$ のときのみ等号が成立する.
また, $a=b$ であれば, $A(k)=a^k$, $B(k)=a^k$ を満たし, $\displaystyle \frac{a+b}{2}(A(k) - B(k)) = 0$ である.
ゆえに, 等号成立は $a=b$ のときのみであることが分かる.
よって, $n=k$ のとき, 不等式 $A(k) \geqq B(k)$ が成り立つと仮定すると, $n=k+1$ のときも不等式 $A(k+1) \geqq B(k+1)$ が成り立つことが示せた.
等号成立は, $n=1$ のときは $a$, $b$ が任意の実数に対して成り立ち, $n \geqq 2$ のときは $a=b$ のときに限る.
ゆえに, 数学的帰納法により, 任意の自然数 $n$ について, $$\displaystyle \frac{a^n+b^n}{2} \geqq \left(\frac{a+b}{2} \right)^n$$ が成り立つことが示せた.
$(1+\sqrt{x})^n+(1-\sqrt{x})^n$ が自然数
詳しい解説はこちら
命題
$x \in \mathbb{N}$, $n \in \mathbb{N}$ のとき, $(1+\sqrt{x})^n + (1-\sqrt{x})^n$ は自然数となる.
任意の自然数 $n$ について, $\displaystyle (1+\sqrt{x})^n + (1-\sqrt{x})^n$ が自然数であることを数学的帰納法で証明してみよう。
例えば, $\displaystyle (1+\sqrt{2})^n + (1-\sqrt{2})^n$ について, $n=1$ のとき $2$, $n=2$ のとき $6$, $n=3$ のとき $14$ ですべて自然数になってます。
命題.
任意の自然数 $n$ について $(1+\sqrt{x})^n + (1-\sqrt{x})^n$ が自然数であることを数学的帰納法によって証明する.
便宜上, 次のように置く.
$$A_x(n) =(1+\sqrt{x})^n + (1-\sqrt{x})^n$$
$A_x(1) =2$, $A_x(2) = 2(1+x)$ であり, それぞれ自然数である. したがって, $n=1, \ 2$ のときは主張は正しい.
$n = k \geqq 2$ とする. $n=1, \cdots, k$ において, $A_x(n)$ が自然数であると仮定する.
$n=k+1$ のときにも, $A_x(n)$ が自然数であることを示す. $A_x(k+1)$ について, 次のように変形する.
$$A_x(k+1) = 2A_x(k) + (x-1)A_x(k-1) \cdots (\ast)$$
$a^{k+1} + b^{k+1}$ $=(a+b) (a^{k} + b^{k})- ab(a^{k-1} + b^{k-1})$
帰納法の仮定により $A_x(k)$, $A_x(k-1)$ は自然数である. また, $x-1$ は非負の整数であるため, $2A_x(k) + (x-1)A_x(k-1)$ は自然数であると言える.
よって, $n=k$ のとき不等式が成り立つと仮定すると, $n=k+1$ のときも不等式が成り立つことが示せた.
数学的帰納法により, 任意の自然数 $n$ について, $(1+\sqrt{x})^n + (1-\sqrt{x})^n$ が自然数であることが示せた.
数学的帰納法の具体例
禿げ頭のパラドクス
髪の毛が1本もない頭はハゲである。
ハゲ頭に一本毛が増えてもハゲである。
ゆえに、何本毛が生えていてもハゲである。
砂山のパラドクス
大量の砂は砂山をなす。
砂山から1粒取り除いても砂山である。
ゆえに、どれだけ砂を取り除いても砂山である。
極限でのふるまい
数学的帰納法は全ての $n$ で $P(n)$ が真であることを示すが, 極限での真偽は言及できない.
(例) $\frac{n+1}{n} > 1$ は任意の自然数 $n$ で真だが, $n \to \infty$ では偽である.
数学のまとめノート
「数学的帰納法」とは
自然数に関する命題が、すべての自然数について成り立つことを証明するための手法のこと。
準備
自然数 $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$ である.
