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

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

• The title and question i) are not the same. Also what have you tried? – mathreadler Jan 30 '19 at 12:39
• Possible duplicate of Converting recursive equations into matrices – Jyrki Lahtonen Jan 30 '19 at 13:00
• @JyrkiLahtonen, only a duplicate for (i). – lhf Jan 30 '19 at 13:02
• Well, A) it answers part (iii) as well, B) there should be only one question.per post. It is highly likely that the other parts have been covered earlier as well. – Jyrki Lahtonen Jan 30 '19 at 13:04
• I guess the easiest way it to multiply the equation by $$\begin{bmatrix}1&1\\1&0\end{bmatrix}$$ and then the RHS is $$\begin{bmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_{n}\end{bmatrix}$$ by assumption and you just need to evaluate $$\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}\begin{bmatrix}1&1\\1&0\end{bmatrix}=\begin{bmatrix}F_{n+1}+F_n&F_{n+1}\\F_n+F_{n-1}&F_{n}\end{bmatrix}$$ which by the Fibonacci recursion however matches $$\begin{bmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_{n}\end{bmatrix} \, .$$ For iii) just take the determinant. – Diger Jan 30 '19 at 15:02

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.

• It seems that (ii) and (iii) are meant to be solved using (i). – lhf Jan 30 '19 at 12:51

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.

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