1. ## Fibonacci Induction Proofs

I have 2 proofs relating to Fibonacci numbers and each other.

1. F_m+n = (F_m-1)(F_n) + (F_m)(F_n+1) for m≥1 and n≥0. (_ indicates subscript)

So far I have,
I am letting m be fixed and using induction on n.
Basis: n = 0, LHS: F_(m+0) = F_m
RHS: F_(m-1)*F_(0) + F_(m)*F_(0+1) = F_m

Induction Hypothesis: n = k, F_(m+k) = F_(m-1)*F_k + F_m*F_(k+1)
Induction Step: n=k+1, F_[m+(k+1)] = F_(m-1)*F_(k+1) + F_m*F_[(k+1)+1]
I am not sure where to go from here, can anyone help?

Then 2. Prove that for all m≥1 and n≥1, F_m divides F_(m*n). I am to do induction on n and use what I found in part 1 to help.

Thanks

2. Originally Posted by CoraGB
I have 2 proofs relating to Fibonacci numbers and each other.

1. F_m+n = (F_m-1)(F_n) + (F_m)(F_n+1) for m≥1 and n≥0. (_ indicates subscript)

So far I have,
I am letting m be fixed and using induction on n.
Basis: n = 0, LHS: F_(m+0) = F_m
RHS: F_(m-1)*F_(0) + F_(m)*F_(0+1) = F_m

Induction Hypothesis: n = k, F_(m+k) = F_(m-1)*F_k + F_m*F_(k+1)
Induction Step: n=k+1, F_[m+(k+1)] = F_(m-1)*F_(k+1) + F_m*F_[(k+1)+1]
I am not sure where to go from here, can anyone help?

Then 2. Prove that for all m≥1 and n≥1, F_m divides F_(m*n). I am to do induction on n and use what I found in part 1 to help.

Thanks

Hi there,

For the first part you need to use "strong" induction, that is you need more than one previous case to prove the next (you need 2.)

So for part one:

The base case:

$\displaystyle F_{m+1} = F_{m-1} + F_{m} = F_{m-1} F_1 + F_{m} F_2$

and

$\displaystyle F_{m+2} = F_{m} + F_{m+1} = F_{m} + F_{m-1} + F_{m} = 2 F_m + F_{m-1} = F_{m-1} F_2 + F_{m} F_3$

Then

$\displaystyle F_{m+n} = F_{m+n-1} + F_{m+n-2} = (F_{m-1} F_{n-1} + F_m F_n) + (F_{m-1}F_{n-2} + F_m F_{n-1})$

using the induction hypothesis on the case n-1 and n-2.

Then
$\displaystyle (F_{m-1} F_{n-1} + F_m F_n) + (F_{m-1}F_{n-2} + F_m F_{n-1})$

$\displaystyle = F_{m-1}(F_{n-1} + F_{n-2}) + F_m (F_n + F_{n-1}) = F_{m-1} F_n + F_m F_{n+1}$

For the second part

Clearly, $\displaystyle F_m | F_m$ for the base case.

Then

$\displaystyle F_{nm} = F_{m + (n-1)m} = F_{m-1} F_{(n-1)m} + F_m F_{(n-1)m +1}$

where $\displaystyle F_m | F_{(n-1)m}$ by the induction hypothesis proving the result.

3. Thanks so much!

4. Sorry for bumping this old topic, but I am trying to understand the first proof, and can't get my head around the 2nd last step:

$\displaystyle (F_{m-1} F_{n-1} + F_m F_n) + (F_{m-1}F_{n-2} + F_m F_{n-1})=F_{m-1}(F_{n-1} + F_{n-2}) + F_m (F_n + F_{n-1})$

More presicely what I don't understand is:
$\displaystyle \frac{F_m F_n}{F_{m-1}}=F_{n-2}$

and

$\displaystyle \frac{F_{m-1}F_{n-2}}{F_{m}}=F_n$

(At least I think that is what is happening)

Would anyone care to explain to me why this is allowed?

5. Originally Posted by opsahl92
Sorry for bumping this old topic, but I am trying to understand the first proof, and can't get my head around the 2nd last step:

$\displaystyle (F_{m-1} F_{n-1} + F_m F_n) + (F_{m-1}F_{n-2} + F_m F_{n-1})=F_{m-1}(F_{n-1} + F_{n-2}) + F_m (F_n + F_{n-1})$

More presicely what I don't understand is:
$\displaystyle \frac{F_m F_n}{F_{m-1}}=F_{n-2}$

and

$\displaystyle \frac{F_{m-1}F_{n-2}}{F_{m}}=F_n$

(At least I think that is what is happening)

Would anyone care to explain to me why this is allowed?
I'm sorry I'm not following the question. You will have to explain what you mean with more detail. I don't know where you got

$\displaystyle \frac{F_m F_n}{F_{m-1}}=F_{n-2}$

from (thats actually not used in the proof, in fact its probably false.) Try explaining your reasoning.

6. Originally Posted by gmatt
...

Then
$\displaystyle (F_{m-1} F_{n-1} + F_m F_n) + (F_{m-1}F_{n-2} + F_m F_{n-1})$

$\displaystyle = F_{m-1}(F_{n-1} + F_{n-2}) + F_m (F_n + F_{n-1})$

(Direct quote from your post! )

I just can't figure out how you got from the first to the 2nd line!

I got the fractions by pulling $\displaystyle F_{m-1}$ and $\displaystyle F_m$ out of the parenthesises in the first line of the quote.

7. Originally Posted by opsahl92
(Direct quote from your post! )

I just can't figure out how you got from the first to the 2nd line!

I got the fractions by pulling $\displaystyle F_{m-1}$ and $\displaystyle F_m$ out of the parenthesises in the first line of the quote.
Ahh! I see what you mean now. Yes sorry, I should of made that step more explicit, its just a rearrangement of terms:

$\displaystyle (F_{m-1} F_{n-1} + F_m F_n) + (F_{m-1}F_{n-2} + F_m F_{n-1})$
$\displaystyle = (F_{m-1} F_{n-1} + F_{m-1}F_{n-2}) + (F_m F_n + F_m F_{n-1})$
$\displaystyle = F_{m-1}(F_{n-1} + F_{n-2}) + F_m (F_n + F_{n-1})$

8. I get it now!! Thank you so much! I should've noticed, though! xD