Write formula for matrix in terms of Fibonacci numbers

Question

How could I express this matrix in terms of Fibonacci numbers? It seems like I'd have to use induction once I have a candidate for a formula but I'm unsure of where to start with expressing the matrix in terms of Fibonacci numbers.

Thanks in advance!

Let $T:\mathbb{R^2}\rightarrow \mathbb{R^2}$ be a linear map such that

$$T\left( \begin{array}{c} x\\ y\\ \end{array} \right)=\left( \begin{array}{c} y\\ x+ y\\ \end{array} \right)$$

using the basis $\beta=\{e_1,e_2\}$

$$e_1=\left( \begin{array}{c} 1\\ 0\\ \end{array} \right),\quad e_2=\left( \begin{array}{c} 0\\ 1\\ \end{array} \right)$$

Write a formula for the matrix$$ [T^n]_\beta, \forall n\in\mathbb{N}$$ in terms of Fibonacci numbers.

Answer 1

Let us try to do it for $n = 1$. In that case, $T(e_1) = e_2$ and $T(e_2) = e_1 + e_2$, so this gives the matrix $\begin{pmatrix}0 \quad 1 \\ 1 \quad 1\end{pmatrix}$ for $T$.

If we have to find $T^n$ now, the first thing that we do is to find some elementary powers of $T$. Let's try to find $T^2$: $$ T^2 = \begin{pmatrix}1 \quad 1\\ 1 \quad 2\end{pmatrix}, T^3 = \begin{pmatrix}1 \quad 2\\ 2 \quad 3\end{pmatrix},T^4 = \begin{pmatrix}2 \quad 3\\ 3 \quad 5\end{pmatrix} $$ So the pattern, as can be seen clearly, is that $T^n = \begin{pmatrix} F_{n-1} \quad F_n \\ F_{n} \quad F_{n+1}\end{pmatrix}$.

The best we can do is to prove this by induction : Note that $T\begin{pmatrix}F_{n-1} & F_{n}\\ F_{n} & F_{n+1}\end{pmatrix} = \begin{pmatrix} F_{n} & F_{n+1} \\ F_{n-1} + F_n & F_{n} + F_{n+1}\end{pmatrix}$, from where you can conclude.

Answer 2

$T(e_1)=e_2$ and $T(e_2)=(1,1)$, so the matrix is formed by columns $T(e_1)$ and $T(e_2)$: $$T:=\begin{pmatrix} 0&1\\1&1 \end{pmatrix}$$

Note that $$T^n=\begin{pmatrix} 0&1\\1&1 \end{pmatrix}^n=\begin{pmatrix}F_{n-1}&F_n\\F_n & F_{n+1} \end{pmatrix}.$$

Where $F_0=0$ and $F_1=1$. You can check this by induction:

$$T^{n+1}=\begin{pmatrix} 0&1\\1&1 \end{pmatrix}\begin{pmatrix}F_{n-1}&F_n\\F_n & F_{n+1} \end{pmatrix}=\begin{pmatrix}F_n& F_{n+1}\\F_{n-1}+F_n&F_n+F_{n+1}\end{pmatrix}$$

But $F_{n-1}+F_n=F_{n+1}$ and $F_{n}+F_{n+1}=F_{n+2}$ by definition.