練習問題

Frangフラング Kehryケーリーは考えを変えた。図 \(\text{5.2}\) に示した L 字タイルではなく、図 \(\text{5.7}\) に示す奇妙な形をしたタイル (およびその鏡像) を中庭に敷き詰めるべきだと彼は主張した。このタイルの敷き詰めが可能だと示すために、彼は第 5.1.5 項と同様の議論を用いた。しかし、以前に示した証明と異なり、次の証明には論理的な誤りがある。その誤りを指摘せよ。

偽の主張

Bill の銅像が任意の場所に置かれた \(2^{n} \times 2^{n}\) の中庭に図 \(\text{5.7}\) のタイルを敷き詰める方法が存在する。

誤った証明数学的帰納法で示す。\(P(n)\) を述語「Bill の銅像が任意の場所に置かれた \(2^{n} \times 2^{n}\) の中庭に図 \(\text{5.7}\) のタイルを敷き詰める方法が存在する」と定める。

ベースケース: \(n=0\) のとき中庭には Bill の銅像を置く空間しかないので、\(P(0)\) は成り立つ。

帰納ステップ: ある \(n \geq 0\) で \(P(n)\) が成り立つと仮定する。このとき、Bill の銅像が任意の場所に置かれた \(2^{n} \times 2^{n}\) の中庭に図 \(\text{5.7}\) のタイルを敷き詰める方法が存在する。\(2^{n+1} \times 2^{n+1}\) の中庭を \(4\) 個の \(2^{n} \times 2^{n}\) 領域に分割することを考える。このとき図 \(\text{5.8}\) に示すように、Bill の銅像用の空間 \(\text{B}\) を含む領域が \(1\) 個ある。それ以外の \(3\) 個の領域では Bill の銅像用の空間を図の \(\text{X}\) のように設定する。

このとき帰納法の仮定より、\(2^{n} \times 2^{n}\) の領域それぞれに図 \(\text{5.7}\) のタイルを敷き詰める方法が存在する。後は \(3\) 個の \(\text{X}\) からなる領域にタイルを敷けば、\(2^{n+1} \times 2^{n+1}\) の領域全体に対するタイルの敷き詰めが完了する。以上で \(P(n)\) を仮定して \(P(n+1)\) が示せた。よって数学的帰納法の原理より全ての非負整数 \(m\) で \(P(m)\) が成り立つ。示したい命題は Bill の銅像を中心に置く \(P(n)\) の特殊ケースだから、同じく成り立つ。 ■

問題 5.3

\(n \geq 1\) で次の等式が成り立つことを数学的帰納法で示せ:

\[ 1^{3} + 2^{3} + \cdots + n^{3} = \left( \frac{n(n+1)}{2} \right)^{\! 2} \tag{5.5}\]

第 5.1.3 項で示したテンプレートの \(5\) 個のステップを解答に含めること:

「数学的帰納法で示す」と書く。
帰納法の仮定 \(P(n)\) を定義する。
ベースケースを示す。
\(P(n) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(n+1)\) を示す
全ての \(n \geq 1\) で \(P(n)\) が成り立つと結論付ける。

問題 5.4

全ての非負整数 \(n\) と実数 \(r \neq 1\) に対する次の等式を数学的帰納法で示せ:

\[ 1 + r + r^{2} + \cdots + r^{n} = \frac{r^{n+1} - 1}{r - 1} \tag{5.6}\]

問題 5.5

全ての整数 \(n > 1\) に対する次の不等式を数学的帰納法で示せ:

\[ 1 + \frac{1}{4} + \frac{1}{9} + \cdots + \frac{1}{n^{2}} < 2 - \frac{1}{n} \tag{5.7}\]

問題 5.6

Bill の銅像が四隅のいずれかに置かれた \(2^{n} \times 2^{n}\) に L 字タイルを敷き詰める方法が存在すると示せ。定理 5.1.2 の証明で示した Bill の銅像が任意の場所にあるバージョンの問題に対する結果や証明を使ってはいけない (この問題の意図は、異なる帰納法の仮定を使っても命題を示せる場合があることの例示である)。
\(\text{(a)}\) の結果を使って、Bill の銅像が中心にあるバージョンの元の命題を証明せよ。

問題 5.7

全ての非負整数 \(n\) に対する次の等式の証明をこれまでに二種類 (第 2.2.1 項と第 5.1.4 項で) 示した:

\[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} \]

この等式と矛盾する主張を証明してみよう！

偽の主張

全ての \(n \geq 0\) で次の等式が成り立つ:

\[ 2 + 3 + 4 + \cdots + n = \frac{n(n+1)}{2} \]

誤った証明数学的帰納法で示す。\(P(n)\) を述語 \(2 + 3 + 4 + \cdots + n = n(n+1)/2\) とする。

ベースケース: \(n=0\) のとき等式の両辺は \(0\) なので \(P(0)\) は成り立つ (\(0\) 個の項の和は \(0\) である)。

帰納ステップ: 続いて全ての \(n \geq 0\) で \(P(n)\) が真のとき \(P(n+1)\) が真だと示す。\(P(n)\) が真だと仮定すると \(2 + 3 + 4 + \cdots + n = n(n+1)/2\) が成り立つ。このとき次の等式が分かる:

\[ \begin{aligned} 2 + 3 + 4 + \cdots + n + (n + 1) &= (2 + 3 + 4 + \cdots + n) + (n + 1) \\[10pt] &= \frac{n(n+1)}{2} + (n + 1) \\[10pt] &= \frac{(n+1)(n+2)}{2} \end{aligned} \]

この変形では項をまとめ、帰納法の仮定 \(P(n)\) を使用し、最後に式を整理している。ここから \(P(n)\) が真のとき \(P(n+1)\) が真だと分かる。よって数学的帰納法の原理より、全ての非負整数 \(n\) で \(P(n)\) は成り立つ。 ■

この証明の誤りを正確に指摘せよ。

問題 5.8

Fibonacciフィボナッチ数 \(F(n)\) の定義は第 5.2.2 項で示した。任意の整数 \(n \geq 1\) に対する次の等式を数学的帰納法で示せ:

\[ F(n-1) \cdot F(n+1) - F(n)^{2} = (-1)^{n} \tag{5.8}\]

問題 5.9

任意のビット列 \(\alpha\) を二進数として解釈したときの非負整数を \(\operatorname{num}(\alpha)\) と定める (先頭に並ぶ \(\texttt{0}\) は無視する)。例えば \(\operatorname{num}(\texttt{10}) = 2\) や \(\operatorname{num}(\texttt{0101}) = 5\) が成り立つ。

\(n+1\) ビット加算器 (\(n+1\)-bit adder) は長さ \(n+1\) のビット列で表された二つの整数を加算する。正確に言えば、\(n+1\) ビット加算器の入力は長さ \(n+1\) のビット列 \(\alpha_{n}\), \(\beta_{n}\)、そして \(0\) または \(1\) の値 \(c_{0}\) である。\(\alpha_{n}\), \(\beta_{n}\) の各桁を次のように定める:

\[ \begin{aligned} \alpha_{n} &::= a_{n} \ldots a_{1} a_{0} \\ \beta_{n} &::= b_{n} \ldots b_{1} b_{0} \end{aligned} \]

そして、\(n+1\) ビット加算器の出力は長さ \(n+1\) のビット列 \(\sigma_{n}\)、そして \(0\) または \(1\) の値 \(c_{n+1}\) である。\(\sigma_{n}\) の各桁を次のように定める:

\[ \sigma_{n} ::= s_{n} \ldots s_{1} s_{0} \]

入力と出力は次の制約を満たす:

\[ \operatorname{num}(\alpha_{n}) + \operatorname{num}(\beta_{n}) + c_{0} = 2^{n+1}c_{n+1} + \operatorname{num}(\sigma_{n}) \tag{5.9}\]

\(n+1\) ビット加算器を実装する単純なデジタル回路として、\(n+1\) ビットのリップルキャリー (ripple-carry)回路がある。この回路は次の \( 2(n+1) + 1\) ビットを入力に受け取る:

\[ a_{n},\ \ldots,\ a_{1},\ a_{0},\ b_{n},\ b_{1},\ b_{0},\ c_{0} \]

そして次の \(n+2\) ビットを出力する:

\[ c_{n+1},\ s_{n},\ \ldots,\ s_{1},\ s_{0} \]

問題 3.6 で見たように、リップルキャリー回路は次の式で表される:

\[ s_{i} ::= a_{i} \ \operatorname{\text{\footnotesize XOR}}\ b_{i} \ \operatorname{\text{\footnotesize XOR}}\ c_{i} \qquad\qquad\qquad\qquad\qquad\quad \tag{5.10}\]

\[ c_{i+1} ::= (a_{i} \ \operatorname{\text{\footnotesize AND}} \ b_{i}) \ \operatorname{\text{\footnotesize OR}}\ (a_{i} \ \operatorname{\text{\footnotesize AND}} \ c_{i}) \ \operatorname{\text{\footnotesize OR}}\ (b_{i} \ \operatorname{\text{\footnotesize AND}} \ c_{i}) \tag{5.11}\]

ここで \(0 \leq i \leq n\) である。\(1\) が \(\textbf{T}\) に対応し、\(0\) が \(\textbf{F}\) に対応する慣習を利用している。

全ての非負整数 \(n\) に対して、式 \(\text{(5.10)}\) と式 \(\text{(5.11)}\) が次の等式を意味すると示せ:

\[ a_{n} + b_{n} + c_{n} = 2c_{n+1} + s_{n} \tag{5.12}\]
\(n+1\) ビットのリップルキャリー回路が実際に \(n+1\) ビット加算器である (入力と出力が等式 \(\text{(5.9)}\) を満たす) ことを \(n\) に関する数学的帰納法で示せ。

ヒント: 整数の二進表現の定義から次の等式が分かる:

\[ \operatorname{num}(\alpha_{n+1}) = \alpha_{n+1} 2^{n+1} + \operatorname{num}(\alpha_{n}) \tag{5.13}\]

問題 5.10

正三角形分割 (divided equilateral triangle, DET) は次のように定義される¹:

単一の正三角形は DET である。その単位部分正三角形 (unit subtriangle) はそれ自身と定義される。
\(T\) が DET のとき、\(4\) 個の \(T\) を図 \(\text{5.9}\) のように並べた正三角形 \(T^{\prime}\) も DET である。このとき \(T^{\prime}\) の単位部分正三角形はそれに含まれる \(4\) 個の \(T\) の単位部分正三角形と定義される。

4 個の DET T から構成される DET T^{\prime} — 図 5.9\(4\) 個の DET \(T\) から構成される DET \(T^{\prime}\)

3 個の DET から構成される台形 — 図 5.10\(3\) 個の DET から構成される台形

DET の長さ (length) を、DET の底辺に並んだ単位部分正三角形の個数と定義する。DET の長さに関する数学的帰納法を使って、DET に含まれる単位部分正三角形の個数が長さの二乗に等しいと示せ。
DET から隅にある単位正三角形を \(1\) 個取り除いた図形には、\(3\) 個の単位正三角形からなる台形 (図 \(\text{5.10}\)) を敷き詰められると示せ。

問題 5.11

『情報科学のための数学』のマスコット理論カバくんTheory Hippopotamusは、ご褒美でもらった単位正方形のタイルで遊んでいたときに驚くべき発見をした。

理論カバくんは図 \(\text{5.11}\) \(\text{(a)}\) に示すお気に入りの正方形タイルを床に置き、その外周の長さが \(4\) で偶数であることを確認した。続いて、彼はその横に正方形タイルをもう一つ置いて図 \(\text{5.11}\) \(\text{(b)}\) の図形を作成した。そして、この図形の外周の長さも \(6\) で偶数であることに彼は気が付いた (図では外周が太線で示されている)。理論カバくんは既存の図形と少なくとも一つの辺を共有するように何もない場所に新しい正方形タイルを配置することを繰り返し、図 \(\text{5.11}\) \(\text{(c)}\) の図形を完成させた。この図形の外周の長さも \(36\) で偶数であることを彼は発見した。

我々の勇敢な大型動物は奇妙なパターンを発見したところで途方に暮れてしまった。正方形タイルの個数に関する数学的帰納法を使って、理論カバくんが正方形タイルをどれだけどのように配置したとしても外周の長さは常に偶数だと示せ。

問題 5.12

\(n\) 個の集合の和集合に対する共通部分の分配律を数学的帰納法で示せ:

\[ A \cap \bigcup_{i=1}^{n} B_{i} = \bigcup_{i=1}^{n}\ (A \cap B_{i}) \tag{5.14}\]

ヒント: \(n=2\) の場合は定理 4.1.2 で示した。

問題 5.13

Kochコッホ雪片 (Koch snowflake) と呼ばれる幾何学図形 \(S_{0}\), \(S_{1}\), \(\ldots\) の興味深い構築方法は次の通りである。図形 \(S_{0}\) を各辺の長さが \(1\) の正三角形とする。\(S_{n}\) から \(S_{n+1}\) を作るには、\(S_{n}\) の各辺を三分割し、中間部分を図 \(\text{5.12}\) のように同じ長さの二つの辺で置き換える。

S_{0}, S_{1}, S_{2}, S_{3} — 図 5.12\(S_{0}\), \(S_{1}\), \(S_{2}\), \(S_{3}\)

\(S_{n}\) の面積を \(a_{n}\) とする。\(a_{0}\) は各辺の長さが \(1\) の正三角形の面積に等しいので、高校レベルの幾何学から \(a_{0} = \sqrt{3}/4\) が分かる。

数学的帰納法を使って、\(n\) 番目の Koch 雪片の面積に関する次の等式が全ての \(n \geq 0\) で成り立つと示せ:

\[ a_{n} = a_{0} \left( \frac{8}{5} - \frac{3}{5} \left( \frac{4}{9} \right)^{\! n} \right) \tag{5.15}\]

問題 5.14

全ての非負整数 \(n\) に対する次の等式を数学的帰納法で示せ:

\[ \sum_{k=1}^{n} k \cdot k! = (n+1)! - 1 \tag{5.16}\]

問題 5.15

全ての非負整数 \(n\) に対する次の等式を数学的帰納法で示せ:

\[ 0^{3} + 1^{3} + 2^{3} + \cdots + n^{3} = \left( \frac{n(n+1)}{2} \right)^{\! 2} \]

この等式そのものを帰納法の仮定 \(P(n)\) として利用せよ。

問題 5.16

非負整数 \(n\) に関する述語 \(P(n)\) が次の関係を満たすと仮定する:

\[ \forall k.\ P(k) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(k+2) \tag{5.17}\]

このとき、次に示す述語論理式の中には一部の \(P\) に対して真になるもの、全ての \(P\) に対して真になるもの、そしてどんな \(P\) に対しても偽になるものが存在する。それぞれの述語論理式がどれかを解答し、その理由を簡単に説明せよ。

\(\forall n \geq 0.\ P(n)\)
\(\operatorname{\text{\footnotesize NOT}} (P(0)) \ \operatorname{\text{\footnotesize AND}} \ \forall n \geq 1.\ P(n)\)
\(\forall n \geq 0.\ \operatorname{\text{\footnotesize NOT}} (P(n))\)
\((\forall n \leq 100.\ P(n)) \ \operatorname{\text{\footnotesize AND}} \ (\forall n > 100.\ P(n)) \)
\((\forall n \leq 100.\ \operatorname{\text{\footnotesize NOT}} (P(n))) \ \operatorname{\text{\footnotesize AND}} \ (\forall n > 100.\ P(n))\)
\(P(0) \ \operatorname{\text{\footnotesize IMPLIES}}\ \forall n.\ P(n+2)\)
\((\exists n.\ P(2n)) \ \operatorname{\text{\footnotesize IMPLIES}}\ \forall n.\ P(2n+2)\)
\(P(1) \ \operatorname{\text{\footnotesize IMPLIES}}\ \forall n.\ P(2n+1)\)
\((\exists n.\ P(2n)) \ \operatorname{\text{\footnotesize IMPLIES}}\ \forall n.\ P(2n + 2)\)
\(\exists n, \exists m > n.\ P(2n) \ \operatorname{\text{\footnotesize AND}} \ \operatorname{\text{\footnotesize NOT}} (P(2m))\)
\((\exists n.\ P(n)) \ \operatorname{\text{\footnotesize IMPLIES}}\ \forall n, \exists m > n.\ P(m)\)
\(\operatorname{\text{\footnotesize NOT}} (P(0)) \ \operatorname{\text{\footnotesize IMPLIES}}\ \forall n.\ \operatorname{\text{\footnotesize NOT}} (P(2n))\)

問題 5.17

命題変数 \(P_{1}\), \(P_{2}\), \(\ldots\), \(P_{n}\), \(\ldots\) を含む命題論理式 \(F_{1}\), \(F_{2}\), \(\ldots\), \(F_{n}\), \(\ldots\) を次のように定める:

\[ \small\begin{aligned} &F_{1} (P_{1}) &&::= P_{1} \\ &F_{2} (P_{1}, P_{2}) &&::= P_{1} \ \operatorname{\text{\scriptsize IMPLIES}}\ P_{2} \\ &F_{3} (P_{1}, P_{2}, P_{3}) &&::= (P_{1} \ \operatorname{\text{\scriptsize IMPLIES}}\ P_{2}) \ \operatorname{\text{\scriptsize IMPLIES}}\ P_{3} \\ &F_{4} (P_{1}, P_{2}, P_{3}, P_{4}) &&::= ((P_{1} \ \operatorname{\text{\scriptsize IMPLIES}}\ P_{2}) \ \operatorname{\text{\scriptsize IMPLIES}}\ P_{3}) \ \operatorname{\text{\scriptsize IMPLIES}}\ P_{4} \\ &F_{5} (P_{1}, P_{2}, P_{3}, P_{4}, P_{5}) &&::= (((P_{1} \ \operatorname{\text{\scriptsize IMPLIES}}\ P_{2}) \ \operatorname{\text{\scriptsize IMPLIES}}\ P_{3}) \ \operatorname{\text{\scriptsize IMPLIES}}\ P_{4}) \ \operatorname{\text{\scriptsize IMPLIES}}\ P_{5} \\ &&& \vdots \end{aligned} \]

\(F_{n}(P_{1}, P_{2}, \ldots, P_{n})\) が真になるような \(P_{1}\), \(P_{2}\), \(\ldots\), \(P_{n}\) に対する異なる真理値割り当ての個数を \(T_{n}\) と定める。例えば \(F_{2}(P_{1}, P_{2})\) が真になる \(P_{1}\), \(P_{2}\) に対する真理値割り当ては \(3\) 個あるので、\(T_{2} = 3\) が分かる:

\[ \def\arraystretch{1.2}\begin{array}{cc|c} P_{1} & P_{2} & F_{2}(P_{1}, P_{2}) \\ \hline \textbf{T} & \textbf{T} & \textbf{T} \\ \textbf{T} & \textbf{F} & \textbf{F} \\ \textbf{F} & \textbf{T} & \textbf{T} \\ \textbf{F} & \textbf{F} & \textbf{T} \end{array} \]

全ての正整数 \(n\) で次の等式が成り立つ理由を説明せよ:

\[ T_{n+1} = 2^{n+1} - T_{n} \tag{5.18}\]
全ての正整数 \(n\) で次の等式が成り立つことを数学的帰納法で示せ:

\[ T_{n} = \frac{2^{n+1} + (-1)^{n}}{3} \tag{\(\ast\)} \]

問題 5.18

\(0\), \(1\), \(\ldots\), \(n-1\) の数字が書かれた \(n\) 個の封筒がある。封筒 \(0\) には \(2^{0} = 1\) ドルが含まれ、封筒 \(1\) には \(2^{1}\) ドルが含まれ、以下同様に封筒 \(n-1\) には \(2^{n-1}\) ドルが含まれる。次の述語を \(P(n)\) と定める:

全ての非負整数 \(k < 2^{n}\) に対して、含まれる金額の合計がちょうど \(k\) ドルに等しい封筒の集合が存在する。

全ての整数 \(n \geq 1\) で \(P(n)\) が成り立つことを数学的帰納法で示せ。

問題 5.19

全ての整数 \(n \geq 1\) で次の等式が成り立つことを数学的帰納法で示せ:

\[ 1 \cdot 2\ +\ 2 \cdot 3\ +\ 3 \cdot 4\ + \cdots +\ n(n+1) = \frac{n(n+1)(n+2)}{3} \tag{5.19}\]

問題 5.20

\(k\) ビット \(\texttt{AND} \) 回路とは、\(k\) 個の \(0\)-\(1\) 値² \(d_{0}\), \(d_{1}\), \(\ldots\), \(d_{k-1}\) を入力に受け取り、次の \(0\)-\(1\) 値を出力するデジタル回路である:

\[ d_{0} \ \operatorname{\text{\footnotesize AND}} \ d_{1} \ \operatorname{\text{\footnotesize AND}} \ \cdots \ \operatorname{\text{\footnotesize AND}} \ d_{k-1} \]

\(k\) ビット \(\texttt{OR}\) 回路も同様に (\(\operatorname{\text{\footnotesize AND}}\) を \(\operatorname{\text{\footnotesize OR}}\) に置き換えたものとして) 定義される。以降では「\(k\) ビット \(\texttt{AND}\) 回路」「\(k\) ビット \(\texttt{OR}\) 回路」を省略して「\(\texttt{AND}\) 回路」「\(\texttt{OR}\) 回路」と呼ぶ。

\texttt{AND} 回路と \texttt{NOT} ゲートから作った \texttt{OR} 回路 — 図 5.13\(\texttt{AND}\) 回路と \(\texttt{NOT}\) ゲートから作った \(\texttt{OR}\) 回路

\(\texttt{OR}\) 回路を使いたい状況で \(\texttt{AND}\) 回路と \(\texttt{NOT}\) ゲートしか利用できないとする。\(\texttt{NOT}\) ゲートはインバーター (inverter) とも呼ばれ、一つの \(0\)-\(1\) 値 \(x\) を入力に受け取り、一つの \(0\)-\(1\) 値 \(\operatorname{\text{\footnotesize NOT}} (x)\) を出力する。これらを \(\texttt{OR}\) 回路に変換するには、図 \(\text{5.13}\) に示すように全ての入力を \(\texttt{NOT}\) ゲートに通してから \(\texttt{AND}\) 回路に入力し、\(\texttt{AND}\) 回路の出力を \(\texttt{NOT}\) に通せばよい。この構成が正しい理由を簡単に説明せよ。

大規模なデジタル回路は小規模なデジタル回路をコンポーネントとして利用し、それらを接続することで作成される。最も基礎的なコンポーネントの一つが \(2\) 入力 \(1\) 出力の \(\texttt{AND}\) ゲートであり、このゲートの出力は入力の \(\operatorname{\text{\footnotesize AND}}\) に等しい。冒頭で定義した用語を使えば、\(\texttt{AND}\) ゲートは \(2\) ビット \(\texttt{AND}\) 回路に等しい。

\(\texttt{AND}\) ゲートから大規模な \(\texttt{AND}\) ゲートを作る方法はいくつかある。例えば、\(3\) 個の \(\texttt{AND}\) ゲートから \(4\) ビット \(\texttt{AND}\) 回路を作る方法を図 \(\text{5.14}\) に示す。

一般に、深さ \(n\) の樹状 \(\texttt{AND}\) 回路 (以降では深さ-\(n\) 回路と呼ぶ) は \(2^{n}\) 個の入力を持ち、二つの深さ-\((n-1)\) 回路と一つの \(\texttt{AND}\) ゲートから構成される。図 \(\text{5.15}\) に示すように、\(2^{n}\) 個の入力は等分されて二つの深さ-\((n-1)\) 回路に入力され、それらの出力が \(\texttt{AND}\) ゲートに入力される。図 \(\text{5.14}\) に示した \(4\) ビット \(\texttt{AND}\) 回路は深さ-\(2\) 回路でもある。深さ-\(1\) 回路は単一の \(\texttt{AND}\) ゲートと定義される。

深さ-\(n\) 回路に含まれる \(\texttt{AND}\) ゲートの個数を \(\text{gate\#}(n)\) と定義する。全ての \(n \geq 1\) で次の等式が成り立つことを数学的帰納法で示せ:

\[ \text{gate\#}(n) = 2^{n} - 1 \tag{5.20}\]

問題 5.21

本書では非負整数に関する述語の証明で利用できる重要な原理をいくつか見た:

数学的帰納法の原理
強い数学的帰納法の原理
整列原理

これらの原理を表した推論規則を次の中からそれぞれ選べ (存在するとは限らない)。

\[ \frac{P(0), \quad \forall m.\ (\forall k \leq m.\ P(k)) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(m+1)}{\forall n.\ P(n)} \]
\[ \frac{P(b), \quad \forall k \geq b.\ P(k) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(k+1)}{\forall k \geq b.\ P(k)} \]
\[ \frac{\exists n. P(n)}{\exists n.\ (P(m) \ \operatorname{\text{\footnotesize AND}} \ (\forall k.\ P(k) \ \operatorname{\text{\footnotesize IMPLIES}}\ k \geq m))} \]
\[ \frac{P(0),\quad \forall k > 0.\ P(k) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(k+1)}{\forall n.\ P(n)} \]
\[ \frac{\forall m.\ (\forall k < m.\ P(k)) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(m)}{\forall n.\ P(n)} \]

問題 5.22

Fibonacciフィボナッチ数 \(F(n)\) の定義は第 5.2.2 項で示した。次の誤った証明に含まれる論理的に誤った文を正確に指摘せよ。

偽の主張

全ての Fibonacci 数は偶数である。

誤った証明以降の議論で使われる変数 \(n\), \(m\), \(k\) は全て非負整数の値を取ると定める。\(\operatorname{Even}(n)\) を述語「\(F(n)\) は偶数」と定義する。\(\operatorname{Even}(n)\) を帰納法の仮定とする強い数学的帰納法で証明する。

ベースケース: \(F(0) = 0\) は偶数より \(\operatorname{Even}(0)\) は成り立つ。

帰納ステップ: 強い帰納法の仮定「\(0 \leq k \leq n\) を満たす全ての \(k\) で \(\operatorname{Even}(k)\)」を仮定する。この上で \(\operatorname{Even}(n+1)\) を示せばよい。

強い帰納法の仮定より \(\text{Even(n)}\) と \(\operatorname{Even}(n-1)\) が成り立つので、\(F(n)\) と \(F(n-1)\) はどちらも偶数である。一方、定義より \(F(n+1)\) は \(F(n) + F(n-1)\) に等しく、これは二つの偶数の和である。つまり \(F(n+1)\) は偶数であり、\(\operatorname{Even}(n+1)\) が成り立つ。

よって強い数学的帰納法の原理より全ての非負整数 \(m\) で \(F(m)\) は偶数である。 ■

問題 5.23

Aliceアリスは述語 \(P(n)\) が特定の非負整数に対して成り立つことを示そうとしている。彼女は非負整数 \(n = 0, 1, \ldots\) に対する次の関係を証明できた:

\[ P(n) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(n+3) \]

Alice がさらに \(P(5)\) の成立を証明できたとする。このとき、正しいと示せる命題を次の中から全て選べ:
1. 全ての \(n \geq 5\) で \(P(n)\) が成り立つ
2. 全ての \(n \geq 5\) で \(P(3n)\) が成り立つ
3. \(n = 8, 11, 14, \ldots\) で \(P(n)\) が成り立つ
4. \(n < 5\) では \(P(n)\) が成り立たない
5. \(\forall n.\ P(3n+5)\)
6. \(\forall n > 2.\ P(3n-1)\)
7. \(P(0) \ \operatorname{\text{\footnotesize IMPLIES}}\ \forall n.\ P(3n + 2)\)
8. \(P(0) \ \operatorname{\text{\footnotesize IMPLIES}}\ \forall n.\ P(3n)\)
全ての \(n > 5\) で \(P(n)\) が成り立つと結論付けるために Alice が証明する必要がある命題を次から選べ:
1. \(P(5)\)
2. \(P(5)\), \(P(6)\)
3. \(P(0)\), \(P(1)\), \(P(2)\)
4. \(P(5)\), \(P(6)\), \(P(7)\)
5. \(P(2)\), \(P(4)\), \(P(5)\)
6. \(P(2)\), \(P(4)\), \(P(6)\)
7. \(P(3)\), \(P(5)\), \(P(7)\)

問題 5.24

\(12\) セント以上の任意の郵便料金は、\(4\) セント切手と \(5\) セント切手だけを使ってちょうど支払えると示せ。

問題 5.25

Fibonacciフィボナッチ数 \(F(n)\) の定義は第 5.2.2 項で示した。強い数学的帰納法を使って、フィボナッチ数を表す次の閉形式の式³が正しいことを証明せよ:

\[ F(n) = \frac{p^{n} - q^{n}}{\sqrt{5}} \]

ここで \(p = (1 + \sqrt{5}) / 2\) および \(q = (1 - \sqrt{5}) / 2\) である。

ヒント: \(p\) と \(q\) は \(x^{2} - x - 1 = 0\) の根であり、\(p^{2} = p+1\) と \(q^{2} = q + 1\) が成り立つ。

問題 5.26

数列 \((a_{0}, a_{1}, \ldots, a_{n})\) が広義減少とは、\(n\) 未満の任意の添え字 \(i\) で \(a_{i} \geq a_{i+1}\) が成り立つことを言う。この定義より、長さ \(1\) の任意の数列は広義減少である。

「\(2\) 以上の任意の整数は素数からなる一意な広義減少列の積 (product of a unique weakly decreasing sequence of primes, pusp) である」という重要な事実の誤った証明を次に示す。どこが間違っているのか指摘せよ。

補題

\(2\) 以上の任意の整数は pusp である。

例えば \(252 = 7 \cdot 3 \cdot 3 \cdot 2 \cdot 2\) であり、これ以外に素数からなる広義減少列であって積が \(252\) に等しいものは存在しない。

誤った証明 \(P(n)\) を述語「\(n\) は pusp」として、これから全ての \(n \geq 2\) で \(P(n)\) が成り立つことを強い数学的帰納法で示す。\(P(n)\) を帰納法の仮定とする。

ベースケース: \(2\) は素数 \(2\) だけからなる長さ \(1\) の広義減少列の積であり、これ以外に素数からなる広義減少列であって積が \(2\) に等しいものは明らかに存在しない。よって \(P(2)\) は成り立つ。

帰納ステップ: \(n\) を \(2\) 以上の整数とする。\(2 \leq i < n + 1\) を満たす全ての整数 \(i\) が pusp だと仮定する。これから \(P(n+1)\) が成り立つこと、つまり \(n+1\) も pusp だと示す。場合分けを用いる:

Case 1:

\(n+1\) が素数なら、素数 \(n+1\) だけからなる広義減少列の積は \(n+1\) に等しい。さらに、素数 \(n+1\) に約数は存在しないので、この数列以外に積が \(n+1\) に等しい素数からなる広義減少列は存在しない。よって、この場合は \(P(n+1)\) が成り立つ。

Case 2:

\(n+1\) が素数でないなら、\(n+1 = km\) を満たす整数 \(k\), \(m\) が存在する。このとき \(2 \leq k, m < n + 1\) が成り立つので、強い帰納法の仮定より \(k\) と \(m\) は pusp である。積が \(k\) および \(m\) に等しい素数からなる二つの広義減少列を順序が保たれるように組み合わせれば、積が \(n+1\) に等しい素数からなる一意な広義減少列が得られる。よって \(n+1\) は pusp であり、この場合でも \(P(n+1)\) は成り立つ。

両方の場合で \(P(n+1)\) が示せたので、強い数学的帰納法の原理より全ての \(n \geq 2\) で \(P(n)\) が成り立つことの証明が完了した。 ■

問題 5.27

\(k\) 個のブロックを積み上げたスタック \(S\) のポテンシャル (potential) \(p(S)\) を \(k(k-1)/2\) と定める。スタックの集合 \(A\) のポテンシャル \(p(A)\) を \(A\) に含まれるスタックのポテンシャルの和と定める。

スタックゲームのスコアに関する定理 5.2.1 を一般化し、スタックの集合 \(A\) から始めて任意の操作の列を適用した結果のスタックの集合を \(B\) とする。このとき \(p(A) \geq p(B)\) であり、適用した操作のポイントの和は \(p(A) - p(B)\) だと示せ。

ヒント: \(A\) を \(B\) にするまでに適用された操作の個数に関する数学的帰納法を使う。

問題 5.28

\(n \geq 1\) 人の集まりを \(4\) 人または \(7\) 人のグループに分割することを考える。余りを出さずにグループ分けが可能な \(n\) はどんな値か答えよ。その解答が正しいことを数学的帰納法で示せ。

問題 5.29

次に示す補題は正しいものの、それに続く証明には誤りが含まれる。証明に含まれる正当化できないステップを正確に指摘し、その理由を説明せよ。

補題

任意の素数 \(p\) と正整数 \(n\), \(x_{1}\), \(x_{2}\), \(\ldots\), \(x_{n}\) に対して、もし \(p \; | \; x_{1}x_{2}\ldots x_{n}\) なら \(p \; | \; x_{i}\) を満たす \(1 \leq i \leq n\) が存在する。

誤った証明 \(n\) に関する強い数学的帰納法で示す。帰納法の仮定 \(P(n)\) を述語「正整数 \(n\) で示すべき補題が成り立つ」とする。

ベースケース: \(p \; | \; x_{1}\) なら \(i=1\) とすれば \(p \; | \; x_{i}\) となる。よって \(P(1)\) は成り立つ。

帰納ステップ: 全ての \(k \leq n\) で \(P(k)\) が成立すると仮定する。これから \(P(n+1)\) を示す。

\(p \; | \; x_{1}x_{2}\cdots x_{n+1}\) が成り立つと仮定する。\(y_{n} = x_{n}x_{n+1}\) と定めると \(x_{1}x_{2}\cdots x_{n+1} = x_{1}x_{2} \cdots x_{n-1}y_{n}\) である。この等式の右辺は \(n\) 個の項の積だから、強い帰納法の仮定より \(p\) を割り切る項が存在する。もし \(p \; | \; x_{i}\) を満たす \(i < n\) が存在するなら、それが探していた \(i\) である。そうでないなら \(p \; | \; y_{n}\) だが、\(y_{n}\) は \(x_{n}\) と \(x_{n+1}\) の積なので、帰納法の仮定をもう一度使えば \(i = n\) または \(i = n + 1\) で \(p \; | \; x_{i}\) だと分かる。 ■

問題 5.30

Fibonacciフィボナッチ数 \(F(n)\) の定義は第 5.2.2 項で示した。\(F(n)\) が満たす驚くような等式が多くある。そんな等式の例を次に示す:

\[ F(0)^{2} + F(1)^{2} + \cdots + F(n)^{2} = F(n)F(n+1) \tag{5.21}\]

全ての非負整数 \(n\) で等式 \(\text{(5.21)}\) が正しいことを数学的帰納法で示せ。等式 \(\text{(5.21)}\) そのものを帰納法の仮定 \(P(n)\) として使うこと。

問題 5.1

問題 5.2

問題 5.3

問題 5.4

問題 5.5

問題 5.6

問題 5.7

問題 5.8

問題 5.9

問題 5.10

問題 5.11

問題 5.12

問題 5.13

問題 5.14

問題 5.15

問題 5.16

問題 5.17

問題 5.18

問題 5.19

問題 5.20

問題 5.21

問題 5.22

問題 5.23

問題 5.24

問題 5.25

問題 5.26

問題 5.27

問題 5.28

問題 5.29

問題 5.30

問題 5.31

問題 5.32

問題 5.33