利用普通生成函数解斐波那契数列的通项问题
最近一场模拟赛考了这个公式，发现自己不会证，在 @Y_B_X 大佬的帮助下学会了证明，记录一下方便复习
- 问题：定义斐波那契数列 (f_i=f_{i-1}+f_{i-2},f_1=f_2=1)，求 ({ f_i }) 通项。
解：首先设 ({ f_i }) 的普通生成函数为
[F(x)=sumlimits_{k geq 1}{f_kx^k}
]
按套路，设
[G(x)=sumlimits_{k geq 3}{f_kx^k}=F(x)-x-x^2
]
那么有:
[G(x)=sumlimits_{k geq 3}{f_kx^k}=sumlimits_{k geq 3}{(f_{k-1}+f_{k-2})x^k}=xsumlimits_{k geq 2}{f_kx^k}+x^2 sumlimits_{k geq 1}{f_kx^k}=x(F(x)-x)+x^2F(x)
]
结合 (G(x)=F(x)-x-x^2)，移项解得：
[F(x)=frac{x}{1-x-x^2}
]
这就是斐波那契数列的生成函数。
到了这一步，我们将它级数展开，按套路设：
[frac{x}{1-x-x^2}=frac{x}{(1-x·x_1)(1-x·x_2)}=frac{A}{1-x·x_1}+frac{B}{1-x·x_2}
]
可解得 (x_1=frac{1 + sqrt 5}{2},x_2=frac{1 - sqrt 5}{2})，整理上式有：
- (frac{x}{1-x·x_2}=A+frac{1-x·x_1}{1-x·x_2}B)
-
(frac{x}{1-x·x_1}=A+frac{1-x·x_2}{1-x·x_1}B)
在这两个式子中分别令 (x·x_1=1,x·x_2=1)，最后可解出：
[A=frac{1}{sqrt 5},B=-frac{1}{sqrt 5}
]
将 (F(x)=frac{A}{1-x·x_1}+frac{B}{1-x·x_2})级数展开：
[F(x)=A(sumlimits_{k geq 1}{(x·x_1)^k})+B(sumlimits_{k geq 1}{(x·x_2)^k})
]
将 (A,B,x_1,x_2) 全部代入，最后有：
[F(x)=sumlimits_{k geq 1}[frac{1}{sqrt 5}(frac{1 + sqrt 5}{2})^k-frac{1}{sqrt 5}(frac{1 - sqrt 5}{2})^k]x^k
]
于是有斐波那契数列的通项公式：
[f_n=[x^n]F(n)=frac{1}{sqrt 5}(frac{1 + sqrt 5}{2})^n-frac{1}{sqrt 5}(frac{1 - sqrt 5}{2})^n
]
P.S.
- 若 (f_0=f_1=1)，则通项公式为：
[f_n=frac{1}{sqrt 5}(frac{1 + sqrt 5}{2})^{n+1}-frac{1}{sqrt 5}(frac{1 - sqrt 5}{2})^{n+1}
]