- 目次
- 理解
- 事例
- まとめ
【理解】数学的帰納法とは
数学的帰納法の解説について
すべての自然数 $n$ に対して, 命題 $P(n)$ が真であることを証明する
[custom_content_widget post_id="37304"]
帰納法のパラドックスについて
何本毛が生えていてもハゲである
禿げ頭のパラドクス
髪の毛が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)$
[custom_content_widget post_id="37309"]
$\displaystyle \sum_{k=1}^n k^2= \frac{1}{6}n(n+1)(2n+1)$
[custom_content_widget post_id="37382"]
$\displaystyle \sum_{k=1}^n k^3= \left\{\frac{1}{2}n(n+1)\right\}^2$
[custom_content_widget post_id="37413"]
$\displaystyle \sum_{k=1}^n ar^{k-1} = \frac{a(r^n-1)}{r-1}$
[custom_content_widget post_id="37441"]
フィボナッチ数列に関する帰納的証明について
$\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\}$
[custom_content_widget post_id="37351"]
$F_1 + \ldots+F_n=F_{n+2}-1$
[custom_content_widget post_id="37061"]
$F_1 + \ldots+F_{2n-1}=F_{2n}$
[custom_content_widget post_id="37093"]
$F_2 + \ldots+F_{2n}=F_{2n+1}-1$
[custom_content_widget post_id="37107"]
$F_1^2 + \ldots+F_{n}^2=F_nF_{n+1}$
[custom_content_widget post_id="37474"]
整数の性質の帰納的証明について
$5^n-1$ が $4$ の倍数である
[custom_content_widget post_id="38155"]
不等式の帰納的証明について
$n \geqq 2$ ならば $3^n > 4n$
[custom_content_widget post_id="38165"]
$n \geqq 4$ ならば $2^n > n^2 - n+2$
[custom_content_widget post_id="38176"]
対称式 $a^n+b^n$ の変形を使う証明について
$a^n+b^n$ $= (a+b)(a^{n-1}+b^{n-1})$ $- ab(a^{n-2}+b^{n-2})$
[custom_content_widget post_id="38578"]
基本対称式の漸化式を使う問題
$\displaystyle \frac{a^n+b^n}{2} \geqq \left(\frac{a+b}{2}\right)^n$
[custom_content_widget post_id="38416"]
$(1+\sqrt{x})^n+(1-\sqrt{x})^n$ が自然数
[custom_content_widget post_id="38421"]
様々な証明について
$(p + \sqrt{q})^n=a_n + b_n\sqrt{q}$ $\Leftrightarrow$ $(p - \sqrt{q})^n=a_n - b_n\sqrt{q}$
[custom_content_widget post_id="38710"]
$1$, $2$, $2^2$, $\cdots$, $2^{n-1}$ を使って $1$ から $2^{n}-1$ までの自然数をすべて作れること
[custom_content_widget post_id="38426"]
まとめノート
「数学的帰納法」とは
自然数に関する命題が、すべての自然数について成り立つことを証明するための手法のこと。
準備
自然数 $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$ である.
