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

You are not logged in.

#1 2006-07-26 14:04:40

All_Is_Number
Member
Registered: 2006-07-10
Posts: 258

Prove It!

Prove that any positive integer can be expressed as a sum of terms in the Fibonacci sequence without using any term more than once.

For example:

161803 = 121393 + 28657 + 10946 + 610 + 144 + 34 + 13 + 5 + 1

These are the 26th, 23rd, 21st, 15th, 12th, 9th, 5th and 2nd terms in the Fibonacci sequence.

You can shear a sheep many times but skin him only once.

Offline

#2 2006-08-09 03:27:09

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Prove It!

Great question.  I've never tried this before, so here goes nothing:

If you don't understand this, or induction proofs in general, let me know.

This proof also outlines how you should come up with such summations.  We can do 1 to 5 by:

1: 1
2: 1 + 1
3: 2 + 1
4: 3 + 1
5: 3 + 2

Now we want to go from 5 to 8.  All we do is take our first 3, and add 5 to them.   We can do this since we know 5 can't be in any of them (since they are less than 5):

6: 5 + 1
7: 5 + 1 + 1
8: 5 + 2 + 1

Now we can do the same thing to get to 13:

9: 8 + 1
10: 8 + 1 + 1
11: 8 + 2 + 1
12: 8 + 3 + 1
13: 8 + 3 + 2

And by the proof above, this must work for all numbers.

"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..."

Offline

#3 2006-08-09 10:43:00

Zhylliolom
Real Member
Registered: 2005-09-05
Posts: 412

Re: Prove It!

Ricky, your LaTeX goes off the page, you might want to make it easier to read. Otherwise, everything looks good.

Offline

#4 2006-08-09 12:34:59

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Prove It!

I think that has to do with your screen resolution.  Try changing it and see if it helps.

"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..."

Offline

#5 2006-08-09 13:30:04

Zhylliolom
Real Member
Registered: 2005-09-05
Posts: 412

Re: Prove It!

I can't get it any better on this monitor . I wonder if there is a way to make LaTeX work for everyone's point of view. Equations will wrap, why doesn't \mbox{}?

Offline

#6 2006-08-23 10:15:00

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: Prove It!

The latex goes the page indeed.

IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#7 2006-08-23 10:20:00

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: Prove It!

And there's more generalized result: Zeckendorf's theorem

Last edited by krassi_holmz (2006-08-23 10:20:40)

IPBLE:  Increasing Performance By Lowering Expectations.

Offline