Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm lost on where to start on this proof:

Using the fact that $A^m A^n = A^{m+n}$ , prove the identity

$F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$

I want to use induction starting with n = 1, but would I also have to make m = 1? I haven't done induction with 2 variables before.

or because of $A^m A^n = A^{m+n}$ should I setup the problem as a matrix (in that case what would the columns/rows be)?

I tried doing it mathematically however I think my algebra is wrong so I won't post it here. Am I correct to believe that $F_{m-1} = F_m*-1$ is not the same as $2^{n+1} = 2^n*2$?

Any help would be appreciated, thanks.

share|improve this question
    
I can guess what $F_n$ is from the title, but do we have to guess about $A$ as well? What is it and what relation with the Fibonacci number $F_i$ do you know? I cannot imagine they ask you this without saying anything about $A$. Maybe it is a matrix you have to find? –  Marc van Leeuwen Apr 22 '13 at 4:28
    
Unfortunately that is all they say, nothing about A, except for this extra statement which I don't think is related to A: The Fibonacci numbers are given by the formula F1 = F2 = 1 and for n ≥ 3. We also define F0 = 0. Fn = Fn−1 + Fn−2. –  Goose Apr 22 '13 at 4:29

3 Answers 3

up vote 1 down vote accepted

You can actually use induction here. We induct on $n$ proving that the relation holds for all $m$ at each step of the way. For $n=2$, $F_1 = F_2 =1$ and the identity $F_m+F_{m-1}=F_{m+1}$ is true for all $m$ by the definition of the Fibonacci sequence. We now have a strong induction hypothesis that the identity holds for values up until $n$, for all $m$. To show that it holds for $n+1$, for all $m$ we note that $$ F_m F_{n+1} + F_{m-1} F_n = F_m(F_{n-1} + F_n) + F_{m-1}(F_{n-2} + F_{n-1}) = $$ $$ (F_mF_n+F_{m-1}F_{n-1}) + (F_mF_{n-1} + F_{m-1}F_{n-2}) = F_{m+n-1} + F_{m+n-2} = F_{m+n}. $$ This completes the induction.

share|improve this answer

Fibonacci numbers have a matrix representation:

$$\left( \begin{smallmatrix} F_{n+1} & F_n \\ F_n & F_{n-1}\end{smallmatrix} \right) = \left( \begin{smallmatrix} 1 & 1 \\ 1 & 0 \end{smallmatrix}\right)^n$$

This is probably what you were meant to use for this problem.

share|improve this answer

Hint: If $$v_{n}=\left[ \begin{array} {c} F_{n+1} \\ F_{n}\end{array}\right]$$Then:$$F_{m}F_{n}+F_{m-1}F_{n-1}=\langle v_{m-1},v_{n-1}\rangle$$where $\langle \cdot, \cdot \rangle$ is the standard inner product on $\mathbb{R}^2$. This along with Vadim123's hint should get the job done.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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