5.2 強い数学的帰納法

数学的帰納法の特に有用な変種に強い数学的帰納法 (strong induction) がある。この手法を使う目的は通常の数学的帰納法と変わらない: 全ての非負整数で何らかの述語が成り立つことを示すために使われる。\(n + 1\) に対する述語の成立が \(n\) に対する成立からは示せず、\(n\) 以下の全ての非負整数に対する成立を使って初めて示せるとき強い数学的帰納法は有用となる。

5.2.1 強い数学的帰納法に関する規則

強い数学的帰納法の原理 (principle of strong induction)

\(P(n)\) を非負整数 \(n\) に関する述語とする。次の条件が成り立つと仮定する:

\(P(0)\) が真
全ての \(n \in \mathbb{N}\) で、\(P(0)\), \(P(1)\), \(\ldots\), \(P(n)\) が全て真だと仮定すると \(P(n+1)\) が真

このとき全ての \(m \in \mathbb{N}\) で \(P(m)\) が成り立つ。

通常の数学的帰納法との唯一の違いは、帰納ステップで使える仮定が増えることである！通常の数学的帰納法では \(P(n)\) が真だと仮定して \(P(n+1)\) を証明するのに対して、強い数学的帰納法では \(P(0)\), \(P(1)\), \(\ldots\), \(P(n)\) が全て真だと仮定して \(P(n+1)\) の証明に挑める。つまり仮定できる命題が強いので、証明は簡単になる。

強い数学的帰納法は推論規則として次のように表せる:

推論規則

\[ \frac{P(0),\quad \forall n \in \mathbb{N}.\ (P(0) \ \operatorname{\text{\footnotesize AND}} \ P(1) \ \operatorname{\text{\footnotesize AND}} \ \cdots \ \operatorname{\text{\footnotesize AND}} \ P(n)) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(n+1)} {\forall m \in \mathbb{N}.\ P(m)} \]

さらに簡潔にも表現できる:

推論規則

\[ \frac{P(0), \quad (\forall k \leq n \in \mathbb{N}.\ P(k)) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(n+1)}{\forall m \in \mathbb{N}.\ P(m)} \]

強い数学的帰納法を使った証明のテンプレートは第 5.1.2 項で示したテンプレートと基本的に変わらない。ただ、次の二点が異なる:

最初に「強い数学的帰納法で示す」と書く。
帰納ステップでは \(P(n)\) だけではなく \(P(0)\), \(P(1)\), \(\ldots\), \(P(n)\) の全てが真だと仮定してよい。

5.2.2 Fibonacci 数

十三世紀の初頭にイタリア人数学者 Fibonacciフィボナッチが考案したウサギの繁殖モデルの中で、彼の名前が付けられる数列が登場した。Fibonacci 数 (Fibonacci number) はパイナップルの芽や松ぼっくりの形といった様々な興味深い生物学的特徴の成長を記述できることが分かっており、情報科学でもデータ構造の複雑性やアルゴリズムの計算時間の解析で姿を現す。

Fibonacci 数を並べた列は、\(0\) と \(1\) から初めて最後の二要素の和を書き足していくことで得られる:

\[ 0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ \ldots \]

\(n\) 番目の Fibonacci 数 \(F(n)\) の数式を使った定義を次に示す:

\[ \begin{aligned} F(0) &::= 0 \\ F(1) &::= 1 \\ F(n) &::= F(n-1) + F(n-2) \qquad (n \geq 2) \end{aligned} \]

\(F(n)\) の値は直前の二つの値 \(F(n-1)\) と \(F(n-2)\) を利用して計算されるので、\(F(0)\) と \(F(1)\) という二つの初期値が必要になる点に注意してほしい。

Fibonacci 数の簡単な性質として、「偶数・奇数・奇数」という長さ \(3\) のパターンが繰り返されることがある。この性質は同値関係を使うと簡潔に表現できる:

\(F(n)\) は偶数 \(\quad \longleftrightarrow \quad\) \(F(n + 3)\) が偶数

\((5.4)\)

ここで \(n\) は任意の非負整数である。これから数学的帰納法で同値関係 \(\text{(5.4)}\) を証明する。\(F(n)\) は \(F(n-1)\) だけではなく \(F(n-2)\) にも依存するので、この証明には強い数学的帰納法が必要になる。

証明強い数学的帰納法で示す。同値関係 \(\text{(5.4)}\) を強い帰納法の仮定 \(P(n)\) とする。

ベースケース:

\(n = 0\) のとき \(F(0) = 0\) と \(F(3) = 2\) はどちらも偶数である。
\(n = 1\) のとき \(F(1) = 1\) と \(F(4) = 3\) はどちらも偶数でない。

よって \(P(0)\) と \(P(1)\) は成り立つ。

帰納ステップ: \(n \geq 1\) とする。これから強い帰納法の仮定 \(P(n)\) と \(P(n-1)\) を使って \(P(n+1)\) を示す。

容易に分かるように、任意の整数 \(k\), \(m\) に対して次の関係が成り立つ:

\[ m + k \text{ が偶数 } \quad \longleftrightarrow \quad (m \text{ が偶数} \ \longleftrightarrow \ k \text{ が偶数}) \tag{\(\ast\)} \]

よって \(n \geq 1\) に対して次が分かる:

\[ \begin{aligned} F(n+1) \text{ が偶数} \quad \longleftrightarrow \quad & F(n) + F(n-1) \text{ が偶数} \\ & \quad (\because\ F(n+1) \text{ の定義より}) \\ \longleftrightarrow \quad & (F(n) \text{ が偶数}\ \longleftrightarrow\ F(n-1) \text{ が偶数}) \\ & \quad (\because\ (\ast) \text{ より} ) \\ \longleftrightarrow \quad & (F(n+3) \text{ が偶数}\ \longleftrightarrow\ F(n+2) \text{ が偶数}) \\ & \quad (\because\ \text{強い帰納法の仮定より} ) \\ \longleftrightarrow \quad & F(n+3) + F(n+2) \text{ が偶数}\\ & \quad (\because\ (\ast) \text{ より} ) \\ \longleftrightarrow \quad & F(n+4) \text{ が偶数} \\ & \quad (\because\ F(n+4) \text{ の定義より}) \end{aligned} \]

つまり次の関係が分かった:

\[ F(n + 1) \text{ が偶数} \quad \longleftrightarrow \quad F(n+4) \text{ が偶数} \]

これは \(P(n+1)\) の成立を意味するので、示したい命題は証明された。 ■

Fibonacci 数には長く続く愛好家コミュニティが存在し、彼らによって発見された様々な驚くべき性質が知られている。問題 5.8, 問題 5.25, 問題 5.30 でその一部を見る。

5.2.3 素因数分解

以前に整列原理を使って証明した定理 2.3.1 を、今度は強い数学的帰納法で証明してみよう。

定理

\(1\) より大きい任意の整数は、素数の積として表せる。

証明強い数学的帰納法で示す。述語 \(P(n)\) を次のように定める:

\(n\) は素数の積として表せる。

全ての \(n \geq 2\) で \(P(n)\) が成り立つと示せばよい。\(P(n)\) を帰納法の仮定とする。

ベースケース: \(2\) は素数であり、慣習により一つの素数 \(2\) の積は \(2\) に等しい。よって \(P(2)\) は成り立つ。

帰納ステップ: ある \(n \geq 2\) で、\(2\) から \(n\) までの全ての整数が素数の積として表せると仮定する。この上で \(P(n+1)\) を示す必要がある。つまり、\(n+1\) が素数の積として表せると示さなければならない。二つの場合を分けて考える:

Case 1:

\(n + 1\) が素数なら、慣習により一つの素数 \(n+1\) の積は \(n+1\) に等しい。よって \(P(n+1)\) は成り立つ。

Case 2:

\(n + 1\) が素数でないなら、定義より \(n + 1 = k \cdot m\) を満たす整数 \(k\), \(m\) が存在する。この \(k\), \(m\) はいずれも \(2\) 以上 \(n\) 以下なので、強い帰納法の仮定より \(k\) と \(m\) は素数の積として表せる。よって素数の積を二つ乗じた \(k \cdot m = n + 1\) も素数の積として表せる。つまり \(P(n+1)\) は成り立つ。

両方の場合で \(P(n+1)\) は成り立つと分かった。よって強い数学的帰納法の原理より全ての \(n \geq 2\) で \(P(n)\) は成り立つ。 ■

5.2.4 小銭の計算

Inductiaインダクティアという国で流通する通貨 Strongストロング (\(\text{Sg}\)) には \(3~\text{Sg}\) 硬貨と \(5~\text{Sg}\) 硬貨が存在する。Inductia の人々は \(4~\text{Sg}\) や \(7~\text{Sg}\) といった少ない額は硬貨でちょうど支払えないものの、\(8~\text{Sg}\) 以上の額であれば硬貨だけでちょうど支払えることを知っていた。

Inductia の硬貨を使った 26~\text{Sg} の支払い — 図 5.5Inductia の硬貨を使った \(26~\text{Sg}\) の支払い

強い数学的帰納法を使うとき、\(n + 1 \geq 11\) のケースは簡単に証明できる。なぜなら \((n + 1) - 3 \geq 8\) であり、強い帰納法の仮定により \((n+1) - 3 ~\text{Sg}\) はちょうど支払えると言えるからである。その支払い方法に \(3~\text{Sg}\) を加えれば \(n + 1~\text{Sg}\) となる。よって後は \(8~\text{Sg}\), \(9~\text{Sg}\), \(10~\text{Sg}\) がちょうど支払えることを手動で確かめればよい。大した仕事ではない。

テンプレートに従った詳細な証明を次に示す:

証明 \(8~\text{Sg}\) 以上の任意の額は Inductia の硬貨でちょうど支払えることを強い数学的帰納法で示す。次の述語を帰納法の仮定とする:

総額が \((n+8)~\text{Sg}\) となる硬貨の集合が存在する。

ベースケース: \(3~\text{Sg}\) 硬貨と \(5~\text{Sg}\) 硬貨が一枚ずつあれば \(8~\text{Sg}\) なので、\(P(0)\) は成り立つ。

帰納ステップ: ある \(k \leq n\) で \(P(k)\) が成り立つと仮定し、その仮定を使って \(P(n+1)\) を証明する。場合分けを使って示す:

Case 1:

\(n + 1 = 1\) のとき、\((n + 1) + 8 = 9~\text{Sg}\) は \(3\) 枚の \(3~\text{Sg}\) 硬貨で作れる。

Case 2:

\(n + 1 = 2\) のとき、\((n + 1) + 8 = 10~\text{Sg}\) は \(2\) 枚の \(5~\text{Sg}\) 硬貨で作れる。

Case 3:

\(n + 1 \geq 3\) のとき、\(0 \leq n - 2 \leq n\) が成り立つので、強い帰納法の仮定より総額が \((n - 2) + 8~\text{Sg}\) に等しい硬貨の集合が存在する。それに \(1\) 枚の \(3~\text{Sg}\) 硬貨を加えれば、総額が \((n + 1) + 8~\text{Sg}\) である硬貨の集合が得られる。

\(n \geq 0\) より \(n + 1 \geq 1\) なので、これら以外に場合は存在しない。よって \(P(n+1)\) は全ての場合で正しく、強い数学的帰納法の原理より全ての \(n \geq 0\) で総額が \(n + 8~\text{Sg}\) となる硬貨の集合が存在する。言い換えれば、\(8~\text{Sg}\) 以上の任意の額は Inductia の硬貨でちょうど支払える。 ■

5.2.5 スタックゲーム

全世界で大流行間違いなしのエキサイティングなゲームをもう一つ紹介しよう！

スタックゲーム (stack game) と呼ばれるゲームは、\(n\) 個のブロックが積み上がったスタックが \(1\) 個ある状態から始まる。プレイヤーはスタックを分割して二つにする操作をスタックが \(n\) 個になるまで実行する。スタックを分割するたびにプレイヤーはポイントを獲得する: 高さ \(a + b\) のスタックを高さ \(a\) のスタックと高さ \(b\) のスタックに分割するとき、獲得できるポイントは \(ab\) である。各操作で得られたポイントの和が最終的なスコアとなる。どのような戦略がスコアを最大化するだろうか？

例えば、\(n = 10\) 個のボックスが積み上がったスタックから始まるゲームの進行例を図 \(\text{5.6}\) に示す。これより優れた戦略は存在するだろうか？

\[ \def\arraystretch{1.2}\begin{array}{ll} \hspace{45pt}\text{スタックの高さ} & \hspace{10pt}スコア \\ \hline \text{\large\mathstrut} \underline{10} & \\ \ \ 5\quad \underline{5} & 25 \text{ ポイント} \\ \ \ \underline{5}\quad 3 \quad 2 & 6 \\ \ \ \underline{4}\quad 3\quad 2\quad 1 & 4 \\ \ \ 2\quad \underline{3}\quad 2\quad 1\quad2 & 4 \\ \ \ \underline{2}\quad 2\quad 2\quad 1\quad 2\quad 1 & 2 \\ \ \ 1\quad \underline{2}\quad 2\quad 1\quad 2\quad 1\quad 1 & 1 \\ \ \ 1\quad 1\quad \underline{2}\quad 1\quad 2\quad 1\quad 1\quad 1 & 1 \\ \ \ 1\quad 1\quad 1\quad 1\quad \underline{2}\quad 1\quad 1\quad 1\quad 1 & 1 \\ \ \ 1\quad 1\quad 1\quad 1\quad 1\quad 1\quad 1\quad 1\quad 1\quad 1 & 1 \\ \hline \hspace{120pt}\text{最終スコア} \hspace{6pt} = & 45 \text{ ポイント} \end{array} \]

図 5.6\(n=10\) としたスタックゲームの進行例 (各行で下線の引かれたスタックが分割される)

スタックゲームの解析

強い数学的帰納法を使ってスタックゲームを解析してみよう。これからスコアがブロックの個数だけから決まると証明する ── あなたの戦略は意味を持たない！

定理 5.2.1

\(n\) 個のブロックを使うスタックゲームは、プレイヤーがどんな操作をしたとしてもスコアが \(n(n - 1)/2\) ポイントで終了する。

次に示す証明を見ると、次の点に気が付くだろう:

強い数学的帰納法のテンプレートは通常の数学的帰納法に対するものと似ている。
通常の数学的帰納法と同様に、添え字 \(n\) は調整できる。この証明はベースケースで \(P(1)\) を証明し、帰納ステップで全ての \(n \geq 1\) で \(P(1)\), \(\ldots\), \(P(n)\) の成立を仮定して \(P(n+1)\) を証明している。

証明強い数学的帰納法で示す。\(P(n)\) を述語「\(n\) 個のブロックを使うスタックゲームでは、どんな操作をしてもスコアが \(n(n-1)/2\) ポイントで終了する」と定める。

ベースケース: \(n=1\) のとき、ブロックは \(1\) 個だけなので、可能な操作は存在しない。そのためスコアは \(0\) であり、これは \(1 (1 - 1)/ 2 = 0\) に等しい。よって \(P(1)\) は成り立つ。

帰納ステップ: 全ての \(n \geq 1\) で \(P(1)\), \(\ldots\), \(P(n)\) が \(P(n+1)\) を含意すると示す必要がある。そこで \(P(1)\), \(\ldots\), \(P(n)\) が全て真と仮定し、\(n+1\) 個のブロックが積み上がったスタックを考える。最初の操作で、この唯一のスタックは高さ \(a\) のスタックと高さ \(b\) のスタックに分割される。ここで \(a + b = n + 1\) かつ \(0 < a, b < n\) が成り立つ。最終的なスコアは、この最初の操作のポイント、そして新しい二つのスタックを分割することで得られるスコアの和である:

\[ \begin{aligned} \text{総スコア} &= \text{最初の操作のポイント} \\ & \ \quad + \text{高さ } a \text{ のスタックを分割することで得られるスコア} \\ & \ \quad + \text{高さ } b \text{ のスタックを分割することで得られるスコア} \\ &= ab + \frac{a(a -1)}{2} + \frac{b(b-1)}{2} \\ &\qquad (\because\ P(a), P(b)) \\[10pt] &= \frac{(a+b)^{2} - (a+b)}{2} \\[10pt] &= \frac{(a+b)((a +b) - 1)}{2} \\[10pt] &= \frac{(n+1)n}{2} \end{aligned} \]

つまり \(P(1)\), \(P(2)\), \(\ldots\), \(P(n)\) は \(P(n+1)\) を含意する。よって強い数学的帰納法の原理より、示したい命題は成り立つ。 ■