Show that $\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}^n$ for all $n ∈ N$.

Question

The Fibonacci numbers $F_n$ are recursively defined by

$F_0 = 0, F_1 = 1$

$F_{n+2} = F_{n+1} + F_n, n = 0,1,...$

i) Show that $\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}^n$ for all $n ∈ N$.

ii) Show that $F_0^2 + F_1^2 + ...+F_n^2 = F_n F_{n+1}$ for all $n ∈ N$.

iii) Show that $F_{n-1} F_{n+1} - F_n^2 = (-1)^n$ for all $n ∈ N$.

Answer 1

Just try to prove those by induction on $n\in\mathbb{N}$.

For example, the "induction step" for the second exercise is:

Suppose that $F_0^2+\cdots+F_n^2=F_nF_{n+1}$, then $$F_0^2+\cdots+F_n^2+F_{n+1}^2=F_nF_{n+1}+F_{n+1}^2=F_{n+1}(F_n+F_{n+1})=F_{n+1}F_{n+2}$$

Try the same approach in the other exercises. Don't forget the base cases.

Answer 2

Hint:

(i) Easy induction.

(ii) Note that $$ \begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}^2 = \begin{bmatrix}F_{n+1}^2+F_n^2&*\\*&*\end{bmatrix} $$

(iii) Take determinants.

Answer 3

i) Diagonalize the RHS matrix: $$\begin{pmatrix}1&1\\ 1&0\end{pmatrix}^n= \begin{pmatrix}\psi&\phi\\ 1&1\end{pmatrix} \begin{pmatrix}\psi^n &0\\ 0&\phi^n\end{pmatrix} \begin{pmatrix}-\frac{1}{\sqrt{5}}&\frac{\phi}{\sqrt{5}}\\ \frac1{\sqrt{5}}&-\frac{\psi}{\sqrt{5}}\end{pmatrix}=\\ \begin{pmatrix}\psi^{n+1}&\phi^{n+1}\\ \psi^n&\phi^n\end{pmatrix} \begin{pmatrix}-\frac{1}{\sqrt{5}}&\frac{\phi}{\sqrt{5}}\\ \frac1{\sqrt{5}}&-\frac{\psi}{\sqrt{5}}\end{pmatrix}=\\ \begin{pmatrix}\frac{\phi^{n+1}-\psi^{n+1}}{\sqrt{5}}&\frac{\phi^n-\psi^n}{\sqrt{5}}\\ \frac{\phi^n-\psi^n}{\sqrt{5}}&\frac{\phi^{n-1}-\psi^{n-1}}{\sqrt{5}}\end{pmatrix}=\\ \begin{pmatrix}F_{n+1}&F_n\\ F_n&F_{n-1}\end{pmatrix}.$$ Note: $\phi\cdot \psi=-1$.