跳轉到

07.3 遞迴關係式#

本節目標#

  • 理解遞迴數列（recurrence）的概念：用前面的項定義後面的項。
  • 用 SymPy 的 rsolve() 解線性遞迴關係式，求出閉式（closed form）。
  • 推導 Fibonacci 數列的 Binet 公式，並用矩陣特徵值（連結 6.3 節）重新推導。
  • 實驗：解出 Tower of Hanoi 的遞迴式。

一、遞迴數列的概念#

遞迴數列用「前一項（或前幾項）」來定義下一項。例如等差數列：

\[ a_{n+1} = a_n + d, \quad a_0 = c \]

最有名的例子是 Fibonacci 數列：

\[ F_{n+2} = F_{n+1} + F_n, \quad F_0 = 0,\ F_1 = 1 \]

遞迴式方便計算，但我們常想知道第 \(n\) 項的「直接公式」（閉式）。把遞迴式解成 \(a_n\) 的顯式表達式，就是解遞迴關係式。

先用 Python 一步步算 Fibonacci（數值方法）：

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print([fib_iter(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

二、rsolve()：解線性遞迴#

SymPy 的 rsolve(遞迴式, 函數, 初始條件) 能把遞迴式解成閉式。先看簡單的等比遞迴 \(a_{n+1} = 2 a_n\) ， \(a_0 = 3\) ：

from sympy import rsolve, symbols, Function, simplify, sqrt, Rational

a = symbols('a', integer=True, nonnegative=True)
f = Function('f')

sol = rsolve(f(a + 1) - 2*f(a), f(a), {f(0): 3})
print(sol)     # 3*2**a

再看等差遞迴 \(a_{n+1} = a_n + 5\) ， \(a_0 = 2\) ：

print(rsolve(f(a + 1) - f(a) - 5, f(a), {f(0): 2}))   # 5*a + 2

解 Fibonacci 遞迴：

F = rsolve(f(a + 2) - f(a + 1) - f(a), f(a), {f(0): 0, f(1): 1})
print(simplify(F))
# sqrt(5)*(1/2 + sqrt(5)/2)**a/5 - sqrt(5)*(1/2 - sqrt(5)/2)**a/5

三、Fibonacci 的閉式：Binet 公式#

上式正是著名的 Binet 公式：

\[ F_n = \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^n - \frac{1}{\sqrt{5}} \left( \frac{1 - \sqrt{5}}{2} \right)^n \]

其中 \(\frac{1+\sqrt{5}}{2}\) 就是黃金比例 \(\varphi \approx 1.618\) 。驗證它確實給出 Fibonacci 數：

phi = (1 + sqrt(5)) / 2
psi = (1 - sqrt(5)) / 2
F_binet = (phi**a - psi**a) / sqrt(5)

expected = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
for i, e in enumerate(expected):
    assert simplify(F_binet.subs(a, i)) == e
print("Binet 公式驗證通過")

# 有趣的性質：相鄰兩項的比值趨近黃金比例
print((F_binet.subs(a, a + 1) / F_binet.subs(a, a)).limit(a, 3, '+'))  # 會趨近 phi

四、用矩陣特徵值推 Fibonacci（連結 6.3）#

把遞迴 \(F_{n+2} = F_{n+1} + F_n\) 寫成矩陣形式：

\[ \begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} \]

反覆套用可得 \(\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = A^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}\) 。矩陣的特徵值決定行為——這正是 6.3 節特徵值理論的應用：

from sympy import Matrix

A = Matrix([[1, 1], [1, 0]])
print(A.eigenvals())
# {1/2 + sqrt(5)/2: 1, 1/2 - sqrt(5)/2: 1}
# 特徵值就是 phi 與 psi！閉式必然是 c1*phi^n + c2*psi^n 的形式

print(A.eigenvects())

用矩陣冪直接驗證：

v = Matrix([1, 0])   # (F_1, F_0)
for i in range(2, 12):
    Fn = (A**(i - 1) * v)[0]
    print(i, Fn)
# 依序印出 1, 2, 3, 5, 8, 13, ...

rsolve 的使用細節：

  1. 遞迴式要寫成「式子 = 0」的形式，例如 f(n+2) - f(n+1) - f(n)。
  2. 初始條件用字典 {f(0): 0, f(1): 1}，個數需與遞迴的「階數」相同（二階遞迴給兩個條件）。
  3. 函數符號要用 Function('f') 定義，索引變數需宣告為整數。
  4. rsolve 也支援非齊次項（如 \(a_{n+1} = 2a_n + 1\) ）與非線性某些型態，但線性齊次最可靠。
# 非齊次範例：a_{n+1} = 2*a_n + 1, a_0 = 0（河內塔的同型遞迴）
print(rsolve(f(a + 1) - 2*f(a) - 1, f(a), {f(0): 0}))   # 2**a - 1

五、動手實驗：Tower of Hanoi 遞迴式解出#

河內塔規則： \(n\) 個盤子從柱 A 搬到柱 C，一次搬一個、小盤永遠在大盤上。搬 \(n\) 個盤子的最少步數 \(T_n\) 滿足：

\[ T_n = 2 T_{n-1} + 1, \quad T_1 = 1 \]

直覺：先把上面 \(n-1\) 個搬到暫存柱（ \(T_{n-1}\) 步），搬最大盤（1 步），再把 \(n-1\) 個疊回來（ \(T_{n-1}\) 步）。

先用遞迴算出前幾項，猜測規律：

def hanoi(n):
    if n == 1:
        return 1
    return 2 * hanoi(n - 1) + 1

print([hanoi(i) for i in range(1, 9)])
# [1, 3, 7, 15, 31, 63, 127, 255]
# 規律：2^n - 1

用 rsolve 正式解出：

T = rsolve(f(a + 1) - 2*f(a) - 1, f(a), {f(1): 1})
print(simplify(T))      # 2**a - 1

驗證閉式與遞迴一致：

for i in range(1, 12):
    assert simplify(T.subs(a, i)) == hanoi(i)
print("河內塔閉式驗證通過")

再解另一個變體：若可以「一次搬兩個相鄰盤」（簡化規則），遞迴變成 \(T_n = 2 T_{n-1} - 1\) ：

T2 = rsolve(f(a + 1) - 2*f(a) + 1, f(a), {f(1): 1})
print(simplify(T2))     # 1（常數解）

實驗 2：另一個經典遞迴——爬樓梯問題。一次可爬 1 階或 2 階，爬 \(n\) 階的方法數 \(S_n = S_{n-1} + S_{n-2}\) ，正是 Fibonacci：

S = rsolve(f(a + 2) - f(a + 1) - f(a), f(a), {f(1): 1, f(2): 2})
print([simplify(S.subs(a, i)) for i in range(1, 10)])
# [1, 2, 3, 5, 8, 13, 21, 34, 55] -> Fibonacci 位移一位

實驗 3：二階遞迴的通解結構。 \(a_{n+2} = 5 a_{n+1} - 6 a_n\) ，特徵方程 \(r^2 - 5r + 6 = 0\) 的根是 2 與 3：

from sympy import Eq, solve
r = symbols('r')
print(solve(Eq(r**2 - 5*r + 6, 0), r))   # [2, 3]

sol2 = rsolve(f(a + 2) - 5*f(a + 1) + 6*f(a), f(a), {f(0): 1, f(1): 4})
print(simplify(sol2))    # 2*3**a - 3*2**a？算一下：2*3**a - 2**a
# 結果會是 c1*2**a + c2*3**a 的形式，係數由初始條件決定

觀察重點： 1. 遞迴式給「怎麼算」，閉式給「是什麼」——rsolve 幫我們跨越這一步。 2. 線性齊次遞迴的閉式由特徵根決定，矩陣特徵值與遞迴特徵根是同一件事的兩面。 3. 河內塔 \(T_n = 2^n - 1\) 說明「指數爆炸」： \(n=64\) 時步數超過 \(10^{19}\) ，這是世界末日傳說的數學根據。

小結與練習#

本節我們學會了： - 遞迴關係式的概念與 rsolve() 的用法（遞迴式、函數、初始條件三個參數）。 - Fibonacci 的 Binet 公式 \(F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}\) ， \(\varphi\) 為黃金比例。 - 用矩陣 \(A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\) 的特徵值理解遞迴的閉式結構（連結 6.3）。 - 解出河內塔遞迴 \(T_n = 2T_{n-1} + 1\) 的閉式 \(T_n = 2^n - 1\) 。

練習： 1. 用 rsolve 解 \(a_{n+1} = 3a_n + 2\) ， \(a_0 = 1\) ，並驗證前 5 項。 2. 解遞迴 \(a_{n+2} - 4a_{n+1} + 4a_n = 0\) ， \(a_0 = 1\) ， \(a_1 = 3\) （注意重根時解的形式是 \((c_1 + c_2 n) 2^n\) ）。 3. 用矩陣 \(A^{10}\) 計算 \(F_{11}\) ，與 rsolve 的結果比對。 4. 某人存款年利率 5%，每年年底再存 10000 元，寫出餘額的遞迴式並用 rsolve 解出 \(n\) 年後的餘額。