# Fibonacci and Matrices [duplicate]

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.

## marked as duplicate by jameselmore, Martin Sleziak, J. M. is a poor mathematician, Omnomnomnom, dawOct 19 '15 at 15:02

• How about trying to prove this statement by induction on $n$? – Amitesh Datta Oct 19 '15 at 12:47
• What don't you get? You don't get what a matrix is? you don't get what $A^n$ means? you don't get what a Fibonacci number is? Meet us halfway – someone will help you. – Gerry Myerson Oct 19 '15 at 12:50
• – Martin Sleziak Oct 19 '15 at 13:43

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}$$
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}$$