Strong induction on Fibonacci numbers

May 2010
15
0
Hi,

today I'm really stuck with strong inductions...

Let \(\displaystyle F_n\) be the \(\displaystyle n^{th}\) Fibonacci number. Prove that for all m ≥ 1 and all n, \(\displaystyle F_{m+n} = F_{m-1} F_n + F_m F_{n+1}\).

Can someone help me with it?
 
Oct 2009
769
87
Response

Recently got a book by Posamentier on Fibonacci numbers that I believe discusses strong induction on them. I'll look it up when I get home and let you know what I find out.

Question for you. Have you tried Googling for an answer?
 
May 2010
15
0
Question for you. Have you tried Googling for an answer?
Yes I tried but this particular proof is not explained. I can only find the strong induction proof of the fibonacci numbers defined as \(\displaystyle F_n = F_{n-1} + F_{n-2}\) with \(\displaystyle F_0 = 0\) and \(\displaystyle F_1 = 1\) with \(\displaystyle n \ge 2\).

Thank you very much!
 
Dec 2009
3,120
1,342
Hi,

today I'm really stuck with strong inductions...

Let \(\displaystyle F_n\) be the \(\displaystyle n^{th}\) Fibonacci number. Prove that for all m ≥ 1 and all n, \(\displaystyle F_{m+n} = F_{m-1} F_n + F_m F_{n+1}\).

Can someone help me with it?
Hi The Fangel,

P(k)

\(\displaystyle F_{m+k}=F_{m-1}F_k+F_mF_{k+1}\)

P(k+1)

\(\displaystyle F_{m+k+1}=F_{m-1}F_{k+1}+F_mF_{k+2}\)

Proof

\(\displaystyle F_{k+1}=F_k+F_{k-1}\ \Rightarrow\ \)\(\displaystyle F_k=F_{k+1}-F_{k-1}\)

and

\(\displaystyle F_{k+2}=F_{k+1}+F_k\ \Rightarrow\ F_{k+1}=F_{k+2}-F_k\)

then it follows

\(\displaystyle F_{m+k+1}=F_{m+k}+F_{m+k-1}\)

\(\displaystyle =F_{m-1}F_k+F_mF_{k+1}+F_{m+k-1}\)

\(\displaystyle =F_{m-1}F_{k+1}-F_{m-1}F_{k-1}+F_mF_{k+2}-F_mF_k+F_{m+k-1}\)

\(\displaystyle =F_{m-1}F_{k+1}+F_mF_{k+2}+\left(F_{m+k-1}-F_mF_k-F_{m-1}F_{k-1}\right)\)

as the part in brackets is zero based on P(k), then

\(\displaystyle F_{m+k+1}=F_{m-1}F_{k+1}+F_mF_{k+2}+0\)
 
  • Like
Reactions: TheFangel
Oct 2009
769
87
Answer

Looked it up in my book. Here's how it describes it (reworded of course):

First it describes it as a lemma, which needs to be proven (using the statements for n = k - 1 and for n = k to prove the statement for n = k + 1 so you'll be needing two base cases instead of just one meaning we have to check for n = 1 and n = 2).

When n = 1, we have to verify that . Now since , we must verify that which must be true since it's a defining relationship for the Fibonacci numbers.

When n = 2, then we need to verify that . Now since and , then we need to verify that which is true based on the following:



Next we assume the statement holds for n = k - 1 and n = k or

and which is the
induction hypothesis. From out of the next series of equations:


=
=
=
=
=

we have which is the statement for n = k + 1 which completes the proof.
 
  • Like
Reactions: TheFangel
May 2010
15
0
Thank you very much to both of you!

In the end I chose the one of wonderboy because it shows in a clearer way the strong induction mechanism, even though both are very valid.

Thanks again for your time!