Need help understanding Fibonacci Fast Doubling Proof From this website, http://www.nayuki.io/page/fast-fibonacci-algorithms (fast doubling proof close to the bottom of the page).
I have understood the proof for the most part but I am struggling to see how this part of the proof works especially when the the F(n) function is squared.
\begin{align}
   F(2n+1) &= F(n+1)^2 + F(n)^2. \\
   F(2n) &= F(n) \left[ F(n+1) + F(n-1) \right] \\
   &= F(n) \left[ F(n+1) + (F(n+1) - F(n)) \right] \\
   &= F(n) \left[ 2F(n+1) - F(n) \right]. \\
   F(2n-1) &= F(n)^2 + F(n-1)^2.
  \end{align}
 A: Start with:
$$F(n+1) = F(n) + F(n-1)$$
Rewrite as:
$$\begin{align} F(n + 1) &= F(n) + F(n-1) \\
                F(n) &= F(n) \end{align}$$
which is:
$$\begin{align}
\begin{bmatrix} F(n+1) \\ F(n)\end{bmatrix}
&=
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}
\begin{bmatrix} F(n) \\ F(n-1)\end{bmatrix} \\ &=
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^2
\begin{bmatrix} F(n-1) \\ F(n-2)\end{bmatrix} \\ &=
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^3
\begin{bmatrix} F(n-1) \\ F(n-3)\end{bmatrix} \\ & \dots \\ &=
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n
\begin{bmatrix} F(1) \\ F(0)\end{bmatrix} 
\end{align}$$
Taking $F(0) = 0$ and $F(1) = 1$, you get:
$$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{bmatrix}$$
So to use "doubling", we just plug $2n$ into the formula:
$$\begin{align}
\begin{bmatrix} F(2n+1) \\ F(2n)\end{bmatrix}
&=
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{2n}
\begin{bmatrix} F(1) \\ F(0)\end{bmatrix}  \\ \\ &=
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n}
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n}
\begin{bmatrix} F(1) \\ F(0)\end{bmatrix}  \\ \\ &=
\begin{bmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{bmatrix}
\begin{bmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{bmatrix}
\begin{bmatrix} 1 \\ 0 \end{bmatrix}  \\ \\ &=
\begin{bmatrix} F(n+1)^2 + F(n)^2 \\ F(n)F(n+1) + F(n-1)F(n) \end{bmatrix} \\ 
\\ ~
\\ & \text{And if you want...}
\\ ~
\\ &=
\begin{bmatrix} F(n+1)^2 + F(n)^2 \\ F(n)F(n+1)+ \bigg(F(n+1) - F(n)\bigg)F(n) \end{bmatrix}\\ \\&=
\begin{bmatrix} F(n+1)^2 + F(n)^2 \\ 2F(n+1)F(n) - F(n)^2 \end{bmatrix}
\end{align}$$
Which isn't actually better than matrix exponentiation asymptotically.  And regardless, since the Fibonacci sequence grows exponentially, it will always require exponential time to compute just due to the size of the output.  The matrix or "doubling" approach takes you from $O({\rm exp}~x^2)$ to $O({\rm exp}~x)$ asymptotic calculation time, which isn't nothing, but it still isn't exactly tractable either.
A: This follows immediately by looking at the preceding lines. Since the two square matrices are equal, each corresponding entry must be equal. By looking at the $(1,1)$-entry we get $F(2n+1)=F(n+1)^2+F(n)^2$; by looking at either the $(1,2)$- or $(2,1)$-entry we get $F(2n)=F(n)F(n+1)+F(n)F(n-1)$, from which the other lines are just basic manipulations.
A: While playing around with the Fibonacci series. I found a way to compute nth Fibonacci number in Log(N) complexity without using matrices.
My method is simpler and intuitive and could be used for self derivation.
I wrote a medium blog regarding this. Thought it would be helpful.
https://medium.com/@ani1998ket/deriving-the-fast-fibonacci-identities-without-matrices-o-log-n-4cd9ce69d9d4
