求解线性递推序列闭合式：推导含z²-6z+5分母的生成函数

嘿，我来一步步帮你梳理怎么从给定的递推关系和生成函数定义，推导出分母为z² - 6z + 5的生成函数，核心是利用递推关系把无穷级数转化为代数方程：

第一步：明确生成函数的定义 #

题目里给出的生成函数是：
$$f(z) = \frac{s_1}{z} + \frac{s_2}{z^2} + \frac{s_3}{z^3} + ... = \sum_{n=1}^{\infty} \frac{s_n}{z^n}$$
我们的目标是把这个无穷级数和递推关系$s_n = 6s_{n-1} -5s_{n-2}$（$n≥3$）结合起来。

第二步：利用递推关系构造等式 #

先把递推式移项，得到对所有$n≥3$成立的式子：
$$s_n -6s_{n-1} +5s_{n-2} = 0$$
接下来，对这个式子从$n=3$到$∞$求和，每一项都乘以$\frac{1}{z^n}$，这样就能和生成函数的形式对应起来：
$$\sum_{n=3}^{\infty} \frac{s_n}{z^n} -6\sum_{n=3}^{\infty} \frac{s_{n-1}}{z^n} +5\sum_{n=3}^{\infty} \frac{s_{n-2}}{z^n} = 0$$

第三步：把每个求和式转化为含$f(z)$的表达式 #

我们可以通过变量替换，把每个无穷级数用$f(z)$和初始项表示：

• 第一个求和式：$\sum_{n=3}^{\infty} \frac{s_n}{z^n} = f(z) - \frac{s_1}{z} - \frac{s_2}{z^2}$（去掉前两项，剩下的就是$f(z)$的后半部分）
• 第二个求和式：$\sum_{n=3}^{\infty} \frac{s_{n-1}}{z^n} = \frac{1}{z}\sum_{k=2}^{\infty} \frac{s_k}{z^k} = \frac{1}{z}\left(f(z) - \frac{s_1}{z}\right)$（令$k=n-1$，替换后整理）
• 第三个求和式：$\sum_{n=3}^{\infty} \frac{s_{n-2}}{z^n} = \frac{1}{z^2}\sum_{k=1}{\infty} \frac{s_k}{z^k} = \frac{1}{z^2}f(z)$（令$k=n-2$，替换后正好是完整的$f(z)$）

第四步：代入初始值并整理求解$f(z)$ #

把$s_1=1$、$s_2=2$代入上面的表达式，再代入到第二步的等式里：
$$\left(f(z) - \frac{1}{z} - \frac{2}{z^2}\right) -6\cdot\frac{1}{z}\left(f(z) - \frac{1}{z}\right) +5\cdot\frac{1}{z^2}f(z) = 0$$
为了简化计算，两边同时乘以$z^2$消去分母：
$$z^2f(z) - z -2 -6z(f(z) - \frac{1}{z}) +5f(z) = 0$$
展开后合并同类项：
$$f(z)(z^2 -6z +5) + (-z -2 +6z) = 0$$
整理后就能解出$f(z)$：
$$f(z) = \frac{2 -5z}{z^2 -6z +5}$$

关键思路总结 #

• 核心是用递推关系把生成函数的无穷级数转化为有限的代数方程，通过对齐级数的项来抵消无穷部分；
• 别忘了初始项的处理，因为递推关系只从$n≥3$开始成立，前两项需要单独拿出来；
• 乘以$z$的幂次消去分母是简化计算的常用技巧。

内容的提问来源于stack exchange，提问作者L.Z.