4
$\begingroup$

The question is

Let $( F_0, F_1, F_2,... )$ be the Fibonacci sequence defined by $F_0=0,\, F_1=1, and F_{n+1}=F_n+F_{n-1}$, n greater than or equal to 1. Prove the following identities. $$\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^n =\begin{bmatrix} F_{n+1} &F_n \\ F_n &F_{n-1} \end{bmatrix}$$ This is what I tried.

Proof: Base case: If $n=1$ the formula says $$\begin{bmatrix} 1 & 1\\ 1& 0 \end{bmatrix}^{1}=\begin{bmatrix} F_{1+1} & F_1\\ F_1 &F_0 \end{bmatrix}=\begin{bmatrix} 1+0 & 1\\ 1 & 0 \end{bmatrix}=\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}$$ which is true.

Inductive Step: Suppose the formula holds for $n=k$ i.e. that $$\begin{bmatrix} 1 & 1\\ 1& 0 \end{bmatrix}^{k}=\begin{bmatrix} F_{k+1} &F_k\\ F_k &F_{k-1} \end{bmatrix}$$ is true.

We have to show that the formula holds for $n=k+1$ that is $$\begin{bmatrix} 1 &1 \\ 1&0 \end{bmatrix}^{k+1}= \begin{bmatrix} F_{k+2} & F_{k+1} \\ F_{k+1}&F_k \end{bmatrix}$$ is true. Adding $\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{k+1}$ both sides give $$\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^k + \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{k+1}= \begin{bmatrix} F_{k+1} &F_k\\ F_k &F_{k-1} \end{bmatrix} + \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{k+1}$$ This is where I'm stuck. From here I don't know how to proceed. Please let me know if I'm in the right direction.

$\endgroup$
  • $\begingroup$ I don't think proof-verification is a correct tag. $\endgroup$ – Parth Thakkar Sep 8 '13 at 6:09
4
$\begingroup$

HINT:

Instead of adding, multiply either sides of

$$\begin{bmatrix} 1 & 1\\ 1& 0 \end{bmatrix}^{k}=\begin{bmatrix} F_{k+1} &F_k\\ F_k &F_{k-1} \end{bmatrix}$$ by

$$\begin{bmatrix} 1 & 1\\ 1& 0 \end{bmatrix} $$

$\endgroup$
  • $\begingroup$ After I multiplied \begin{bmatrix} 1 & 1\\ 1& 0 \end{bmatrix} to the right side I obtained \begin{bmatrix} F_{k+1}+F_k &F_{k+1}\\ F_{k}+F_{k-1} &F_k \end{bmatrix} but that's not my desired result. $\endgroup$ – Candy Pelagio Sep 8 '13 at 6:27
  • 2
    $\begingroup$ @CandyPelagio, why shall we not use $F_{n+1}=F_n+F_{n-1}?$ $\endgroup$ – lab bhattacharjee Sep 8 '13 at 6:28

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.