矩阵递推斐波那契数列

  斐波那契数列都很熟悉，它满足, /(F_{n} = /begin{cases}1&n/leqslant2//F_{n – 1} + F_{n – 2}&n > 2/end{cases}/) 。
因为/(F_n/)从第三项开始是不断的递推下去的，所以我们可以考虑用矩阵加速递推。
  设/(Fib/left( n/right)/)表示一个/(1×2/)的矩阵/(/begin{bmatrix}F_n& F_{n – 1}/end{bmatrix}/).我们希望根据/(Fib/left( n – 1/right) = /begin{bmatrix}F_{n – 1}&F_{n – 2}/end{bmatrix}/)推出/(Fib/left( n/right)/)。
  因为/(Fib_n = Fib_{n – 1} + Fib_{n – 2}/)，所以我们引入一个辅助矩阵/(base/),第一列应该为/(/begin{bmatrix}1//1/end{bmatrix}/),这样在进行矩阵乘法运算的时候才能令/(F_{n – 1}/)和/(F_{n – 2}/)相加，从而得出/(F_{n}/),同理为了得出/(F_{n – 1}/)，矩阵/(base/)的第二列应该为/(/begin{bmatrix}1//0/end{bmatrix}/).
  综上所述: /(base = /begin{bmatrix}1&1//1&0/end{bmatrix}/)原式化为$$/begin{bmatrix}F_{n – 1}&F_{n – 2}/end{bmatrix}×/begin{bmatrix}1&1 // 1&0/end{bmatrix} = /begin{bmatrix}F_{n – 1} × 1 + F_{n – 2}×1&F_{n – 1}×0 + F_{n – 2}×1/end{bmatrix} = /begin{bmatrix} F_{n}&F_{n – 1} /end{bmatrix}$$
  这样我们就可以根据/(/begin{bmatrix}F_{2}&F_{1}/end{bmatrix}/)一直与/(/begin{bmatrix}1&1//1&0/end{bmatrix}/)进行矩阵乘法运算从而递推出/(/begin{bmatrix}F_{n}&F_{n – 1}/end{bmatrix}/)。
  那么定义/(ans = /begin{bmatrix}F_{2}&F_{1}/end{bmatrix},base = /begin{bmatrix}1&1//1&0/end{bmatrix}/),通过观察发现从/(/begin{bmatrix}F_{2}&F_{1}/end{bmatrix}/)递推出/(/begin{bmatrix}F_{n}&F_{n – 1}/end{bmatrix}/)只需要做/(n – 2/)次矩阵乘法。所以可以得出$$Fib/left( n/right) = ans×base^{n – 2}$$