5.1 通常の数学的帰納法

数学的帰納法を理解するために、教授がキャンディーのぎっしり詰まった袋を講義に持ってきたと想像してほしい。彼女は学生を一列に並べ、次のルールでキャンディーを学生に配ると宣言した:

列の先頭にいる学生はキャンディーを受け取る。
ある学生がキャンディーを受け取るなら、その学生の後ろにいる学生もキャンディーを受け取る。

列に並んだ学生に (当然) \(0\) から始まる番号を順に割り当てたとしよう。このとき、教授が宣言した二番目の短いルールは次の命題全てを意味すると理解できる:

もし学生 \(0\) がキャンディーを受け取るなら、学生 \(1\) もキャンディーを受け取る。
もし学生 \(1\) がキャンディーを受け取るなら、学生 \(2\) もキャンディーを受け取る。
もし学生 \(2\) がキャンディーを受け取るなら、学生 \(3\) もキャンディーを受け取る。

\[ \vdots \]

もちろん、これらの命題は数学的な言葉で簡潔に表現できる:

全ての非負整数 \(n\) について、もし学生 \(n\) がキャンディーを受け取るなら、学生 \(n + 1\) もキャンディーを受け取る。

あなたは学生 \(17\) だとしよう。上記のルールの下であなたはキャンディーをもらえるだろうか？一つ目のルールによれば、列の先頭にいる学生 \(0\) はキャンディーを受け取る。よって二つ目のルールより、学生 \(1\) もキャンディーを受け取る。すると同じく二つ目のルールより、学生 \(2\) もキャンディーを受け取る。以降も同様であり、二つ目のルールを \(17\) 回適用するとキャンディーはあなた (学生 \(17\)) にも渡されると分かる！もちろん、このルールの下では列に並んだ全ての学生がキャンディーを受け取る。

5.1.1 通常の数学的帰納法

上記の二つのルールから「列に並んだ学生は全員キャンディーを受け取る」を導いた推論は本質的に数学的帰納法である。

数学的帰納法の原理 (induction principle)

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

\(P(0)\) が真
全ての非負整数 \(n\) で \(P(n) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(n + 1)\) が真

このとき、全ての非負整数 \(m\) で \(P(m)\) が成り立つ。

本節では数学的帰納法の変種をいくつか示すので、上記の数学的帰納法を通常の数学的帰納法 (ordinary induction) と呼ぶことにする。これは第 1.4.1 項で紹介した形式を使えば次のように表せる:

推論規則

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

この通常の数学的帰納法を表す推論規則の正しさは、列に並んだ学生全員がキャンディーを受け取る事実と同じように直感的に理解できると思う。先ほどのキャンディーの例から、通常の数学的帰納法の健全性を当然のものとして証明なしに仮定してよい理由を理解できることを願っている。実際、この推論規則はさらに基礎的な原理から導くのが難しいほどに明らかであることを第 5.3 節で見る。一方で明らかでないのは応用できる領域の広さである。

5.1.2 見慣れた等式を使った例

次の等式 \(\text{(5.1)}\) は \(n\) 以下の非負整数の和を計算する公式である。この等式は全ての非負整数 \(n\) に対して成り立つので、数学的帰納法で示せる可能性を持った命題である。この等式は以前に整列原理を使って証明した (定理 2.2.1) ものの、ここでは数学的帰納法による (数学的帰納法の原理を使った) 証明を示す。

定理 5.1.1

全ての \(n \in \mathbb{N}\) で次の等式が成り立つ:

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

証明この定理を数学的帰納法で証明するために、等式 \(\text{(5.1)}\) が成り立つことを述語 \(P(n)\) と定める。このとき定理 5.1.1 は「全ての \(n \in \mathbb{N}\) で \(P(n)\) が成り立つ」と言い換えられる。これで準備は整った: 後は数学的帰納法の原理を使えばこの結論が得られる。そのために必要なのは次の二つの命題の証明である:

\(P(0)\) が真
全ての \(n \in \mathbb{N}\) で \(P(n) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(n+1) \) が真

つまり、私たちの仕事はこの二つの命題の証明に単純化された。

一つ目の命題は \(0\) 個の項の和を \(0\) と定める慣習から従う。つまり \(P(0)\) は \(0\) 個の項の和が \(0(0+1)/2 = 0\) に等しいと主張しているので、正しい。

二つ目の命題の証明は少し複雑になる。ただ、第 1.5 節で説明した任意の論理的含意の恒真性を証明するときの基本的な戦略を思い出してほしい: 左側の命題を仮定して、それを使って右側の命題を証明すればよい。今考えている論理的含意では \(P(n)\) ── 等式 \(\text{(5.1)}\) ── を仮定できる。その上で証明すべきは \(P(n+1)\) である。つまり、次の等式を示す必要がある:

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

二つの等式は非常に似ている。実際、等式 \(\text{(5.1)}\) の両辺に \((n + 1)\) を加えて整理すると等式 \(\text{(5.2)}\) が得られる:

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

よって、もし \(P(n)\) が真なら \(P(n+1)\) も真である。この議論は任意の非負整数 \(n\) で成り立つから、証明が必要とされていた二つ目の命題も証明できた。従って数学的帰納法の原理より、任意の非負整数 \(m\) で \(P(m)\) は成り立つ。これで定理 5.1.1 は証明された。 ■

5.1.3 数学的帰納法を使う証明のテンプレート

定理 5.1.1 の証明は非常に簡単だったものの、数学的帰納法を使う最も複雑な証明と同様の構造を持つ。テンプレートとしてまとめると、数学的帰納法を使う証明は次の五つのステップからなる:

「数学的帰納法を使う」と書く: 最初に証明の全体的な流れを伝えておけば、読者は証明を追いやすくなる。
適切な述語 \(P(n)\) を明確に定義する: この述語 \(P(n)\) は帰納法の仮定 (induction hypothesis) と呼ばれる。以降の議論では全ての非負整数 \(n\) で \(P(n)\) が成り立つことが証明される。数学的帰納法を使う証明で最も重要なのは帰納法の仮定を明確に定義する部分である場合が多い。そして学生が書いた証明が分かりにくい原因として最も多いのは帰納法の仮定が曖昧なことである。

最も単純なケースでは、等式 \(\text{(5.1)}\) の証明と同じように、帰納法の仮定が示したい命題と一致する。帰納法の仮定に複数の変数が含まれているために、数学的帰納法の「\(n\)」として振る舞う変数を明示しなければならない場合もある。
\(P(0)\) が成り立つと示す: この証明は簡単な場合が多い ── 上述の例でも簡単だった。この部分をベースケース (base case) やベースステップ (base step) と呼ぶ。
全ての非負整数 \(n\) で \(P(n)\) なら \(P(n+1)\) だと示す: この部分を帰納ステップ (induction step) と呼ぶ。どんなときでも基本的な流れは「\(P(n)\) を仮定し、それを利用して \(P(n+1)\) を示す」で変わらない。二つの命題は見た目が似ているはずだが、そのギャップを埋めるのが簡単とは限らない。証明は \(n\) を任意の非負整数と仮定する必要がある。なぜなら、次の含意が全て正しいと示す必要があるからである:

\[ P(0) \rightarrow P(1),\quad P(1) \rightarrow P(2), \quad P(2) \rightarrow P(3),\quad \ldots \]
数学的帰納法を適用する: 二つの命題が証明されれば、数学的帰納法の原理から \(P(n)\) が全ての非負整数 \(n\) で成り立つと結論できる。これは数学的帰納法を使う全ての証明に共通の最終ステップであり非常に標準的なので、明示的に言及されないこともよくある。

証明では「ベースケース」と「帰納ステップ」のラベルを必ず付けたほうがよい。そうすれば議論の流れが明確になり、重要なステップ (例えばベースケースの確認) を見逃す可能性が低下する。

5.1.4 余計な説明を省いた証明

第 5.1.2 項で示した定理 5.1.1 の証明に間違っているところはない。ただ、数学的帰納法を使う典型的な証明には含まれない不必要な説明が多く含まれている。そこで、教科書などでよく見る形式 (そして、あなたが答案に書くべき形式) に書き直した証明を次に示す。

簡潔に書き換えた定理 5.1.1 の証明数学的帰納法で示す。等式 \(\text{(5.1)}\) を帰納法の仮定 \(P(n)\) とする。

ベースケース: \(n=0\) のとき等式 \(\text{(5.1)}\) の両辺は \(0\) なので、\(P(0)\) は成り立つ。

帰納ステップ: \(P(n)\) が成り立つと仮定する。つまり、ある非負整数 \(n\) で等式 \(\text{(5.1)}\) が成り立つと仮定する。等式 \(\text{(5.1)}\) の両辺に \(n + 1\) を加えると、次の関係が分かる:

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

つまり \(P(n+1)\) は成り立つ。

従って数学的帰納法の原理より、\(P(n)\) は全ての非負整数 \(n\) で成り立つ。 ■

この数学的帰納法による証明に不満を覚えた読者もいるかもしれない。この証明を見ても等式の正しさが直感的に理解できるわけではないし、そもそも等式 \(\text{(5.1)}\) の右辺にある式がどうやって得られたのか説明されない。これは数学的帰納法の弱みでもあれば強みでもある。証明を見ても何も洞察が得られないと考えれば弱みであるのに対して、証明を通して命題の正しさを読者に納得させるとき洞察が必要ないと考えれば強みである。

5.1.5 さらに難しい例

後に有名になる MIT の Stataスタタ Centerセンターの開発プロジェクトでは、予算を大幅に超えて積み上がり続けるコストをどうにかするために過激な資金調達のアイデアがいくつか提案された。噂された計画の一つは次の通りである。正方形の中庭を作り、それを小さな正方形に分割する。具体的には、\(n\) を何らかの非負整数として中庭の各辺を \(2^{n}\) 個に等分し、向かい合った分割点を結ぶことで格子状に中庭を分割する。そして中心¹にある正方形の一つに巨額の寄付金が期待できる大資産家 ── プロジェクト関係者は秘密裏に Bill と呼んだ ── の銅像を設置することが計画された。\(n=3\) とした場合の中庭の様子を図 \(\text{5.1}\) に示す。

中庭: n = 3 とした場合の 2^{n} \times 2^{n} 格子 — 図 5.1中庭: \(n = 3\) とした場合の \(2^{n} \times 2^{n}\) 格子

問題をややこしくするのが奇抜な建築家 Frangフラング Kehryケーリーだった。彼は特注の L 字タイル (図 \(\text{5.2}\)) を中庭に敷き詰めるべきだと主張した。\(n\) を任意の非負整数とするとき、Bill の銅像を中心に置いた \(2^{n} \times 2^{n}\) の中庭に L 字のタイルを敷き詰めることは可能だろうか？例えば \(n = 2\) のとき、この制約を守るタイル配置を図 \(\text{5.3}\) に示す。全ての非負整数 \(n\) に対して敷き詰めが可能であることを数学的帰納法で証明してみよう。

n=2 とした場合の L 字タイルの敷き詰め (\text{B} は Bill の銅像を表す) — 図 5.3\(n=2\) とした場合の L 字タイルの敷き詰め (\(\text{B}\) は Bill の銅像を表す)

定理 5.1.2

全ての非負整数 \(n\) に対して、Bill の銅像を中心に置いた \(2^{n} \times 2^{n}\) の中庭に上記の L 字タイルを敷き詰める方法が存在する。

証明 (失敗例) 数学的帰納法で示す。\(P(n)\) を述語「Bill の銅像を中心に置いた \(2^{n} \times 2^{n}\) の中庭に L 字タイルを敷き詰める方法が存在する」と定め、\(P(n)\) を帰納法の仮定とする。

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

帰納ステップ: ある非負整数 \(n\) で \(P(n)\) が成り立つと仮定する。これから示すべきは \(P(n+1)\) である。つまり Bill の銅像を中心に置いた \(2^{n+1} \times 2^{n+1}\) の中庭に L 字タイルを敷き詰める方法を示せばよい...

さて、困ったことになった！ Bill の銅像を中心に置いた小さな中庭に L 字タイルを敷き詰める方法が分かったとしても、大きな中庭における Bill の銅像の配置と L 字タイルの敷き詰めを考える上で何の役にも立たない。言い換えれば、\(P(n)\) と \(P(n+1)\) のギャップを埋める方法が明らかでない。

つまり定理 5.1.2 を証明するには、証明したい命題とは異なる帰納法の仮定が必要になる。

こういった状況では、示すべき命題より強い命題を帰納法の仮定にすることを最初に考えるべきである: そうした上で帰納法の仮定が真だと分かれば、示すべき命題も真だと直ちに分かる。例えば、この問題では述語「Bill の銅像が任意の場所に置かれた \(2^{n} \times 2^{n}\) の中庭に L 字タイルを敷き詰める方法が存在する」を帰納法の仮定にする。

このアドバイスは奇妙に思える: 「命題が証明できないなら、それより強い命題を証明してみよ」なんて！しかし数学的帰納法を使う証明では、このやり方で上手く行くことが多い。なぜなら、証明する命題を強くすると、帰納ステップで \(P(n) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(n+1)\) を示すときに利用できる仮定 \(P(n)\) も強くなるからである。この事実を定理 5.1.2 の証明で確かめてみよう。

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

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

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

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

この証明には優れた特徴が二つある。まず、L 字タイルを敷き詰める方法の存在だけではなく、実際に条件を満たす敷き詰めを構築するアルゴリズムが得られている。次に、強い結果が得られている: 「ハトが寄るので」と理由を付けて Bill の銅像を中庭の隅に移動できる！

数学的帰納法を使う証明が行き詰ったときは、帰納法の仮定を強めることが優れた一手になる場合が多い。ただし、強めた仮定は実際に正しい必要がある。正しくない命題はどうやっても証明できない。ときには、証明しやすい帰納法の仮定を見つけるのに多くの試行錯誤と偶然のひらめきが必要になる。例えば、あるとき数学者は「全ての平面グラフは \(5\)-選択可能 (\(5\)-choosable)」という予想²の証明または反例の発見に \(20\) 年以上にわたって成功していなかった。そんなとき、Carstenカールステン Thomassenトーマセンは 1994 年に一枚のナプキンで説明できるほど単純な数学的帰納法の証明を発表した。彼の証明の鍵は非常に賢い帰納法の仮定であり、それがあれば残りの議論は簡単だった！

5.1.6 間違った数学的帰納法の証明

もし我々が本書の執筆を上手くこなしているなら、読者は「数学的帰納法ってそんなに難しくない気がする ── \(P(0)\) を示して、全ての \(n\) で \(P(n) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(n+1)\) を示すだけじゃないか！」と考えているに違いない。その考えは一部で正しい。しかし、自分で数学的帰納法を使う証明を書き始めると問題に直面することがある。例えば、次に示すような議論で全ての馬は同じ色であることを「証明」してしまうかもしれない ── この授業はサボってよさそうだからロボットのプログラムでも書くか、と決断するのはまだ早い！

偽の主張

全ての馬は同じ色である。

この主張に \(n\) が含まれないことに注目してほしい。そのため、まず \(n\) を使う主張に書き換える必要がある。具体的には、これから次の主張を「証明」する:

偽の主張 5.1.3

\(n\) を \(1\) 以上の非負整数とする。任意の \(n\) 頭の馬の集まりについて、その集まりに属する全ての馬は同じ色である。

これは \(n \geq 0\) ではなく \(n \geq 1\) に対する主張なので、数学的帰納法を少しだけ変えた手法を使うのが自然である: \(P(1)\) をベースケースとして証明し、それから帰納ステップで \(P(n) \ \operatorname{\text{\footnotesize IMPLIES}}\ P(n+1)\) を証明する。これは完全に正しい数学的帰納法の変種であり、次の証明に含まれる誤りではない。

誤った証明 \(n\) に関する数学的帰納法で示す。帰納法の仮定を次の述語とする:

任意の \(n\) 頭の馬の集まりに属する全ての馬は同じ色である。

\((5.3)\)

ベースケース: \(n = 1\) のとき、\(n\) 頭の馬の集まりには \(1\) 頭しか馬が含まれない。その集まりに属する全ての (唯一の) 馬は明らかに同じ色である。よって \(P(1)\) が成り立つ。

帰納ステップ: ある整数 \(n \geq 1\) で \(P(n)\) が成り立つと仮定する。このとき、任意の \(n\) 頭の馬の集合について、その集まりに属する全ての馬は同じ色である。次に示す \(n+1\) 頭の馬の集まりがあるとする:

\[ h_{1},\ h_{2},\ \ldots\ h_{n},\ h_{n+1} \]

この \(n+1\) 頭の馬が同じ色だと示せばよい。

帰納法の仮定より、最初の \(n\) 頭の馬は同じ色と分かる:

\[ \underbrace{h_{1},\ h_{2},\ \ldots\ h_{n}}_{\text{同じ色}},\ h_{n+1} \]

帰納法の仮定をもう一度適用すれば、最後の \(n\) 頭の馬も同じ色だと分かる:

\[ h_{1},\ \underbrace{h_{2},\ \ldots\ h_{n},\ h_{n+1}}_{\text{同じ色}} \]

言い換えれば、\(h_{1}\) は \(h_{n+1}\) 以外の全ての馬 ── \(h_{2}\), \(\ldots\), \(h_{n}\) ── と同じ色を持つ。同様に、\(h_{n+1}\) は \(h_{1}\) 以外の全ての馬 ── \(h_{2}\), \(\ldots\), \(h_{n}\) ── と同じ色を持つ。よって \(h_{1}\) と \(h_{n+1}\) は \(h_{2}\), \(\ldots\), \(h_{n}\) と同じ色である。つまり \(n+1\) 頭の馬は同じ色であり、\(P(n+1)\) が真と分かる。よって \(P(n)\) が成り立つとき \(P(n+1)\) は成り立つ。

従って数学的帰納法の原理より、\(1\) 以上の全ての整数 \(n\) で \(P(n)\) は成り立つ。 ■

明らかに偽の主張が証明できてしまった！数学は壊れているのだろうか？数学なんて放り出して詩を学ぶべきだろうか？もちろんそんなことはない！これは証明が間違っていることを意味するに過ぎない。

上記の証明の間違いは「\(h_{1}\) は \(h_{n+1}\) 以外の全ての馬 ── \(h_{2}\), \(\ldots\), \(h_{n}\) ── と同じ色を持つ」にある。ドット \(\ldots\) で省略された記号の列 \(h_{2}\), \(\ldots\), \(h_{n}\) は、\(h_{1}\) と \(h_{n+1}\) 以外の馬が少なくとも \(1\) 頭存在する印象を与えるものの、それは \(n = 1\) のとき正しくない。\(n = 1\) のとき \(h_{1}\), \(h_{2}\), \(\ldots\), \(h_{n}\), \(h_{n+1}\) は \(h_{1}\), \(h_{2}\) だけになるので、\(h_{1}\) と同じ色を持つ「\(h_{n+1}\) 以外の馬」が存在しない！そのとき当然、\(h_{1}\) と \(h_{2}\) が同じ色を持つと示せない。

「この証明の間違いは、\(n \geq 2\) のとき \(P(n)\) は偽なのに、\(P(n+1)\) を証明するときに \(P(n)\) を仮定していることだ」と説明する学生が時々いる。この説明では本講義の試験で点数を得られない理由を学生に納得させる方法を考えてみてほしい。

\(n=0\) の場合は特殊ケースで、中庭が \(1\) 個の正方形からなるために銅像の設置場所に選択肢がない。\(n > 0\) なら中心の正方形は \(4\) 個ある。 ↩︎
\(5\)-選択可能性は \(5\)-彩色可能性を少しだけ一般化した概念である。全ての平面グラフは \(4\)-彩色可能であるのに対して、\(4\)-選択可能でない平面グラフは存在する。こういった文章を理解できなくても心配する必要はない。グラフ、平面性、彩色可能性は本書の第 II 部で解説される。 ↩︎