Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

gizmoguy19
Member
Registered: 2012-07-03
Posts: 6

Recursion Problems

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)

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Recursion Problems

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,053

Re: Recursion Problems

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


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

gizmoguy19
Member
Registered: 2012-07-03
Posts: 6

Re: Recursion Problems

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Recursion Problems

Hi;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Recursion Problems

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?

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,053

Re: Recursion Problems

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?  smile

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Recursion Problems

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,053

Re: Recursion Problems

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


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Recursion Problems

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


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,053

Re: Recursion Problems

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


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Recursion Problems

That looks okay now.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,053

Re: Recursion Problems

Thank you.

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

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

Board footer

Powered by FluxBB