二阶齐次线性递推通项公式的寻找

---

前置技能：斐波那契数列与二阶线性递推

斐波那契数列$f(n)$是递归定义的：

$$f(n)=f(n-1)+f(n-2), n\ge 2$$

其中$f(0) = 0, f(1) = 1$。如果使用艾弗森约定处理分段，可以用一个公式统一：

$$f(n)=f(n-1)+f(n-2)+[n=1]$$

一般地，一个二阶线性递推式被递归地定义：

$$g(n) = \alpha g(n-1)+\beta g(n-2), n\ge 2$$

其中$g(0) = \lambda, g(1) = \mu$。同样地，使用艾弗森约定可以变形为：

$$g(n)=\alpha g(n-1)+\beta g(n-2)+\lambda [n=0]+(\mu-\lambda \alpha)[n=1]$$

容易证明这两种表达形式具有等价性。

技术：生成函数

一个数列$g(n)$的生成函数为$G(n) = \left<g(n)\right>$，被定义为：

$$G(n) = \sum_{n}g(n)z^n$$

其中$z$是一个形式变量。其中许多生成函数可以被写成紧凑的封闭形式，《具体数学》中指出，在写成封闭形式时我们一般不必考虑级数的收敛性。我们考虑一种特殊形式生成函数的封闭形式，其中$g(n) = k\rho^n$，根据定义有：

$$G(n) = \sum_{n}k\rho^nz^n = k+\rho z\sum_{n}g_nz^n=k+\rho zG(n)$$

解得：$G(n) = \frac k {1-\rho z}$

反过来，如果我们知道了一个函数的生成函数形如：$G(n) = \frac k {1-\rho z}$，我们就可以断言，这个数列的第$n$项必然是$[z^n]G=\rho^n$。这将是我们解决问题的关键。

计算过程

$$g(n)=\alpha g(n-1)+\beta g(n-2)+\lambda [n=0]+(\mu-\lambda \alpha)[n=1]$$

由于$g(n-1)=\left<0,g(0),g(1),\dots\right>$，可以发现其生成函数为$zG(n)$。同样的，$g(n-2)$的生成函数是$z^2G(n)$。对于仅在$n=1$时有值的项$(\mu-\lambda a)[n=1]$，其生成函数自然是$(\mu-\lambda a)z$。上式被改写为：

$$G(n)=\alpha zG(n)+\beta z^2G(n)+\lambda+(\mu-\lambda a)z$$

解方程得到：

$$G(n) = \frac {\lambda+(\mu-\lambda \alpha)z} {1-\alpha z-\beta z^2}$$

考虑将这个式子表示成$\frac A {1-pz}+\frac B {1-qz}$的形式，以便用上面的技术解决问题。通分后得到分母的方程：

$$(1-pz)(1-qz)=1-\alpha z-\beta z^2$$

也就是：

$$pq = -\beta\\p+q=\alpha$$

解得：

$$p = \frac {\alpha+t} 2, q = \frac {\alpha-t} 2, t = \sqrt{\alpha^2+4\beta}$$

分子的方程则是：

$$A(1-qz)+B(1-pz) = \lambda+(\mu-\lambda \alpha)z$$

展开并解方程，得到：

$$A = \frac {\lambda t-\lambda \alpha+2\mu}{2t},B = \frac {\lambda \alpha+\lambda t-2\mu} {2t}$$

则我们断言，原方程第$n$项$[z^n]G=Ap^n+Bq^n$。整理后也就是：

$$\frac {\lambda t-\lambda \alpha+2\mu}{2t}\left(\frac {\alpha+t}2\right)^n+\frac {\lambda \alpha+\lambda t-2\mu} {2t}\left(\frac {\alpha-t} 2\right)^n$$

代入数据发现可以满足斐波那契数列和一些小的情景，我们基本可以确定这个公式的正确性。

其他

运用同样的技术，我们可以方便地处理含有常数项甚至$f(n)$项的线性递推数列。