Closed Forms of Recursive Polynomials and Applications

以一個家族統整多種遞迴

本篇研究二變數多項式 M₀=a、M₁=bx+cy+d，以及 Mₙ=xMₙ₋₁+yMₙ₋₂（n≥2），其中 a、b、c、d 是實常數。固定 y=1 或 x=1 並調整初值，可得到不同 Fibonacci 型家族。作者提供有限和與 Binet 封閉公式，再應用於數值序列的長期行為、組合恆等式，以及微分與卷積的關聯。

有限和公式的精簡寫法

令 U₀=0、U₁=1，且 U 遵循相同遞迴。則 n≥1 時，Mₙ=M₁Uₙ+ayUₙ₋₁，而 Uₙ=Σⱼbinom(n−1−j,j)xⁿ⁻¹⁻²ʲyʲ，求和範圍為 0≤j≤floor((n−1)/2)。這是原文有限和的等價整理：j 表示二步塊數，另外有 n−1−2j 個一步塊，排列二步位置得到二項係數。Pascal 恆等式也直接驗證遞迴。

Binet 公式與退化情況

特徵方程為 r²−xr−y=0。兩根不同時，Mₙ=Ar₊ⁿ+Br₋ⁿ，其中 A=(M₁−ar₋)/(r₊−r₋)、B=(ar₊−M₁)/(r₊−r₋)。重根必須滿足判別式 x²+4y=0，故軌跡是 y=−x²/4；掃描版該處的正負號以此條件校正。若 r=x/2≠0，解為 [a+n(M₁/r−a)]rⁿ；若 x=y=0，直接由遞迴知 n≥2 的項全為零。

穩定三角形與初值的角色

參數區域 |y|<1、|x|<1−y 是頂點 (0,1)、(−2,−1)、(2,−1) 所圍三角形的嚴格內部，兩根都在單位圓內，因此所有初值都趨零。外部存在不穩定根，卻不能據此說每組初值皆發散：例如 x=3/2、y=1，根為 2、−1/2；取 M₀=1、M₁=−1/2，增長項消失，留下 Mₙ=(−1/2)ⁿ。教材保留這個必要限定。

三條邊與三個頂點

右邊 x=1−y 的根是 1、−y，序列趨常數；左邊 x=y−1 的根是 −1、y，通常漸近交替。底邊 y=−1、|x|<2 的根為 e±ⁱθ，x=2cosθ，因此有界；θ/(2π) 為有理數時具有週期。頂點 (0,1) 交替初始兩值；(±2,−1) 是重根 ±1，除非初值消去 n 因子，否則會出現線性振幅增長。

由參數代入得到字串恆等式

取 a=1、b=c=0、d=w、x=1、y=w²−w，則 Mₙ=wⁿ。把這組參數代入有限和，可得 wⁿ=Σₖ[binom(n−k,k)+(w−1)binom(n−k−1,k)]wᵏ(w−1)ᵏ。當 w 是正整數，右側也可以解釋為 w 個字母組成的長度 n 字串之分類計數；越界二項係數取零。

分類為何既不重複也不遺漏

令 φₖ(s) 為字串前 n−k 格的非零字母數。Aₖ要求 φₖ=k；Bₖ要求 φₖ₊₁=k 且第 n−k 格非零。兩類大小正是恆等式的兩項。δₖ=φₖ−k 每步下降一或二，從非負走到非正：遇到零是 A 類，從一跳到負一是 B 類。單調性使交會唯一，所以所有字串恰好計一次。例如 n=w=3，四個非空類大小為 1、2、12、12，合計 27。

用生成函數看卷積與微分

離散卷積定義為 (f*g)ₙ=Σₖ₌₀ⁿfₖgₙ₋ₖ。令 B₀=B₁=1、Bₙ=Bₙ₋₁+yBₙ₋₂，其生成函數為 1/D，D=1−z−yz²。另令 R₀=1、R₁=1+y，且使用相同遞迴，生成函數為 (1+yz)/D。直接對 y 微分得到 z/D²，因此比對係數即有 (B*B)ₙ=R′ₙ₊₁(y)。這補充了原文的係數計算證明。

數值例子與一般公式的參數慣例

y=1 時，B 是 1,1,2,3,5,…，自卷積是 1,2,5,10,20,38,…；y=2 時，本篇 Jacobsthal 型初值給 B=1,1,3,5,11,…，卷積是 1,2,7,16,41,94,…。一般 Theorem 8 可清楚寫成：先將 A=cy+d 固定，對新變數 t 微分 Qₙ₊₁,{A,a,A}(t)，最後令 t=y。若把 A(y) 一起微分會額外產生項，與該公式不同。

閱讀重點與來源

這篇的價值在於同一二階遞迴可以同時用有限和、特徵根、字串分類與生成函數理解。讀者應分清多項式變數與固定參數、穩定性與個別初值軌跡，以及有界、週期、收斂三者。來源：Michelle Haver、Kathleen Lee、William McDermott、Alexander Wilson、Wei-Hsuan Yu、Aklilu Zeleke，Closed Forms of Recursive Polynomials and Applications，Ars Combinatoria 142 (2019), 175–195。