Math Is Fun Forum

javadude

Member

Registered: 2008-07-13

Posts: 6

Fibonacci sequence

Ok, another part that Im confused on... I cant seem to wrap my head around this proving by induction.  We are asked to prove a particular fibonacci sequence.  I have the base step and the I got the inductive hypothesis I think... but I cannot figure out how to do the actual proof.

The fibonacci sequence is

My inductive hypothesis is

I've tried so many different ways but I cannot figure out how to prove this... Can someone help me by pushing me into the right direction?  Thanks!

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Fibonacci sequence

Not sure if you messed up the wording of your post or if you're doing your induction hypothesis improperly.

Your IH should be:

and you want to show:

Start by trying to write F(2k+2) in terms of F(2k).  Do the same for F(2(k+1)+1) in terms of F(2k+1) or maybe even F(2k).  Once you do this, it should come out almost immediately.  If it doesn't, post what you get and we'll help ya from there.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Fibonacci sequence

Check your formula. I don’t think it’s the correct formula for the Fibonacci sequence.

Last edited by JaneFairfax (2008-07-14 08:47:13)

javadude

Member

Registered: 2008-07-13

Posts: 6

Re: Fibonacci sequence

Start by trying to write F(2k+2) in terms of F(2k)

Like this?

?

Then I guess F(2(k+1)+1) would be

?

Am I going in the right direction or did I not get what you were asking?

Check your formula. I don’t think it’s the correct formula for the Fibonacci sequence.

The full problem directly from the worksheet is

.  I hope that helps... I figured the beginning part was not important in this part of it.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Fibonacci sequence

The full problem directly from the worksheet is

.  I hope that helps...

That looks better.

I figured the beginning part was not important in this part of it.

Dude, that is NOT the correct way to do maths! You DO NOT ever take shortcuts in doing a math problem! Otherwise you will never solve the problem!

DO NOT ever do such a thing again! Understand?

Anyway. First check that the result holds for

. I’ll leave you to do that yourself.

Now assume the statement is true for some integer

. So

Hence, adding

to both sides gives

That proves the result by induction. Do you understand the steps?

javadude

Member

Registered: 2008-07-13

Posts: 6

Re: Fibonacci sequence

The n=1 part I understand, no problems there...  I understand the assumption that n=k form... I don't understand why you added F(2(k+1)) to both sides... I get that it has something to do with proving the recurrence relationship (proving that n=k+1 is true).  Could you elaborate on that a little?

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Fibonacci sequence

I don't understand why you added F(2(k+1)) to both sides... I get that it has something to do with proving the recurrence relationship (proving that n=k+1 is true).

Well, you answered your own question there, didn’t you? You add the extra term to boths so that you can prove the recurrence relationship.

In general, what you do depends on the particular problem you are proving. In this problem, the LHS is a sum of terms, so you add F(2(k+1)). If it were a product, you would multiply by the extra term instead. In short, you follow whatever the operation is on that side of the equation in order to try and go from an expression for n=k to an expression for n=k+1.

javadude

Member

Registered: 2008-07-13

Posts: 6

Re: Fibonacci sequence

It appeared to be more involved than that when reading it in my textbook... I didnt know it was simply just adding a term to both sides of the equation that represents the next term.  Thats the overall gist of it right? 

So what you showed up above is actually proving that n=k+1; meaning the recurrence is proved.  Is that all there is to it? 

Man they make these things seem more complicated than they have to be.

Thanks alot for your help JaneFairfax... this will help alot in the coming weeks.