I was trying to derive following equation to compute the nth fibonacci number in O(log(n)) time.
F(2n) = (2*F(n-1) + F(n)) * F(n)which i found on wiki form the fibonacci matrix equation stated there but i stuck in deriving it. I understood the derivation till the
(-1)^n = F(n+1)*F(n-1) - F(n)^2but then how do we reach from the above equation to the below equation is unclear to me.
F(m)*F(n) + F(m-1)*F(n-1) = F(m + n-1)In the wiki page only a single line is mentioned which says
since $A^n A^m = A^{n+m}$ for any square matrix A, the following identities can be derived (they are obtained form two different coefficients of the matrix product, and one may easily deduce the second one from the first one by changing n into n + 1),
please help me in understanding the derivation.
Thanks in anticipation!
$\endgroup$ 72 Answers
$\begingroup$The Wiki reference shows that for $n>1$ you can recover $F_n$ as the (1,1) component of $$A^{n-1}= \begin{pmatrix}1 & 1\\ 1& 0\end{pmatrix}^{n-1} = \begin{pmatrix}F_n & F_{n-1}\\ F_{n-1}& F_{n-2}\end{pmatrix}$$ (you also could use the other elements). Now compute the matrix product $$\begin{pmatrix}F_n & F_{n-1}\\ F_{n-1}& F_{n-2}\end{pmatrix} \times \begin{pmatrix}F_m & F_{m-1}\\ F_{m-1}& F_{m-2}\end{pmatrix} =\begin{pmatrix}F_n F_m + F_{n-1}F_{m-1} & *\\ * & *\end{pmatrix} =A^{n-1}A^{m-1} = A^{n+m-2} = \begin{pmatrix}F_{n+m-1} & F_{n+m-2}\\ F_{n+m-2}& F_{n+m-3}\end{pmatrix} $$ and read-off the $(1,1)$ component to get
$$F_n F_m + F_{n-1}F_{m-1} = F_{n+m-1}$$
$\endgroup$ $\begingroup$A simpler explanation of @gammamatester's fantastic answer:
For $n>1$ you can recover $F_n$ as the (1,0) component of $$A^{n}= \begin{pmatrix}1 & 1\\ 1& 0\end{pmatrix}^{n} = \begin{pmatrix}F_{n+1} & F_{n}\\ F_{n}& F_{n-1}\end{pmatrix}$$
We know that $$A^{N} * A^{M} = A^{N+M}$$ that is by multiplying the matrices of $n^{th}$ and $m^{th}$ fibonacci numbers, we'll get the matrix of $(n+m)^{th}$ fibonacci.
Now putting $n$ =$m$ : $$A^{N} * A^{N} = A^{2N}$$
$$\begin{pmatrix}F_{n+1} & F_{n}\\ F_{n}& F_{n-1}\end{pmatrix} \times \begin{pmatrix}F_{n+1} & F_{n}\\ F_{n}& F_{n-1}\end{pmatrix} =\begin{pmatrix}F_{n+1}^2 + F_{n}^2 & F_{n}(F_{n+1}+ F_{n-1})\\ F_{n}(F_{n+1}+ F_{n-1}) & F_{n}^2 + F_{n-1}^2\end{pmatrix} = A^{2n} = \begin{pmatrix}F_{2n+1} & F_{2n}\\ F_{2n}& F_{2n-1}\end{pmatrix} $$
For even indices, compare $(0,1)$ entry:
$$F_{2n} = F_{n}(F_{n+1}+ F_{n-1})$$
For odd indices, compare $(0,0)$ entry:
$$F_{2n+1} = F_{n+1}^2 + F_{n}^2$$
$\endgroup$
