Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Non-Consecutive Fibonacci Numbers

  1. Sep 17, 2007 #1
    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.

    [itex] 33 = F_8 + F_6 + F_4 + F_2 = 21 + 8 + 3 + 1. [/itex]

    Any suggestions?
     
  2. jcsd
  3. Sep 18, 2007 #2
    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.
     
  4. Sep 19, 2007 #3

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    If [itex]F_n < k < F_{n+1}[/itex]

    then [itex]k = F_n + m[/itex]

    where [itex]m < F_{n-1}[/itex]
     
  5. Jul 23, 2011 #4
    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).
     
  6. Jul 23, 2011 #5
    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.
     
  7. Jul 23, 2011 #6
  8. Jul 23, 2011 #7
    ^ 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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?