$n^{2}th$ Fibonacci number Question

Let $F_k$  denote the $k_{th}$ Fibonacci number.  Then, the $n^{2}th$ Fibonacci number $F_n$    can be  computed in $O(\log n)$ time.

My Approach/Confusion
Above question is taken from MIT quiz .I am solving it just to practice and build the concept.
I know that Recurrence relation for Fibonacci number is
$F(k)=F(k-1)+F(k-2)$  solving this , $F(k)=O(2^{k})$
I am not getting how the $n^{2}th$ Fibonacci number $F_n$    can be  computed in $O(\log n)$ time.
 A: The challenge of finding fast algorithms for computing Fibonacci numbers gives interesting insights into how one should best compute recursively defined entities. See https://www.nayuki.io/page/fast-fibonacci-algorithms for a short introduction.
In this case, you should use the identity
$$\left[ \begin{array}{ll} 1 & 1 \\
1 & 0 \end{array}\right]^n = \left[ \begin{array}{ll} F(n+1) & F(n) \\
F(n) & F(n-1)  \end{array}  \right]$$
and exponentiation by repeated squaring of matrices. 
A: Hint: use the Fibonacci relation on the terms in the Fibonacci relation:
$$
F(k)=F(k-1)+F(k-2)\\
=2F(k-2)+F(k-3)\\
=3F(k-3)+2F(k-4)
$$
and so on. If you do it a few more steps, you should recognize the pattern in the coefficients. Stop at the most convenient step, and then use this same method to calculate those terms. In the end, this gives you an $O(\log k)$ algorithm.
A: The recurrence relation can actually find $F_n$ in $O(n)$ if you keep both $F_k$ and $F_{k-1}$ in memory.
However, a more efficient method is to use the matrix formula for the Fibonacci numbers.  If $A$ is the matrix that has a $0$ in the top left corner and $1$ elsewhere, then $A^n=\pmatrix{F_{n-1} & F_n \\ F_n & F_{n+1}}$.  However, you can compute the $n$th power by repeated squaring (or multiplying by $A$), and this takes approximately $\log n$ steps.
A: the $n^{th}$ Fibonacci number is 
$\frac {\phi^n - \phi'^n}{\phi - \phi'}$
Where $\phi = \frac {1+\sqrt{5}}{2}$ and $\phi' = \frac {1-\sqrt{5}}{2}$
That doesn't take very many steps at all.
