二阶线性递推（生成函数）

就是长得像这样的：
a n+2 ${n+2}_{}$=pa n+1 ${n+1}_{}$+qa n $n_{}$
大名鼎鼎的 斐波那契数列 a n+2 ${n+2}_{}$=a n+1 ${n+1}_{}$+a n $n_{}$ 就符合这个

同样：令f(x)=a 0 $0_{}$x 0 $0^{}$+a 1 $1_{}$x 1 $1^{}$+……+a n $n_{}$x n $n^{}$ ——①

而：
-pxf(x)=-pa 0 $0_{}$x 1 $1^{}$-pa 2 $2_{}$x 2 $2^{}$-……-pa n $n_{}$x n+1 ${n+1}^{}$ ——②

-qx 2 $2^{}$f(x)=-pa 0 $0_{}$x 2 $2^{}$-pa 1 $1_{}$x 3 $3^{}$-……-pa n $n_{}$x n+2 ${n+2}^{}$ ——③

①+②+③：
(1-px+qx 2 $2^{}$)f(x)=a 0 $0_{}$+(a 1 $1_{}$-pa 0 $0_{}$)x+(a 2 $2_{}$-a 1 $1_{}$-qa 0 $0_{}$)x 2 $2^{}$+(a 3 $3_{}$-a 2 $2_{}$-qa 1 $1_{}$)x 3 $3^{}$+…+(a n+2 ${n+2}_{}$-a n+1 ${n+1}_{}$-qa n $n_{}$)x n+2 ${n+2}^{}$

关键来了：为啥我们要这样构造呢？
因为 a n+2 ${n+2}_{}$=pa n+1 ${n+1}_{}$+qa n $n_{}$ 移一下项就是：a n+2 ${n+2}_{}$-pa n+1 ${n+1}_{}$-qa n $n_{}$=0
因此，①+②+③就变成了：

(1-px+qx 2 $2^{}$)f(x)=a 0 $0_{}$+(a 1 $1_{}$-pa 0 $0_{}$)x

f(x)= a0+(a1−pa0)x(1−px+qx2) $\frac{a_0+(a_1-p{a}_0)x}{(1-px+q{x}^2)}$

同理拆开成：f(x)= k11−b1x $\frac{k1}{1-b_{1}x}$+ k21−b2x $\frac{k2}{1-b_{2}x}$的样子，再展开回去就阔以啦~

这里我们就用斐波那契数列p=1,q=1的时候来说吧：
这里我们把a 1 $1_{}$当第一项，a 2 $2_{}$当第二项，a 1 $1_{}$=1,a 2 $2_{}$=1
f(x)= 11−x−x2 $\frac{1}{1-x-x^2}$= 1(1−1−5–√2x) $\frac{1}{(1-\frac{1-\sqrt{5}}{2}x)}$ 1(1−1+5–√2x) $\frac{1}{(1-\frac{1+\sqrt{5}}{2}x)}$

令：
a= 1−5–√2 $\frac{1-\sqrt{5}}{2}$
b= 1+5–√2 $\frac{1+\sqrt{5}}{2}$
f(x)= 11−x−x2 $\frac{1}{1-x-x^2}$= 11−ax $\frac{1}{1-ax}$ 11−bx $\frac{1}{1-bx}$

= 15–√ $\frac{1}{\sqrt{5}}$( 11−ax $\frac{1}{1-ax}$- 11−bx $\frac{1}{1-bx}$)

= 15–√∑∞n=0 $\frac{1}{\sqrt{5}}\sum _{n=0}^{\infty }$( (ax) n $n^{}$-(bx) n $n^{}$)

= ∑∞n=0 $\sum _{n=0}^{\infty }$ 15–√ $\frac{1}{\sqrt{5}}$( (a) n $n^{}$-(b) n $n^{}$)x n $n^{}$

So：a n $n_{}$= 15–√ $\frac{1}{\sqrt{5}}$( ( 1−5–√2 $\frac{1-\sqrt{5}}{2}$) n $n^{}$-( 1+5–√2 $\frac{1+\sqrt{5}}{2}$) n $n^{}$
(￣▽￣)~*