Fibonacci and Matrices

Question

Consider Matrix $$ A = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix} $$

Investigate the sequence of powers of $A$ (i.e. $A^n$ for $n = 1, 2, 3, 4,\ldots$.

Verify that $$A^n = \begin{pmatrix}F_{n+1} &F_n \\ F_n & F_{n−1}\end{pmatrix}$$ for $n \geq 20$, where $F_n$ is the $n^{th}$ Fibonacci number.

I don't get it, please help. Thank you!

Answer 1

Induction reasoning for $n\ge2$

$$\begin{bmatrix}1&1\\1&0\end{bmatrix}\times \begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}=\begin{bmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_{n}\end{bmatrix}$$

$$A^{2}=\begin{bmatrix}F_{2}&F_{1}\\F_{1}&F_{0}\end{bmatrix}$$

Answer 2

Hint: $$A^{n+1} = A\cdot A^n = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}\cdot\begin{pmatrix} F_{n+1} & F_{n}\\ F_{n} & F_{n-1} \end{pmatrix}$$$$$$ $$ = \begin{pmatrix} F_{n+1} + F_n & F_{n} + F_{n-1}\\ F_{n} + F_{n-1} & F_{n} \end{pmatrix} = \begin{pmatrix} F_{n+2} & F_{n+1}\\ F_{n+1} & F_{n} \end{pmatrix}$$