22.1 推測検証と定義代入

再帰方程式を解く手法はいくつか存在する。最も単純なのは「解を推測guessして、その正しさを数学的帰納法で検証verifyする」という手法である。本書ではこの手法を推測検証 (guess-and-verify) と呼ぶ。

例えば、第 16.4.2 項で見た Hanoi の塔問題では、\(n\) 個の円盤を全て移動させるのに必要なステップ数が次の再帰方程式で表される:

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

\(T_{n}\) の値をいくつか実際に計算すると \(1\), \(3\), \(7\), \(15\), \(31\), \(63\) となる。ここから \(T_{n} = 2^{n} - 1\) と自然に推測できる。このように再帰方程式の解を推測したときは、その正しさを (典型的には数学的帰納法で) 必ず検証しなければならない。推測が間違っている可能性は常にある。 (この問題で本当に検証が必要だろうか？間違っていたとしても世界が終わるわけでもない...いや、検証しておこう。)

主張 22.1.1

\(T_{n} = 2^{n} - 1\) は次の再帰方程式を満たす:

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

証明 \(n\) に関する数学的帰納法で示す。\(T_{n} = 2^{n} - 1\) を帰納法の仮定とする。\(n = 1\) のとき \(T_{1} = 1 = 2^{1} - 1\) なので、帰納法の仮定は成り立つ。続いて、ある \(n \geq 2\) で \(T_{n-1} = 2^{n-1} - 1\) が成り立つと仮定して \(T_{n} = 2^{n} - 1\) を証明する:

\[ \begin{aligned} T_{n} &= 2 T_{n-1} + 1 \\ &= 2(2^{n-1} - 1) + 1 \\ &= 2^{n} - 1 \end{aligned} \]

最初の式変形は与えられた再帰方程式から、次の式変形は帰納法の仮定から分かる。最後の式変形は代数的な単純化である。 ■

推測した解を検証する証明は短く済む場合が多い。なぜなら、再帰方程式が数学的帰納法による証明と似た構造を持っているからである。例えば上記の証明では、再帰方程式の第一行が表す \(T_{1}\) の定義を使って数学的帰納法のベースケースが示され、第二行が表す \(T_{n}\) を以前の項で表す方法を使って帰納ステップが示される。

これで推測された解が正しいと分かった。Hanoi の塔の伝承では \(n = 64\) としたパズルが解けると世界が終わりを迎えると言われている。ただ \(T_{64} = 2^{64} - 1\) なので、世界が終わるまでに実行しなければならないステップ数は \(1800\) 京を超える。期末試験に向けた勉強は放棄しない方がよさそうだ。

22.1.1 上界に関する落とし穴

再帰方程式の解が複雑で推測が難しいとき、解の上界となる単純な式で見つけようと思うことがあるかもしれない。しかし、その考えには落とし穴がある。例えば、Hanoi の塔問題で現れる再帰方程式の厳密な解は \(T_{n} = 2^{n} - 1\) なので、この解に対する「単純な」上界 \(T_{n} \leq 2^{n}\) の証明を試みると、次のようになる:

誤った証明 \(n\) に関する数学的帰納法を用いる。\(T_{n} \leq 2^{n}\) を帰納法の仮定とする。\(n = 1\) のとき \(T_{1} = 1 \leq 2^{1}\) なので示したい結論は成り立つ。続いて、ある \(n \geq 2\) で \(T_{n-1} \leq 2^{n-1}\) が成り立つと仮定して \(T_{n} \leq 2^{n}\) を証明する:

\[ \begin{aligned} T_{n} &= 2 T_{n-1} + 1 \\ &\leq 2(2^{n-1} - 1) + 1 \\ &{\color{red} {} \not\leq {}} 2^{n} \qquad {\color{red} \text{示したい結論が成立しない！}} \end{aligned} \]

最初の式変形は与えられた再帰方程式から、次の式変形は帰納法の仮定から分かる。最後の式変形は見るも無残な大失敗である。 ■

以前のように証明が進まない！数学的帰納法による証明でよくあるように、先述の議論は帰納法の仮定を強くしたときにだけ上手く進む。これは再帰方程式の解の上界を考えるアプローチが無意味であることを意味しないものの、数学的帰納法と再帰方程式がかみ合わない状況は確かに存在する。

22.1.2 定義代入

推測検証は再帰方程式を解く一般的で単純な手法である。しかし、大きな欠点が一つある: 解を正しく推測する必要がある。Hanoi の塔問題では簡単に推測できたものの、複雑怪奇な形をした再帰方程式の解を正しく推測するのは困難を極める。慣れれば多少は上達するのは事実だが、他の手法を知っておくことも重要となる。

定義代入 (plug-and-chug) は再帰方程式を解くための異なる手法である。この手法は「展開 (expansion)」や「反復 (iteration)」などとも呼ばれる。推測検証と同じように、定義代入でもパターンを特定することが重要なステップとなる。しかし定義代入では定義から計算した実数列ではなく、定義を代入して展開した式を見つめることになる。式を見つめた方が簡単に解が推測できる場合もある。

定義代入は三つのステップからなる。Hanoi の塔問題を使って説明しよう。

ステップ 1: パターンが現れるまで定義の代入を繰り返す

最初のステップでは、再帰方程式の定義にその定義を代入plugし、得られた式を整理chugする操作をパターンが見つかるまで繰り返す。式を整理しすぎるとパターンが見えにくくなる場合があるので、このステップは慎重に進める必要がある。整理は控えめにchug in moderationと憶えておくといいだろう ── 大学生活でもよく言われることだ¹。

Hanoi の塔問題の再帰方程式では次のように式が変形される:

\[ \begin{aligned} T_{n} &= 2 T_{n-1} + 1 && \\ &= 2 (2 T_{n-2} + 1) + 1 && \quad (\text{代入}) \\ &= 4 T_{n-2} + 2 + 1 && \quad (\text{整理}) \\ &= 4 (2 T_{n-3} + 1) + 2 + 1 && \quad (\text{代入}) \\ &= 8 T_{n-3} + 4 + 2 + 1 && \quad (\text{整理}) \\ &= 8 (2 T_{n-3} + 1) + 4 + 2 + 1 && \quad (\text{代入}) \\ &= 16 T_{n-4} + 8 + 4 + 2 + 1 && \quad (\text{整理}) \end{aligned} \]

最初に再帰方程式の定義がある。第二行では定義に含まれる \(T_{n-1}\) に \(2 T_{n-2} + 1\) が代入される。両者が等しいことは同じく再帰方程式の定義から分かる。第三行では式が整理される ── ここで整理しすぎてはいけない！同様に代入と整理を繰り返すと明らかなパターンが現れ、次の等式が成り立つだろうと推測できる:

\[ \begin{aligned} T_{n} &= 2^{k} T_{n-k} + 2^{k-1} + 2^{k-2} + \cdots + 2^{2} + 2^{1} + 2^{0} \\ &= 2^{k} T_{n-k} + 2^{k} - 1 \end{aligned} \]

パターンが分かった後は、式を扱いやすい形に整理して構わない。ここでは幾何級数の公式を使って閉形式の式を得ている。

ステップ 2: パターンの正しさを検証する

ステップ 1 で得た一般的な等式が成り立つことの検証が次のステップとなる。定義の代入plugと整理chugをもう一度行うと、示したい等式の右辺は次のように変形できる:

\[ \begin{aligned} 2^{k} T_{n-k} + 2^{k} - 1 &= 2^{k} (2 T_{n-(k+1)} + 1) + 2^{k} - 1 && \quad (代入) \\ &= 2^{k + 1} T_{n-(k+1)} + 2^{k+1} - 1 && \quad (整理) \end{aligned} \]

最初の式の \(k\) を \(k + 1\) にしたものが最後に得られた。驚くべきことに、この時点で示したかった等式の証明が事実上完了する。理由は次の通りである: \(k = 1\) の場合は与えられた再帰方程式から直ちに成立が分かる。そして上述の式変形からは、ある \(k \geq 1\) で等式が成り立つなら \(k + 1\) でも等式が成り立つと分かる。よって数学的帰納法の原理より、全ての \(k \geq 1\) で等式は成立する。

ステップ 3: 既知の値を使って \(T_{n}\) を求める

最後のステップとして、値が分かっている項の関数として \(T_{n}\) を表す。今考えている問題では \(T_{1} = 1\) が分かっているので、\(k = n -1\) とすれば \(T_{1}\) で \(T_{n}\) を表せる。後は式を整理すれば \(T_{n}\) を表す閉形式の式が得られる:

\[ \begin{aligned} T_{n} &= 2^{n-1} T_{1} + 2^{n-1} - 1 \\ &= 2^{n-1} \cdot 1 + 2^{n-1} - 1 \\ &= 2^{n} - 1 \end{aligned} \]

推測検証を使った解法と同じ解が得られた！

推測検証と定義代入を比べてみよう。推測検証では、再帰方程式が表す実数列の最初の数項 \(T_{1}\), \(T_{2}\), \(T_{3}\), \(\ldots\) の値をパターンが見つかるまで計算する。そのとき探すのは第 \(n\) 項 \(T_{n}\) を表す閉形式の式である。これに対して定義代入では、第 \(n\) 項から「後ろ向きに」考える。つまり \(T_{n}\) を表す式に含まれる \(T_{n-1}\) をさらに \(T_{n-2}\), \(T_{n-3}\), \(\ldots\) で繰り返し置き換えていく。その中でパターンが分かれば、既知の項の関数として \(T_{n}\) を表すことができ、その式に既知の値を代入すれば \(T_{n}\) の閉形式の式が得られる。つまり推測検証と定義代入はそれぞれ反対の方向から問題を解く手法と言える。

訳注: 英単語 chug には「計算や処理を機械のように黙々と進める」の他に「酒を一気飲みする」という意味がある。 ↩︎