# Prove Fibonacci by induction using matrices

How do I prove by induction that the Fibonacci sequence correlates to the below expression of matrices?

$$\begin{pmatrix} f(n) \\ f(n+1) \end{pmatrix} = \begin{pmatrix} 0 && 1 \\ 1 && 1 \end{pmatrix}^n \begin{pmatrix}0 \\ 1\end{pmatrix}, \text{ for any } n\geq0$$

• It is very clearly true directly already, you just represent the recursive formula in a matrix, for the $n$-th number, you apply the formula $n$ times. – DWe1 Oct 25 '17 at 7:20

## 1 Answer

Take $n = 0$ and see that $$\begin{bmatrix} f(n) \\ f(n+1) \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$$ is clearly true: We just see the first two terms.

Suppose for a particular $n \in \mathbb{N}$, $$\begin{bmatrix} f(n) \\ f(n+1) \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^n\begin{bmatrix} 0 \\ 1 \end{bmatrix}$$ then, $$\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} f(n) \\ f(n+1) \end{bmatrix} = \begin{bmatrix} f(n+1) \\ f(n) + f(n+1) \end{bmatrix} = \begin{bmatrix} f(n+1) \\ f(n+2) \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n+1}\begin{bmatrix} 0 \\ 1 \end{bmatrix}$$