斐波拉契数列前n项和的求法

求法"/>

斐波拉契数列前n项和的求法

一、递推关系构建系数矩阵–矩阵快速幂

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪S[n]=S[n−1]+fac[n]fac[n+1]=fac[n]+fac[n−1]fac[n]=fac[n] { S [ n ] = S [ n − 1 ] + f a c [ n ] f a c [ n + 1 ] = f a c [ n ] + f a c [ n − 1 ] f a c [ n ] = f a c [ n ] $$\begin{cases} S[n] = S[n-1] + fac[n] \\&&&&\\ fac[n+1] = fac[n] + fac[n-1] \\&&&&\\fac[n] = fac[n] \end{cases}$$

系数矩阵如下：

⎡⎣⎢⎢⎢⎢⎢⎢S[n]fac[n+1]fac[n]⎤⎦⎥⎥⎥⎥⎥⎥=⎡⎣⎢⎢⎢⎢⎢⎢100111010⎤⎦⎥⎥⎥⎥⎥⎥∗⎡⎣⎢⎢⎢⎢⎢⎢S[n−1]fac[n]fac[n−1]⎤⎦⎥⎥⎥⎥⎥⎥ [ S [ n ] f a c [ n + 1 ] f a c [ n ] ] = [ 1 1 0 0 1 1 0 1 0 ] ∗ [ S [ n − 1 ] f a c [ n ] f a c [ n − 1 ] ] $$\left[ \begin{matrix}S[n] \\\\fac[n+1]\\\\fac[n]\end{matrix} \right] =\left[\begin{matrix}1&1&0\\\\0&1&1\\\\0&1&0\end{matrix}\right] *\left[\begin{matrix}S[n-1]\\\\fac[n]\\\\fac[n-1]\end{matrix}\right]$$
递推得到：
⎡⎣⎢⎢⎢⎢⎢⎢S[n]