All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Fibo again (Posted on 2014-06-26) Difficulty: 2 of 5
Prove the following theorem:

Every positive integer can be represented uniquely as the sum of one or more distinct Fibonacci numbers without including any two consecutive Fibonacci numbers.

Examples: 8=8; 27=21+5+1

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution Comment 1 of 1

First we observe that 1, 2 and 3 can all be represented as themselves; 4 = 3 + 1; and 5 is once again a Fibonacci number which can be represented as itself.  

Consider a Fibonacci number f_n.  Assume that all positive integers <= f_n can be represented as the sum of one or more distinct Fibonacci numbers (without including any two consecutive). 

Then f_n + 1, f_n + 2, f_n + 3, ..., f_n + f_(n-1) - 1 can all be represented as the sum of distinct Fibonacci numbers.  f_n + f_(n-1) would be the first case that would appear to violate the condition that there are no two consecutive in the sum, but f_n + f_(n-1) is simply f_(n+1) and can therefore be represented as itself. 

Thus, all positive integers can be represented in this way.

  Posted by tomarken on 2014-06-26 09:53:47
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2021 by Animus Pactum Consulting. All rights reserved. Privacy Information