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

Homework Help: Representation with Fibonacci numbers

  1. Dec 27, 2007 #1
    [SOLVED] Representation with Fibonacci numbers

    1. The problem statement, all variables and given/known data
    Let k >> m mean that [tex]m \geq m+2[/tex]. Show that every positive integers n has a unique representation of the form [tex] n = F_{k_1} + F_{k_2} + \cdots F_{k_r}[/tex], where [tex]F_{k_i}[/tex] are Fibonacci nuimbers and [tex] k_1 >> k_2 >> \cdots k_r >> 0[/tex].

    EDIT: The first sentence should be: Let k >> m mean that [tex]k \geq m+2[/tex].

    2. Relevant equations

    3. The attempt at a solution
    I can show that the representation exists by induction.
    To show that the representation is unique, I am also trying to use induction. The uniqueness holds for n = 1,2,3. Assume the result holds for n leq k. If k+1 has two such representations, then these two representation must be pairwise different or else the strong IH is violated. I need help drawing the contradiction in the case where the two representations are pairwise distinct. Then we have that 2k+2 is equal to a sum of distinct Fibonacci numbers leq k+1, which seems like it might be impossible, but I am not sure how to prove that.
    Last edited: Dec 27, 2007
  2. jcsd
  3. Dec 27, 2007 #2


    User Avatar
    Science Advisor

    Surely that's not what you meant to write! [itex]m\ge m+ 2[/itex] is NEVER true so that just says "K>> m" is never true. Did you intend to have a k in that?
  4. Dec 27, 2007 #3
    Yes. That was foolish.
  5. Dec 28, 2007 #4
    Last edited: Dec 29, 2007
  6. Dec 29, 2007 #5
  7. Dec 29, 2007 #6


    User Avatar
    Science Advisor
    Homework Helper

    First show that you can write any number as a sum of some Fibonacci numbers [itex]F_{k_i}[/itex] where we have the easier condition [itex]F_{k_1} > \dots > F_{k_r} > 0[/itex]. Let's use a "binary-like" notation, where for example:


    means the sum of the first, fourth, fifth, seventh, and eight Fibonacci numbers (by the way, what convention are you using - what are your first and second Fibonacci numbers?). Now observe that any occurrence of 011 can be replaced with 100 because of the recurrence relation that the Fibonacci sequence satisfies. So the above is equal to:


    Now you yourself need to come up with a general procedure. By the way, look into "Zeckendorf Representation."
  8. Dec 30, 2007 #7
    That was EXTREMELY helpful.

    http://planetmath.org/encyclopedia/ProofThatTheZeckendorfRepresentationOfAPositiveIntegerIsUnique.html [Broken]
    Last edited by a moderator: May 3, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook