 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Fibo again (Posted on 2014-06-26) 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 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:

 Search: Search body:
Forums (0)