- 目次
- 理解
- 事例
- まとめ
【理解】数学的帰納法とは
数学的帰納法の解説について
すべての自然数 $n$ に対して, 命題 $P(n)$ が真であることを証明する
数学的帰納法
自然数 $n$ に関する命題を $P(n)$ とする.
次の(1)(2)が成り立つとき, 任意の自然数 $n$ について, $P(n)$ は真である.
- $P(1)$ が真である
- $n \in \mathbb{N}$ について, $P(n)$ が真ならば, $P(n+1)$ も真である
ドミノ倒しが成功する条件と同じ。
まず初めのドミノがちゃんと倒れる必要がある。これが(1)です。
$n$ 番目のドミノが倒れたとき, $n+1$ 番目のドミノもちゃんと倒れる必要がある。これが(2)です。
これらが確実なら, 何本のドミノでも全部倒れます。
帰納法のパラドックスについて
何本毛が生えていてもハゲである
禿げ頭のパラドクス
髪の毛が1本もない頭はハゲである。
ハゲ頭に一本毛が増えてもハゲである。
ゆえに、何本毛が生えていてもハゲである。
砂山からどれだけ砂を取り除いても砂山である
砂山のパラドクス
大量の砂は砂山をなす。
砂山から1粒取り除いても砂山である。
ゆえに、どれだけ砂を取り除いても砂山である。
極限でのふるまいについて
数学的帰納法は $\displaystyle \lim_{n \to \infty}P(n)$ での真偽は証明できない
数学的帰納法は全ての $n$ で $P(n)$ が真であることを示すが, 極限での真偽は言及できない.
(例) $\frac{n+1}{n} > 1$ は任意の自然数 $n$ で真だが, $n \to \infty$ では偽である.
【事例】数学的帰納法の例題集
数学的帰納法で証明できることの例題を集めました。
自分でも証明してみましょう！
数列の和に関する帰納的証明について
$\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)$ であることを数学的帰納法で証明してみよう。
公式
$$\displaystyle \sum_{k=1}^n k = \frac{1}{2}n(n+1)$$
証明のポイント
$$\begin{aligned}
&\frac{1}{2} n (n+1) + (n+1) \\
& = \frac{1}{2}(n+1)(n+2) \\
& = \frac{1}{2}(n+1)((n+1)+1)
\end{aligned}$$
証明.
等式 $\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)$ は成り立つ.
たとえば,
$n=3$ のとき,
① $1+2+3$
② $\displaystyle \frac{1}{2}\times 3 \times 4$
が公式の両辺。
②$+4$ を観察します。
$4$ を $\displaystyle \frac{1}{2} \times 4 \times 2$ として②に足すと,
$\displaystyle \frac{1}{2} \cdot 4 \cdot (3+2)$
とできます。
これは $n=4$ の右式になってます。
$\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)$ であることを数学的帰納法で証明してみよう。
公式
$$\displaystyle \sum_{k=1}^n k^2 = \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}$$
証明.
任意の自然数 $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= \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$ であることを数学的帰納法で証明してみよう。
公式
$$\displaystyle \sum_{k=1}^n k^3=\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}$$
証明.
任意の自然数 $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} = \frac{a(r^n-1)}{r-1}$
等比数列の和 $\displaystyle \sum_{k=1}^n ar^{k-1} =a + ar + \cdots + ar^{n-1}$ についての和の公式を数学的帰納法で証明してみよう。
公式
$a$ を定数とし, $r\neq1$ とする.
$$\sum_{k=1}^n ar^{k-1}= \frac{a(r^n-1)}{r-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}$$
証明.
等式 $\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}$ は成り立つ.
フィボナッチ数列に関する帰納的証明について
$\displaystyle 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$ からビネーの公式を数学的帰納法で導いてみよう。
ビネーの公式
フィボナッチ数列 $\{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_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\}$$ は正しい.
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$
フィボナッチ数列の初項から第 $n$ 項までの和が $F_{n+2}-1$ であることを証明してみよう。
公式
フィボナッチ数列 $\{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$ が成り立つ.
e.g. 具体的な観察。
$n=3$ のとき
① $F_1 + F_2 + F_3$
② $F_5 -1$
が同じ値の理由を観察します。
$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$
です。
①' $F_5$
②' $ F_3 + F_2 + F_1 + 1$
からそれぞれ $1$ を引けば, ①②ができます。
$F_1 + \ldots+F_{2n-1}=F_{2n}$
奇数番号のフィボナッチ数の和が $F_{2n}$ であることを証明してみよう。
公式
フィボナッチ数列 $\{F_n\}$ について $$F_1 + F_3 + \ldots + F_{2n-1} = F_{2n}$$
証明.
数学的帰納法によって示す.
$n=1$ のとき, 左辺は $F_1 = 1$ である. 右辺は $F_{2 \cdot 1} = 1$ である.
ゆえに, $n=1$ のとき, 示すべき等式は成り立つ.
$n=k \in \mathbb{N}$ のとき, $F_1 + F_3 + \ldots + F_{2k-1} = F_{2k} $ が成り立つと仮定する.
$n = k+1$ のときについて,
$$\begin{aligned}
F_{2n} &= F_{2(k+1)} \\
&= F_{2k+1} +F_{2k} \\
&= F_{2k+1} + (F_{2k-1} + \ldots +F_1) \\
&= F_{2n-1} + \ldots + F_1
\end{aligned}$$
フィボナッチ数列 $\{ F_n\}$ は $F_{2k+2} = F_{2k+1} + F_{2k}$ を満たす.
である.
ゆえに, $n=k+1$ のときも, 示すべき等式は成り立つ.
以上から, 数学的帰納法によって, 任意の自然数 $n$ について $F_1 + F_3 + \ldots + F_{2n-1} = F_{2n} $ が成り立つ.
e.g. 公式の観察。
$n=3$ のとき
① $F_1 + F_3 + F_5$
② $F_6$
が同じ理由を観察します。
①の $F_1$ は
$F_1 = F_2$.
①の $F_3$ は
$F_3 = F_4 - F_2$.
①の $F_5$ は
$F_5 = F_6- F_4$.
これらの和は $F_6$ で②と同じです。
$F_2 + \ldots+F_{2n}=F_{2n+1}-1$
偶数番号のフィボナッチ数の和が $F_{2n+1}-1$ であることを証明してみよう。
公式
フィボナッチ数列 $\{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}$$
フィボナッチ数列 $\{ F_n\}$ は $F_{2k+3} = F_{2k+2} + F_{2k+1}$ を満たす.
である.
ゆえに, $n=k+1$ のときも, 示すべき等式は成り立つ.
以上から, 数学的帰納法によって, 任意の自然数 $n$ について $F_2 + F_4 + \ldots + F_{2n} = F_{2n+1}-1 $ が成り立つ.
e.g. 公式の観察。
$n=3$ のとき
① $F_2 + F_4 + F_6$
② $F_7 - 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$ だから, ①は②と同じ値と分かる。
$F_1^2 + \ldots+F_{n}^2=F_nF_{n+1}$
フィボナッチ数列の初項から第 $n$ 項までの平方和が $F_nF_{n+1}$ であることを証明してみよう。
公式
フィボナッチ数列 $\{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}$ が成り立つ.
e.g. 公式の観察。
$n=3$ のとき,
① $F_1^2 + F_2^2 + F_3^2$
② $F_3F_4$
が等しい理由を観察します。
②について
$F_3F_4 = F_3(F_3+F_2)$ $= F_3^2+ F_2F_3$
です。$F_2F_3$ のところは
$F_2^2 + F_2F_1$
になります。 $F_2F_1$ のところは $F_2=F_1$ から, $F_1^2$ となります。
よって, ②は $F_3^2$ と $F_2^2$ と $F_1^2$ の和となり①と等しくなりました。
整数の性質の帰納的証明について
$5^n-1$ が $4$ の倍数である
任意の自然数 $n$ について, $5^n - 1$ が $4$ の倍数であることを数学的帰納法で証明してみよう。
命題
自然数 $n$ について $\displaystyle 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$ の倍数であることを数学的帰納法によって証明する.
$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$ の倍数であることが言える.
e.g. 命題の観察。
$5^1-1=4$
$5^2-1=24$
$5^3-1=124$
$n=1, 2, 3$ のときは, すべて $4$ の倍数です。
不等式の帰納的証明について
$n \geqq 2$ ならば $3^n > 4n$
2以上の任意の自然数 $n$ について, $3^n >4n$ が成り立つことを数学的帰納法で証明してみよう。
命題
$n \geqq2 $ の自然数について $3^n>4n$ が成り立つ.
命題.
$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 \cdot 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$ が成り立つことが示せた.
$n=1$ のとき $3>4$ で正しくありません。
$n=2$ のとき, $9 > 8$,
$n=3$ のとき $27>12$
で正しいです。
$n \geqq 4$ ならば $2^n > n^2 - n+2$
$4$ 以上の任意の自然数 $n$ について, $2^n>n^2 - n +2$ が成り立つことを数学的帰納法で証明してみよう。
命題
$4$ 以上の自然数 $n$ について $2^n>n^2 - n +2$ が成り立つ.
命題.
$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$ が成り立つことが示せた.
$n=1$ のとき $2>2$,
$n=2$ のとき $4>4$,
$n=3$ のとき $8>8$
で正しくありません。
$n=4$ のとき, $16 > 14$ で正しいです。
対称式 $a^n+b^n$ の変形を使う証明について
$a^n+b^n$ $= (a+b)(a^{n-1}+b^{n-1})$ $- ab(a^{n-2}+b^{n-2})$
$a^n + b^{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)$$
解説.
右辺を変形して, 左辺を導く.
右辺の第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})$
が成り立つ.
e.g. 変形の観察。
例えば,
$a^3 + b^3$
は
$(a+b)(a^2+b^2)$ $- ab(a+b)$
と等しいです。
基本対称式の漸化式を使う問題
$\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$ が成り立つことを数学的帰納法で証明してみよう。
命題
$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$ が成り立つことを数学的帰納法によって証明する.
まず,
$$\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$ が自然数
任意の自然数 $n$ について, $\displaystyle (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$ について $(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$ が自然数であることが示せた.
e.g. 命題の観察。
$(1+\sqrt{2})^n$ $+ (1-\sqrt{2})^n$
について,
$n=1$ のとき $2$,
$n=2$ のとき $6$,
$n=3$ のとき $14$,
ですべて自然数です。
様々な証明について
$(p + \sqrt{q})^n=a_n + b_n\sqrt{q}$ $\Leftrightarrow$ $(p - \sqrt{q})^n=a_n - b_n\sqrt{q}$
$\displaystyle (p+\sqrt{q})^n = a_n + b_n \sqrt{q}$ と表した時の数列 $\{a_n\}$ と $\{b_n\}$ について理解してみよう。
命題
$p$ と $q$ を正の定数とする. 任意の自然数 $n$ について,
$\displaystyle (p+\sqrt{q})^n = a_n + b_n \sqrt{q}$
と表すと,
$\displaystyle (p-\sqrt{q})^n = a_n - b_n \sqrt{q}$
であることが成り立つ. (この逆も成り立つ.)
系（係数の数列の一般項）
上の数列 $\{a_n\}$ と $\{b_n\}$ の一般項は,
$\displaystyle a_n = \frac{1}{2}\{(p+\sqrt{q})^n + (p-\sqrt{q})^n\}$
$\displaystyle b_n = \frac{1}{2\sqrt{q}}\{(p+\sqrt{q})^n - (p-\sqrt{q})^n\}$
である.
証明.
数学的帰納法で証明する. (逆の証明は割愛する.)
$n=1$ のとき,
$(p+\sqrt{q})^1 = 1+ \sqrt{q}$
$(p-\sqrt{q})^1 = 1- \sqrt{q}$
であるから, $a_1 = b_1=1$ でそれぞれの式の係数は等しい. よって, このとき主張は成り立つ.
次に $n \in \mathbb{N}$ のときに, 主張が成り立つことを仮定して, $n+1$ のときも主張が成り立つことを示す.
$(p+\sqrt{q})^{n+1}$
$=(p+\sqrt{q})(p+\sqrt{q})^n$
$=(p+\sqrt{q})(a_n + b_n \sqrt{q})$
$=(pa_n+q)+(a_n+pb_n)\sqrt{q}$
ゆえに, $a_{n+1} = pa_n+q$, $b_{n+1} = a_n+pb_n$ である.
一方で,
$(p-\sqrt{q})^{n+1}$
$=(p-\sqrt{q})(p-\sqrt{q})^n$
$=(p-\sqrt{q})(a_n - b_n \sqrt{q})$
$=(pa_n+q)-(a_n+pb_n)\sqrt{q}$
であり, それぞれの係数が $a_{n+1}$ と $b_{n+1}$ に一致している.
したがって, $n+1$ のときも主張が成り立つことが示せた.
ゆえに, 数学的帰納法から, 任意の自然数 $n$ について,
$\displaystyle (p+\sqrt{q})^n = a_n + b_n \sqrt{q}$
と表すと,
$\displaystyle (p-\sqrt{q})^n = a_n - b_n \sqrt{q}$
であることが成り立つことが示せた.
系の証明.
命題で得た２つの式を連立して, $b_n$ を消去することで $\{a_n\}$ の一般項が得られ, $a_n$ を消去することで $\{b_n\}$ の一般項が得られる.
例えば,
$(1+\sqrt{2})^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$ までの自然数をすべて作れること
$1$ から $2^{n}-1$ までのすべての自然数は, $1$, $2$, $2^2$, $\cdots$, $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$ までの自然数を表すことができることを数学的帰納法で示す.
$n=1$ のとき, $A_1$ の要素の $1$ を用いて $1$ を表すことができる.
$n \in \mathbb{N}$ のときに, 主張が成り立つとする. つまり, $1 \leq k \leq 2^{n}-1$ を満たす自然数について, 集合 $A_n$ から重複を許さずいくつか選んだ数の和で表せると仮定する.
このとき, $1$ から $2^{n+1}-1$ までの自然数を, 集合 $A_{n+1}$ から重複を許さずいくつか選んだ数の和で表せることを示す.
帰納法の仮定から $1 \leq k \leq 2^{n}-1$ を満たす自然数については, $A_{n+1} \supset A_n$ の数の和で表すことができる. また, $2^{n} \in A_{n+1}$ より $2^{n}$ も $A_{n+1}$ の数（の和）で表すことができる. $\cdots (\ast)$
さて, $2^{n} + 1$ から $2^{n+1}-1$ までの自然数については, $1 \leq k \leq 2^{n}-1$ を用いて, $2^n + k$ と表すことができる.
$A_n\cap \{2^n\} = \emptyset$ であり, $(\ast)$ から, $k$ は $A_n$ の数の和で表すことができるので, $2^n + k$ は $A_{n+1}$ の中の数の和で表すことできる.
したがって, $n$ のときに主張が正しいと仮定すると, $n+1$ のときも主張が正しいことを示すことができた.
ゆえに, 数学的帰納法から, 任意の自然数 $n$ について, $1$ から $2^{n}-1$ までのすべての自然数は, $1$, $2$, $2^2$, $\cdots$, $2^{n-1}$ の数の中から重複を許さずいくつか選んだ数の和で表わすことができると分かる.
なお, $1$ から $2^n-1$ までの数は $2^n-1$ 個である. 一方で, 集合 $A_n$ の中から重複を許さずに数を選ぶ組み合わせは, ( $A_n$ の要素の個数が $n$ 個であるから) $2^n$ 通りである. このうち, 何も選ばない場合を除けば, $2^n-1$ 通りである.
すなわち, 作るべき数の個数と和として選ぶ数の選び方の総数が一致しているので, 和の表し方は一意的である.
例えば, $n=3$ のとき,
$1$ から $2^2=4$ までの自然数を全部使えば,
$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$ である.
