斐波那契

斐波那契

首先回忆一下这是个什么东西：

（别名：兔子数列）

数：  1 1 2 3 5 8 13 21 34 55 89 ……
下标：1 2 3 4 5 6 7  8  9  10 11 ……

通项公式

$\frac{1}{\sqrt5}[(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n]$

提示：递推公式推论即可

$F[n]=F[n-1]+F[n-2]$

$F[1]=1$

$F[2]=1$

gcd

和最大公约数

$gcd(F(n)+F(m))=F(gcd(n,m))$

矩阵

$$\left[ \begin{matrix} 1 & 3 \\ 2 & 2 \\ \end{matrix} \right]\times \left[ \begin{matrix} 2 & 4 & 3 \\ 3 & 2 & 1 \\ \end{matrix} \right]= \left[ \begin{matrix} 11 & 10 & 6 \\ 10 & 12 & 8 \\ \end{matrix} \right]$$

形状上：2*2 和 2*3 的矩阵乘积后,结果是 2*3 的矩阵。

即 a*b 矩阵 和 c*d 的矩阵乘积结果是 a*d 的矩阵。其中 b 和 c 必须相等。原因看下面。

运算法则：对于结果矩阵的第 i 行第 j 列的位置的结果是由前一个矩阵的对应的行。和后一个矩阵对应的列。对应位置乘积和获得的。
    
比如第 1 行第 1 列的 11.是由前矩阵的第一行 (1,3) 和后矩阵的第一列 (2,3) 对应位置乘积和。
    
1*2 + 3*3 = 11 获得的。
    
如果上述 b 和 c 如果不相等。那么会有地方"失配"没有数值可以进行计算。不符合矩阵乘法定义。

问题来了矩阵跟斐波那契有啥关系？

$$\left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right]\times \left[ \begin{matrix} F(1) \\ F(0) \\ \end{matrix} \right]= \left[ \begin{matrix} F(1) + F(0) \\ F(1) \\ \end{matrix} \right]= \left[ \begin{matrix} F(2) \\ F(1) \\ \end{matrix} \right]$$

同样：

$$\left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right]\times \left[ \begin{matrix} F(2) \\ F(1) \\ \end{matrix} \right]= \left[ \begin{matrix} F(2) + F(1) \\ F(2) \\ \end{matrix} \right]= \left[ \begin{matrix} F(3) \\ F(2) \\ \end{matrix} \right]$$

整理一下：

$$\left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right]\times \left[ \begin{matrix} F(n-1) \\ F(n-2) \\ \end{matrix} \right]= \left[ \begin{matrix} F(n-1) + F(n-2) \\ F(n-1) \\ \end{matrix} \right]= \left[ \begin{matrix} F(n) \\ F(n-1) \\ \end{matrix} \right]$$

求 $n$ 次方乘 $n$ 次即可，可以快速矩阵求解。

其他公式

• $F(1)+F(2)+F(3)+……+F(n)=F(n+2)-1$

• $F(1)^2+F(2)^2+F(3)^2+……+F(n)^2=F(n)\times F(n+1)$

• $F(1)+F(3)+F(5)+……+F(2n-1)=F(2n)$

• $F(2)+F(4)+F(6)+……+F(2n)=F(2n+1)-1$

• $F(n)=F(m)\times F(n-m+1)+F(m-1)\times F(n-m)$

• $ps:n>=m$

• $F(n-1)\times F(n+1)=F(n)^2+(-1)^n$