Non-Consecutive Fibonacci Numbers

[rbzima]

I've been looking at this problem trying to figure it out for awhile, but haven't been able to come up with a distinct proof of this:

Do you think it's possible to express every positive integer as the sum of non-consecutive Fibonacci numbers? For example, 20 = 13 + 5 + 2, 33 = 21 + 8 + 3 + 1, and 34 = 34.

I worked through some of this and came to the conclusion that for some numbers, the Fibonacci number directly below the chosen positive integer will always be used in the sum.

33 = F_8 + F_6 + F_4 + F_2 = 21 + 8 + 3 + 1.

Any suggestions?

 

[Diffy]

Try induction.

Trivial case is 4, which is 1 + 3. Now assume that for all n less than or equal to some number k can be written as the sum of non consecutive Fibonacci numbers. See what this implies for k + 1.

 

[AlephZero]

If F_n < k < F_{n+1}

then k = F_n + m

where m < F_{n-1}

 

[cubzar]

Try induction.

Trivial case is 4, which is 1 + 3. Now assume that for all n less than or equal to some number k can be written as the sum of non consecutive Fibonacci numbers. See what this implies for k + 1.

I guess that the fibonacci numbers are required to be distinct. Let j(k) be the set of fibonacci numbers summing to k. j(k+1) contains the extra element 1, unless j(k) already contains 1, in which case j(k+1) can be formed by replacing the 1 in j(k) with a 2, unless j(k) already contains a 2, in which case the 1 and 2 can be swapped for a 3 and a 1 can be added, unless j(k) already contains a 3, in which case 1 and 3 can be swapped for a 5, unless j(k) already contains 5, in which case 3 and 5 can be swapped for 8 and 1 can be swapped for 2, unless...
Because each term is the sum of the two before it, and j(k) is finite, by swapping pairs of terms in this pattern j(k+1) can always be obtained from j(k).

 

[cubzar]

Correction: I forgot about the non-consecutive bit.
If j(k) does not contain both 1 and 2, either 1 can be added or 1 can be swapped for 2. If this results in a pair of consecutive fibonacci numbers, the pair can be swapped for the next fibanacci number after that, and any new consucutive pairs created can in turn be swapped etc. Hence j(k+1) is also the sum of distinct non-consecutive fibanacci numbers.

 

[awkward]

See

http://en.wikipedia.org/wiki/Zeckendorf's_theorem

 

[Dr. Seafood]

^ Wonderful, thanks! I wanted to post about this whole "integer representation as sum of non-consecutive Fibonacci numbers" thing on my blog, but it would be the first phenomenon/theorem I'd discuss that didn't have a name already.