- 表紙
- まとめ
- 論理
- 具体例
数学のまとめノート
「数学的帰納法」とは
自然数に関する命題が、すべての自然数について成り立つことを証明するための手法のこと。
準備
自然数 $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$ である.
数学的帰納法の解説
数学的帰納法とは
数学的帰納法の証明手順
数学的帰納法
自然数 $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)$ は真です！
和の公式の証明例
$\sum_{k=1}^n k=\frac{1}{2}n(n+1)$ の証明
詳しい解説はこちら
公式
$$\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)$ は成り立つ.
$\sum_{k=1}^n k^2=\frac{1}{6}n(n+1)(2n+1)$ の証明
詳しい解説はこちら
公式
$$\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)$$ は正しい.
$\sum_{k=1}^n k^3=\left\{ \frac{1}{2}n(n+1) \right\}^2$ の証明
詳しい解説はこちら
公式
$$\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$$ は正しい.
$\sum_{k=1}^n ar^{k-1}= \frac{a(r^n-1)}{r-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}$ が成り立つ.
数学的帰納法の具体例
禿げ頭のパラドクス
髪の毛が1本もない頭はハゲである。
ハゲ頭に一本毛が増えてもハゲである。
ゆえに、何本毛が生えていてもハゲである。
砂山のパラドクス
大量の砂は砂山をなす。
砂山から1粒取り除いても砂山である。
ゆえに、どれだけ砂を取り除いても砂山である。
極限でのふるまい
数学的帰納法は全ての $n$ で $P(n)$ が真であることを示すが, 極限での真偽は言及できない.
(例) $\frac{n+1}{n} > 1$ は任意の自然数 $n$ で真だが, $n \to \infty$ では偽である.
