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}

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.
