## 定義 漸化式(recurrence, recurrence relation, recurrence equation)とは、数列の第n項をそれより前の項(場合によりnそのもの)の関数として定義する式である。数列を閉じた形(closed form)で直接与える代わりに、境界条件(boundary condition、数列の最初の数項の値)と、後続の項を先行項から計算する遷移規則の組で数列を一意に指定する。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.1, §21.2.1) 漸化式を解く(閉じた形を求める)ための初等的な2手法がある。 - **推測して検証(guess-and-verify)**: 数列の最初の数項を計算してパターンを推測し、その推測を帰納法で検証する。単純だが、正しいパターンを言い当てられるとは限らない(マージソートの漸化式では最初の数項に明確なパターンが見えず失敗する)。 - **展開と整理(plug-and-chug、expansion / iteration とも呼ばれる)**: 漸化式を繰り返し「代入(plug)」して「整理(chug)」し、式の列にパターンを見出す。パターンが見えたら1段階分の代入でそのパターン自体を検証し(これは帰納法の帰納段階に相当する)、最後に既知の境界条件の項まで展開して閉じた形を得る。推測して検証が数列の値の列からパターンを見出すのに対し、plug-and-chugは式の列から後ろ向きに(第n項から出発して先行項へ)パターンを見出す点で方向が逆である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.1.2, §21.2.2) **線形漸化式(linear recurrence)**は f(n) = a1 f(n-1) + a2 f(n-2) + ... + ad f(n-d) [+ g(n)] の形をとる漸化式である(a1, ..., ad, dは定数、dを漸化式の階数(order)と呼ぶ)。g(n) = 0のとき**斉次(homogeneous)**、そうでないとき**非斉次(inhomogeneous)**と呼ぶ。斉次線形漸化式は f(n) = x^n という指数関数の形を仮定して代入し、x^(n-d)で割ることで得られる**特性方程式(characteristic equation)** x^d = a1 x^(d-1) + ... + ad から解ける。特性方程式の非重複根rはr^nという解を、重複度kの根rはr^n, n r^n, n^2 r^n, ..., n^(k-1) r^n というk個の独立な解を生む。任意の解の線形結合もまた解であること(定理21.3.1、直接代入による自明な証明)から、これらの解の一般の線形結合が斉次解の一般形になる。フィボナッチ数列 f(n) = f(n-1) + f(n-2)(f(0) = f(1) = 1)はこの手法の典型例で、特性方程式 x^2 = x + 1 の根 (1±√5)/2 から、黄金比φ = (1+√5)/2 を含むBinetの公式 f(n) = (1/√5)(φ^(n+1) - ψ^(n+1))(ψ = (1-√5)/2)という閉じた形が得られる。600年近く未解決だったフィボナッチ数列の閉じた形が、このcookbook手法で機械的に導けることが強調される。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.3.1, §21.3.2) 非斉次線形漸化式は次の5段階で解ける: (1) g(n)を0に置き換えて斉次解を求める、(2) 未確定の係数のまま斉次解の一般形を書き下す、(3) g(n)を戻し、境界条件を無視して特殊解(particular solution)を1つ見つける(g(n)が定数・多項式ならば同次数の多項式を、g(n)が指数関数ならば同じ底の指数関数を試行関数として推測する)、(4) 斉次解と特殊解の和を一般解とする、(5) 境界条件を代入して連立一次方程式を立て、未確定の係数を決定する。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.3.3, §21.3.4) ## 横断的知見 - 漸化式の検証証明(guess-and-verifyの第2段階)は、[[帰納法]]の証明テンプレートと構造的に一致する: 漸化式の第1行(境界条件)が帰納法の基底部に、第2行(遷移規則)が帰納段階にそのまま対応する。この対応は偶然ではなく、漸化式による数列の定義自体が「基底部+構成規則」という[[帰納法]]concept文書が扱う再帰的データ型の定義パターンと同型である。ただし、逆方向(帰納法の仮定を弱めて簡単な上界を証明しようとする)では対応が破綻する例が示されており、漸化式Tn = 2Tn-1 + 1に対しTn ≤ 2^nという弱めた仮定で帰納段階を証明しようとすると、2·2^(n-1) + 1 ≤ 2^nが成り立たず証明が通らない。これは第5章が指摘する「帰納法の仮定を強めると証明が通ることがある」という現象の裏返しの実例であり、漸化式の検証証明では仮定を弱めると失敗するという教訓を追加する。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.1, §21.1.1, [[@2015__MIT__Mathematics for Computer Science - Chapter 5 Induction]] §5.1.5) - フィボナッチ数列の特性方程式による解法(本節)と、[[最大公約数]]concept文書が扱う互除法(Euclidean algorithm)の最悪計算量は、同じフィボナッチ数列を介して結びつく。互除法の反復回数が最大になる入力は連続する2つのフィボナッチ数であるという事実が第21章で明言されており、第8章(最大公約数)の未解決の問いとして残されていた「フィボナッチ数と互除法の最悪計算量の関係」に直接答える。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.3.1, [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] §8.1〜§8.2) - **第21章の特性方程式による解法と、第15章の母関数による解法の関係**: 両章は同じ線形漸化式(フィボナッチ数列 fn=f(n-1)+f(n-2)、ハノイの塔 tn=2t(n-1)+1)を独立の経路で解く別解の関係にある。第21章は解の形が指数関数 x^n であると先に**仮定**して漸化式に代入し、特性方程式 x^d = a1 x^(d-1) + ... + ad を立てて根を求める(定理21.3.1が線形結合の妥当性を保証する)。これに対し第15章は、解の形を一切仮定せず、数列の母関数 F(x) を未知数とみなして F(x) と xF(x)(・x^2F(x)、…)をシフトさせて差し引くという純粋に機械的な操作だけで F(x) を有理関数として求め、最後に部分分数分解して係数を読み取る。フィボナッチ数列で具体的に確認すると、母関数法で得られる部分分数分解 x/(1-x-x^2) = c1/(1-α1x) + c2/(1-α2x) の α1, α2 は特性方程式 x^2=x+1 の根 (1±√5)/2 の逆数に一致しており、2つの手法は表面上異なる代数操作を経由しながら同じ特性方程式の根に帰着する同型の計算であることが分かる。**違いは天下り性の所在**である。特性方程式法は「解の形が x^n である」という発見的な仮定を最初に置く必要があるのに対し、母関数法はその仮定を要さず、母関数のシフトという第15章冒頭から一貫する単一の操作だけで有理関数の式に到達できる。ただし母関数法は最終段階で部分分数分解という別の技法を要求するため、根が単純な場合には両手法の労力は同程度になる。非斉次の場合も対応は保たれる。第21章は非斉次項 g(n) と同じ形の特殊解を推測する(試行関数法、これも天下り的な一手)のに対し、第15章§15.4.3は非斉次項 h(n) の母関数が有理関数であればそれを漸化式の母関数の式に代入するだけでよく、ここでも推測を回避できる。第21章の脚注は「母関数を使えば推測なしに解ける」と一言で示唆するにとどめていたが、本節の突き合わせにより、両者は独立した2つの手法というより「同じ特性方程式に至る、仮定の要不要が異なる2つの経路」であることが具体的な計算で裏付けられる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.3.1〜§21.3.4, [[@2015__MIT__Mathematics for Computer Science - Chapter 15 Generating Functions]] §15.3〜§15.4) ## 未解決の問い - 漸化式の一般形における非重複根と重複根の扱いは、線形代数(固有値の重複度とJordan標準形)と数学的に同型であるはずだが、本章は線形代数への接続に触れない。線形代数を扱う他ソースがingestされたら、この対応を横断的知見として追記したい。 - 特性方程式法と母関数法のどちらが計算量的に有利かは根の重複度や非斉次項の複雑さに依存すると推測されるが、第21章・第15章のいずれも計算量比較を明示的に論じていない。アルゴリズム解析や計算代数を扱う他ソースがingestされたら、この比較を補強したい。 - [[漸近記法]]concept文書の未解決の問いにある「漸近記法とアルゴリズムの計算量クラスとの接続」について、本章はΘ記法を漸化式の解の表現に使うが(Master Theorem・Akra-Bazziの公式)、計算量クラス(P, NP等)そのものへの言及はない。計算複雑性理論を扱う他ソースがingestされたら、この接続を補強したい。 ## 関連 - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 15 Generating Functions]] - 概念: [[帰納法]](漸化式の検証証明の構造的対応) / [[漸近記法]](分割統治漸化式の解の表現に使うΘ記法) / [[分割統治]](漸化式の非線形な姉妹形態) / [[最大公約数]](フィボナッチ数を介した互除法の最悪計算量との接続) / [[母関数]](特性方程式による解法との別解の関係) ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 21, §21.1〜§21.3. - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 15, §15.3〜§15.4.