斐波那契数列（特征方程，通项公式，公约数）

1、求特征方程

设有数列 $c[n] = a * c[n - 1] + b * c[n - 2]$ , 假设存在 $x, y$ 满足下式
$c[n]-x*c[n - 1] = y*(c[n - 1] - x*c[n - 2])$
变形得
$c[n] = (x + y) * c[n - 1] -xy * c[n - 2]$
则对于斐波那契数列则有
$\begin{eqnarray*} x + y &=& 1 \\ -xy&=&1 \end{eqnarray*}$

消去 $y$ 得 $x^2=x+1$

有根
$X_{1,2}=\frac{1\pm\sqrt{5}}{2}$

所以存在 $A, B$ 使
$c[n] = A \times \left( \frac{1 + \sqrt{5}}{2} \right) ^{n} - B \times \left( \frac{1 - \sqrt{5}}{2} \right) ^{n}$
代入 $c[0] = 0, c[1] = 1$ ,得
$A = \frac{\sqrt{5}}{5}, B = - \frac{\sqrt{5}}{5}$
即通项公式为
$c[n] = \frac{\sqrt{5}}{5} \times \left(\frac{1 + \sqrt{5}}{2}\right) ^ {n} - \frac{\sqrt{5}}{5} \times \left(\frac{1 - \sqrt{5}}{2}\right) ^ {n}$

Tips

这公式一般不用再程序题中，因为有无理数无法保证精度

2、公约数

$gcd(F[n], F[m]) = F[gcd(n, m)]$

证明：

设 $n < m, F[n] = a, F[n + 1] = b$ ,则有
$\begin{eqnarray*} F[n + 2] &=& a + b \\ F[n + 3] &=& a + 2b \\ F[n + 4] &=& 2a + 3b\\ F[n + 5] &=& 3a + 5b\\ \cdots &=& \cdots \end{eqnarray*}$
则有
$F[m] = F[m-n-1] \times F[n] + F[m-n] \times F[n+1]$

$gcd(F[n],F[m]) = gcd(F[n], F[m - n -1] \times F[n] + F[m - n] \times F[n + 1] )$

化简则有
$gcd(F[n], F[m]) = gcd(F[n], F[m - n] \times F[n + 1] )$
由于
$gcd(F[n], F[n + 1]) = 1$
可得
$gcd(F[n], F[m]) = gcd(F[n], F[m - n])$
即
$gcd(F[n], F[m]) = gcd(F[n], F[m \mod n])$