??斐波那契数，又称黄金分割数列，是指数列:\(0,1,1,2,3,5,8,……\)。表示后一个数由前两个数的和组成，递归上定义为\(f[0]=0,f[1]=1,f[i]=f[i-1]+f[i-2]\)。
??接下来用推导斐波那契数的通项公式：
??假设常数s、r满足：
????\(f[n]-r*f[n-1]=s*(f[n-1]-r*f[n-2])\)
??再结合斐波那契数的定义，我们可以得到：
????\(r+s=1,rs=-1\)
??所以，对于\(n≥3\)时，有：
????\(f[n]-r*f[n-1]=s*(f[n-1]-r*f[n-2])\)
????\(f[n-1]-r*f[n-2]=s*(f[n-2]-r*f[n-3])\)
????\(……\)
????\(f[3]-r*f[2]=s*(f[2]-r*f[1])\)
??我们联立这n-2个式子，可以得到：
????\(f[n]-r*f[n-1]=s^{n-2}*(f[2]-r*f[1])\)
??因为：
????\(s=1-r,f[1]=f[2]=1\)
??所以可以化简：
????\(f[n]=s^{n-1}+r*f[n-1]\)
???????\(=s^{n-1}+r*s^{n-2}+r^2*f[n-2]\)
???????\(=s^{n-1}+r*s^{n-2}+r^2*s^{n-3}+r^3*f[n-3]\)
???????\(……\)
???????\(=s^{n-1}+r*s^{n-2}+r^2*s^{n-3}+……+r^{n-1}\)
??这就是一个以\(s^{n-1}\)为首项，\(r^{n-1}\)为末项，\(\frac{r}{s}\)为公比的等比数列，直接运用等比数列求和公式：
\[原式=\frac{s^{n-1}-r^{n-1}*\frac{r}{s}}{1-\frac{r}{s}}\]
\[=\frac{s^n-r^n}{s-r}\]
??因为前文求出的两个关于\(r、s\)的式子其中一组解为：
\[s=\frac{1+\sqrt{5}}{2},r=\frac{1-\sqrt{5}}{2}\]
??所以通项公式为：
\[f[n]=\frac{\sqrt{5}}{5}*[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]\]
??给出以下定义在非负整数n下的递归关系：
\[f[n]=
\begin{cases}
f_0 \qquad \qquad \qquad \qquad n=0 \ f_1 \qquad \qquad \qquad \qquad n=1 \ a*f[n-1]+b*f[n-2] \qquad otherwise
\end{cases}
\]
??其中\(a、b\)是满足以下两个条件的常数：
??(一)\(a^2+4b>0\)
??(二)\(|a-\sqrt{a^2+4b}|≤2\)
??给出\(f_0,f_1,a,b,n\)，求\(f[n]\)
?
??我们考虑直接暴推公式，用类似斐波那契数的方法求得公式为：
\[f[n]=\frac{s^n(f_1-mf_0)-r^n(f_1-kf_0)}{s-r}\]
??其中：
\[s、r=\frac{a±\sqrt{a^2+4b}}{2}\]
??直接快速幂求解就行了。
??然而推完式子后发现这实际上是复杂度理论上和矩阵快速幂一样的，而且矩阵快速幂好写很多，然后就不想写代码了。
原文：https://www.cnblogs.com/fangbozhen/p/11755699.html