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.

  • 1
    $\begingroup$ $$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}$$ is both simple to conjecture by inspecting $T^0,T^1,T^2,T^3$ and simple to prove by induction. $\endgroup$ – Jack D'Aurizio Nov 18 '17 at 3:21

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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.