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.
A: $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.
