第十六章：生成函數 — 動畫敘事

第十六集 · Ch.16 生成函數

數列的代數

把一個數列 a₀, a₁, a₂, … 藏進一個多項式裡：
A(x) = a₀ + a₁x + a₂x² + …
然後用代數操作這個多項式，
就能推導出數列的封閉公式。

什麼是生成函數？

生成函數（Generating Function）

數列 (a₀, a₁, a₂, …) 的生成函數是：
A(x) = Σ aₙxⁿ = a₀ + a₁x + a₂x² + …

x 只是一個「佔位符」，不代表具體數值。
目的是把數列的計算問題轉換成多項式代數問題。

生成函數不是用來「代入 x 計算」，
而是用來操縱係數——對它求導、相乘、展開。

常見生成函數速查表

數列	生成函數 A(x)

Fibonacci 封閉公式推導

F(n) = F(n-1)+F(n-2)，用生成函數推出 Binet 公式：

設 F(x) = Σ Fₙxⁿ，利用遞迴關係，整理得：
F(x) = x / (1 - x - x²)

分母分解：1-x-x² = -(x-φ)(x-ψ)
其中 φ = (1+√5)/2 ≈ 1.618（黃金比例），ψ = (1-√5)/2

部分分數展開後，xⁿ 的係數就是 Fibonacci 數：
Fₙ = (φⁿ - ψⁿ) / √5（Binet 公式）

雖然 φ 和 ψ 是無理數，但它們的差除以 √5 永遠是整數！

互動：生成函數係數展開

選一個生成函數，展開前 8 個係數：

請選擇一個生成函數

觀念測驗

生成函數 1/(1-x)² 展開後，xⁿ 的係數是多少？

小結

生成函數：
數列變代數

把數列藏進多項式，然後用代數工具操縱它。
這個技巧能解決遞迴關係、計數問題，
甚至推出像 Binet 公式這樣意想不到的結果。

下一集：機率空間——從硬幣到樣本空間

1 / 7

本頁為動畫敘事版。看完後可前往完整第十六章進行互動練習。

教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)

📚 第十六章：生成函數