首先考虑齐次的.
这一类题目类型为:
已知 $a_0,\,a_1,\,\dots,\,a_{k-1}$, 且对于 $\forall n \ge k$, $a_n = \sum_{j=1}^k c_j a_{n-j}$, 求 $\{a_n\}_{n=0}^{\infty}$ 的生成函数 (又名 母函数, generating function).
当 $k$ 较大时, 通过特征方程是没什么希望了, 所以还得利用生成函数的定义以及形式幂级数的性质. 具体过程如下.
\begin{align*}\sum_{n=0}^{\infty} a_n x^n &= \sum_{n=k}^{\infty} a_n x^n + \sum_{n=0}^{k-1} a_n x^n \\&= \sum_{n=k}^{\infty} \sum_{j=1}^k c_j a_{n-j} x^n + \sum_{n=0}^{k-1} a_n x^n \\&= \sum_{j=1}^k c_j x^j \sum_{n=k-j}^{\infty} a_n x^n + \sum_{n=0}^{k-1} a_n x^n \\&= \sum_{j=1}^k c_j x^j \sum_{n=0}^{\infty} a_n x^n – \sum_{j=1}^k c_j x^j \sum_{n=0}^{k-j-1} a_n x^n + \sum_{n=0}^{k-1} a_n x^n.\end{align*}
到此, 只需要通过移项, 稍作化简即可.
\[ \bigg( 1-\sum_{j=1}^k c_j x^j \bigg) \sum_{n=0}^{\infty} a_n x^n = \sum_{n=0}^{k-1} a_n x^n – \sum_{j=1}^k c_j x^j \sum_{n=0}^{k-j-1} a_n x^n. \]
一个简单例子, Fibonacci 数 $F_0=0,\, F_1=1,\, F_n = F_{n-1} + F_{n-2}$.
\[ (1-x-x^2) \sum_{n=0}^{\infty} F_n x^n = x – 0, \]
即 Fibonacci 数的生成函数为
\[ \sum_{n=0}^{\infty} F_n x^n = \frac x {1-x-x^2}. \]
根据生成函数得到通项公式主要利用最基本的幂级数
\[ \frac1{1-x} = \sum_{n=0}^{\infty} x^n. \]
但一般的公式就没有了, 思路如下, 同样以 Fibonacci 数为例.
\begin{align*} \frac x{1-x-x^2} &= x \sum_{j=0}^{\infty} (x+x^2)^j \\
&= \sum_{j=0}^{\infty} x^{j+1} (1+x)^j \\
&= \sum_{j=0}^{\infty} x^{j+1} \sum_{n-j-1=0}^j \binom j {n-j-1} x^n \\
&= \sum_{n=0}^{\infty} \sum_{j \ge (n-1)/2}^{n-1} \binom j {n-j-1} x^n \\
&= \sum_{n=0}^{\infty} \sum_{j = 0}^{(n-1)/2} \binom {n-j-1}j x^n.\end{align*}
这样就得到了
\[ F_n = \sum_{j = 0}^{(n-1)/2} \binom {n-j-1}j = \sum_{j = 0}^{n-1} \binom {n-j-1}j. \]
可能有人已经发现了, 这不就是 Fibonacci 数和杨辉三角 (西方谓之为 Pascal 三角) 的关系吗.
对于复杂的生成函数, 可以利用 H.~S. Wilf. {\em Generatingfunctionology}. Academic Press, Inc., San Diego, second edition, 1994. 中介绍的 系数提取算子 (coefficient extraction operator) $[x^n]$, 即多项式中 $x^n$ 的系数. 一个不错的性质就是
\[ [x^n]\{ x^m f(x) \} = [x^{n-m}]f(x). \]
有兴趣的可以再自行研究.
另外, 对于非齐次, 麻烦的就是在计算生成函数时会有小尾巴, 方法思路和这个完全一样.