Recursion Problems

gizmoguy19 · 2012-07-04 11:53:50

Hi
I have a questions that I am having trouble solving, any help?

1. Show the Fibonacci Sequence

thanks

Last edited by gizmoguy19 (2012-07-04 12:03:50)

bobbym · 2012-07-04 23:00:13

Hi gizmoguy19;

It is a lot of algebra but did you try the Binet formula?

I just came across a proof using induction.

Or you can use this relation:

If you expand the RHS and make the substitution F(n-3)=F(n-1)-F(n-2) you will get

Now take the RHS of 1)

Now making the substitution F(n-3)=F(n-1)-F(n-2) and F(n-2)=F(n)-F(n-1) to the RHS you get

The RHS of A is equal to the RHS of B so

Bob · 2012-07-05 06:56:50

hi gizmoguy19

Here's a unusual way using 'dominoes'.

Dominoes may either be single squares or doubles (twice as long as wide)

Object: To make a line of a specified length and answer the question "In how many ways can this be done?"

length one. You can do this in only one way, a single square.

length two. You can do this in two ways, a double or two singles.

length three. You can do this in three ways, a double and a single, three singles, a single and a double.

See diagram below for these and the next two.

You'll notice this sequence of results is Fibonacci.

Proof by strong induction.

Clearly it is true for the first few numbers.

Assume it is true for all length lines up to n-1.

How many ways can you make a line of length n ?

A line of n must end in either a single or a double.

If it ends in a single, it must consist of a line of length n-1 followed by a single. The number of ways will be F(n-1)

If it ends in a double, it must consist of a line of length n-2 followed by a double. The number of ways will be F(n-2)

Thus the total number of ways is the sum of these = F(n-1) + F(n-2) = F(n).

So how does that help with your problem?

How many ways can you make a line of 2n ?

Obviously, F(2n) by the proof above.

But, also, as this line is of even length, it cannot have a single at its centre point.

If it has a double at its centre, then it will consist of two lines of length n-1 with a double between.

Each of these lines can be made in F(n-1) ways, independently, so there will be F(n-1) ^2 ways like this.

If it is split by a centre line into two lines each of length n, these can independently be made in F(n) ways, so F(n) ^2 altogether.

So F(2n) = F(n)^2 + F(n-1)^2

See second diagram.

Bob

gizmoguy19 · 2012-07-07 05:54:43

Thanks a lot! I haven't heard of the Binet Formula though.

bobbym · 2012-07-07 06:02:38

Hi;

careless25 · 2012-07-08 14:32:37

Hi bobbym and bob bundy,

bobbym: can you share the link to proff by induction?
bob bundy: the OP asked for f(2n) = f(n+1)^2 - f(n-1)^2, your proof proves f(2n) = f(n)^2 + f(n-1)^2. I am guessing there is some algebraic manipulation to get to the identity given by OP?

Bob · 2012-07-08 19:39:26

hi careless25,

Oh big whoops. I must get my glasses fixed. (or maybe it's my brain that needs replacing!)

When I started this problem I filled pages with F equations and completely forgot what I was supposed to be proving.

So when I came across the domino stuff I was just so delighted I plowed ahead without a care.

I'd like to be able to say it's an easy hop from mine to the original but I haven't found it to be so.

But I'm under an obligation to do so now, so I'll keep at it.

Thanks for being eagle-eyed. You wouldn't consider lending them would you?

Bob

bobbym · 2012-07-08 20:25:43

Hi;

can you share the link to proff by induction

Sorry, but I did not write it down and now I can not find it.

Oh wait, the proof is incorrect. Sorry for mentioning it.

Bob · 2012-07-08 21:33:10

hi careless25,

I've hit a snag. There doesn't seem to be a rule about where you start the sequence {0,1,1,2......} or {1,1,2,3......} or {1,2,3,5.....}. And also with whether you call the first term F(0) or F(1).

The two formulas appear to use different Ns so that's going to make it harder to translate one into the other. see screen shot.

But it can be done .... just got to align the terminology.

Bob

anonimnystefy · 2012-07-08 22:28:44

I think that the mostly used sequence starts with F(0)=1 and F(1)=1.

Bob · 2012-07-08 23:22:55

hi

I've got it sorted anyway.

The screen shot below shows the N numbers required for F(2N) = F(N+1)^2 - F(N-1)^2

As you can see that then changes my formula to

F(2N-1) = F(N)^2 + F(N-1)^2

So, replacing N with N+1

F(2N+1) = F(N+1)^2 + F(N)^2

But for the Fibonacci numbers

F(2N+1) = F(2N) + F(2N-1) by definition

re-arranging

F(2N) = F(2N+1) - F(2N-1)

Substituting from my formula

F(2N) = F(N+1)^2 + F(N)^2 - F(N)^2 - F(N-1)^2 = F(N+1)^2 - F(N-1)^2 QED.

Bob

anonimnystefy · 2012-07-08 23:25:46

That looks okay now.

Bob · 2012-07-08 23:27:10

Thank you.

I'm an old man so you have to allow me more time to get places.

Bob

Math Is Fun Forum

#1 2012-07-04 11:53:50

Recursion Problems

#2 2012-07-04 23:00:13

Re: Recursion Problems

#3 2012-07-05 06:56:50

Re: Recursion Problems

#4 2012-07-07 05:54:43

Re: Recursion Problems

#5 2012-07-07 06:02:38

Re: Recursion Problems

#6 2012-07-08 14:32:37

Re: Recursion Problems

#7 2012-07-08 19:39:26

Re: Recursion Problems

#8 2012-07-08 20:25:43

Re: Recursion Problems

#9 2012-07-08 21:33:10

Re: Recursion Problems

#10 2012-07-08 22:28:44

Re: Recursion Problems

#11 2012-07-08 23:22:55

Re: Recursion Problems

#12 2012-07-08 23:25:46

Re: Recursion Problems

#13 2012-07-08 23:27:10

Re: Recursion Problems

Board footer