So$,$ in order to compute Fn$,$ it suffices to raise this $2\backslash$times $2$ matrix, call it X$,$ to the nth power.

i$)$ Show that O$($log n$)$ matrix multiplications suffice for computing Xn by repeated squaring. Note

that two $2\backslash$times $2$ matrices can be multiplied using $4$ additions and $8$ multiplications.

ii$)$ Let M $($n$)$ be the running time of an algorithm for multiplying n$-$bit numbers. Prove that the

running time of this second algorithm is O$($M $($n$)$ log n$)$