说实话这个东西其实挺有趣的。

证明的话其实我不是很会，貌似是用矩阵证明是一个范德蒙德矩阵是有唯一解的。

我们直接举例子来说吧。

$f(n) = f(n - 1) + f(n - 2)$。

设 $F(z) = \sum_{i = 1}^{\infty} f(i) z^i$，显然存在这样的方程满足。

$$F(z)z^2 = F(z)z + F(z)$$
那么我们将其移项可以得到：

$$F(z)(z^2 - z - 1) = 0$$
显然 $F(z)$ 不为 $0$，那么我们让后面的那个东西 $= 0$。其实后面的柿子就是特征方程。

我们容易解出两个解 $z = \frac{1 \pm \sqrt 5}{2}$。

得到 $f(n) = Ax_1^n + Bx_2^n$ 我们带入前面的两个值 $f(1) = f(2) = 1$ 得到 $A = \frac{1}{\sqrt 5}, B = - \frac{1}{\sqrt 5}$ 可以求出通项。

$$f(n) = \frac{\left(\frac{1 + \sqrt 5}{2}\right)^n - \left(\frac{1 - \sqrt 5}{2}\right)^n}{\sqrt 5}$$

至于生成函数的解法，就是把之前的柿子拆成两项的形式，然后对于两项分别求出生成函数之后相加减即可。