# Prove fibonacci with matrixes [duplicate]

I have a question which i could not figure out the answer to, it was the hardest of them all that i got and i couldnt figure it out, its a proof of fibonaccis serie using matrixes and i need som help

The question: The Fibonacci Numbers are recursively defined as $f_0 = 1$, $f_1 = 1$ and $f_{n+2} = f_{n+1} + f_n,$ for all $n ≥ 0$. Set $M = \binom{1\quad1}{1\quad0}$ and consider the powers $M, M^2, M^3,$ ... of this matrix. Prove that $M^n = \binom{f_n\quad f_{n-1}}{f_{n-1}\quad f_{n-2}}$ for all $n ≥ 2$. Powers of a matrix are the products $M^0 = I,\quad M^1 = M,\quad M^2 = M*M,\quad M^3 = M*M*M, . . . .$

can someone help and show me how to do this please? the proof

## 1 Answer

The statement is true for $n=2$, as the product $$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} f_2 & f_1 \\ f_1 & f_0 \end{pmatrix}$$ Now assume the statement is true for $n$; we will show it is true for $n+1$: $$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f_n & f_{n-1} \\ f_{n-1} & f_{n-2} \end{pmatrix} = \begin{pmatrix} f_n + f_{n-1} & f_{n-1} + f_{n-2} \\ f_{n} & f_{n-1} \end{pmatrix} = \begin{pmatrix} f_{n+1} & f_{n} \\ f_{n} & f_{n-1} \end{pmatrix}$$ Thus induction is established and the statement is true for all $n\geq 2$.