Q:

Write formula for matrix in terms of Fibonacci numbers

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.

A:

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.

