In my reference, Exercise 0.4(e), Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, it is given that $$ \begin{bmatrix}F_n\\F_{n+1}\end{bmatrix}=\begin{bmatrix}0&1\\1&1\end{bmatrix}^n\begin{bmatrix}F_0\\F_1\end{bmatrix} $$
Prove that the running time of $fib3$ is $\mathcal{O}(M(n))$, where $M(n)$ be the running time of an algorithm for multiplying n-bit numbers, and assume that $M(n)=\mathcal{O}(n^2)$
My Attempt
Consider the idea of binary exponentiation in which,
the number $n$ has exactly $\lfloor\log_2 n\rfloor+1$ digits in base 2, ie., we need to perform $\lfloor\log_2 n\rfloor$ multiplications if we know the powers $a^1,a^2,\cdots,a^{2^{\lfloor\log_2 n\rfloor}}\implies \mathcal{O}(\log n)$ multiplications at most.
So we need to compute $\lfloor\log_2 n\rfloor$ powers of $a$, and also at most $\lfloor\log_2 n\rfloor$ multiplications, ie., in total $\le 2\lfloor\log_2 n\rfloor\implies\mathcal{O}(\log n)$.
Squaring the matrix $X$ doubles the number of bits of its entries, and we need to compute $\lfloor\log n\rfloor$ powers of $X$. $$ \text{The number of bits of the entries of }X^{\lfloor\log n\rfloor}\le 2^{\lfloor\log n\rfloor}\le 2^{\log n}=n\\\\ \implies\mathcal{O}(n) $$ $\implies $all intermediate results must be of length $\mathcal{O}(n)$
Now, with all these facts in mind how do we prove the claim ?