Hi,

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

Let be the Fibonacci number. Prove that for all m ≥ 1 and all n, .

Can someone help me with it?

Printable View

- May 26th 2010, 03:06 PMTheFangelStrong induction on Fibonacci numbers
Hi,

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

Let be the Fibonacci number. Prove that for all m ≥ 1 and all n, .

Can someone help me with it? - May 26th 2010, 03:24 PMwonderboy1953Response
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 26th 2010, 03:51 PMTheFangel
- May 27th 2010, 01:55 AMArchie Meade
- May 27th 2010, 06:52 AMwonderboy1953Answer
Looked it up in my book. Here's how it describes it (reworded of course):

First it describes it as a lemma, http://www.mathhelpforum.com/math-he...ad948943-1.gif 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 http://www.mathhelpforum.com/math-he...14270780-1.gif. Now since http://www.mathhelpforum.com/math-he...fc6783d1-1.gif, we must verify that http://www.mathhelpforum.com/math-he...36d1ee07-1.gif which must be true since it's a defining relationship for the Fibonacci numbers.

When n = 2, then we need to verify that http://www.mathhelpforum.com/math-he...5f4a6d90-1.gif. Now since http://www.mathhelpforum.com/math-he...fc6783d1-1.gif and http://www.mathhelpforum.com/math-he...0a7d8b13-1.gif, then we need to verify that http://www.mathhelpforum.com/math-he...b819ac72-1.gif which is true based on the following:

http://www.mathhelpforum.com/math-he...cfce1549-1.gif

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

http://www.mathhelpforum.com/math-he...6cbab4e8-1.gif and http://www.mathhelpforum.com/math-he...652652a9-1.gif which is the

induction hypothesis. From out of the next series of equations:

http://www.mathhelpforum.com/math-he...f1eb9ce3-1.gif

= http://www.mathhelpforum.com/math-he...84ff0bdf-1.gif

= http://www.mathhelpforum.com/math-he...648ef0de-1.gif

= http://www.mathhelpforum.com/math-he...af562370-1.gif

= http://www.mathhelpforum.com/math-he...0a4c5864-1.gif

= http://www.mathhelpforum.com/math-he...cf232561-1.gif

we have http://www.mathhelpforum.com/math-he...b8f2dba8-1.gif which is the statement for n = k + 1 which completes the proof. - May 27th 2010, 11:00 AMTheFangel
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!