# Fibonacci Induction Proofs

• Oct 16th 2009, 06:49 AM
CoraGB
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
• Oct 16th 2009, 09:37 AM
gmatt
Quote:

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.
• Oct 16th 2009, 09:55 AM
CoraGB
Thanks so much!
• May 4th 2010, 08:00 AM
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?
• May 4th 2010, 09:10 AM
gmatt
Quote:

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.
• May 4th 2010, 09:20 AM
opsahl92
Quote:

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.
• May 4th 2010, 09:35 AM
gmatt
Quote:

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})$
• May 4th 2010, 09:39 AM
opsahl92
I get it now!! Thank you so much! :D I should've noticed, though! xD