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 |
Solution
