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)^2
but 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!
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}$$