TAOCP 1.2.8 Exercise 6
Let A=\begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}.
Section 1.2.8: Fibonacci Numbers
Exercise 6. [HM10] Prove Eq. (5).
Verified: yes
Solve time: 36s
Let
$$ A=\begin{pmatrix} 1&1\ 1&0 \end{pmatrix}. $$
The proof is by induction on $n$. For $n=1$,
$$ A^1= \begin{pmatrix} 1&1\ 1&0 \end{pmatrix} = \begin{pmatrix} F_2&F_1\ F_1&F_0 \end{pmatrix}, $$
since $F_0=0$, $F_1=1$, and $F_2=1$. Thus Eq. (5) holds for $n=1$.
Assume that
$$ A^n= \begin{pmatrix} F_{n+1}&F_n\ F_n&F_{n-1} \end{pmatrix}. $$
Then
$$ A^{n+1} = A^nA = \begin{pmatrix} F_{n+1}&F_n\ F_n&F_{n-1} \end{pmatrix} \begin{pmatrix} 1&1\ 1&0 \end{pmatrix} = \begin{pmatrix} F_{n+1}+F_n&F_{n+1}\ F_n+F_{n-1}&F_n \end{pmatrix}. $$
By the defining recurrence for the Fibonacci numbers,
$$ F_{n+1}+F_n=F_{n+2}, \qquad F_n+F_{n-1}=F_{n+1}. $$
Hence
$$ A^{n+1} = \begin{pmatrix} F_{n+2}&F_{n+1}\ F_{n+1}&F_n \end{pmatrix}, $$
which is Eq. (5) with $n$ replaced by $n+1$. Therefore Eq. (5) holds for all $n\ge1$ by induction. This completes the proof.
∎