1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The title and question i) are not the same. Also what have you tried? $\endgroup$ – mathreadler Jan 30 at 12:39
  • $\begingroup$ Possible duplicate of Converting recursive equations into matrices $\endgroup$ – Jyrki Lahtonen Jan 30 at 13:00
  • $\begingroup$ @JyrkiLahtonen, only a duplicate for (i). $\endgroup$ – lhf Jan 30 at 13:02
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jan 30 at 13:04
  • $\begingroup$ 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. $\endgroup$ – Diger Jan 30 at 15:02
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It seems that (ii) and (iii) are meant to be solved using (i). $\endgroup$ – lhf Jan 30 at 12:51
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.