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

I A simple theorem we pondered in our ski lodge... (sum of Fibonacci numbers)

  1. Jan 23, 2017 #1
    We talked about Fibonacci numbers, and I wondered:

    Can any natural number be construed by a sum of unique Fibonacci numbers?

    My guess was yes, and a C program I wrote confirms that to be up to about 2,000, but that's of course is no proof. The best semi-proof I could come up with is that the Fibonacci sequence is more closely than the power-of-two sequence, which we know is enough to construct all numbers. Better explanation, but still a bit hand-wavy.
  2. jcsd
  3. Jan 23, 2017 #2


    Staff: Mentor

  4. Jan 23, 2017 #3
    Awesome, thanks. I figured there would be some ancient proof of this. 1970s is surprisingly young actually!
  5. Jan 23, 2017 #4


    Staff: Mentor

  6. Jan 23, 2017 #5


    User Avatar
    2016 Award

    Staff: Mentor

    Writing every natural number as sum of unique numbers of a set is possible for every set of increasing integers where ##a_1=1## and ##a_{n+1} \leq 2 a_n##. You can prove this by induction:
    • You can write 1 as such a sum as a1=1
    • Induction step: If you can write 1 to ai-1 as such a sum, not using ai (obviously), then you can write ai to ai+ai-1= 2ai-1 ##\geq## ai+1 as such a sum.

    As the Fibonacci numbers start at 1 and don't increase by more than a factor 2 per step, it works for them.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: A simple theorem we pondered in our ski lodge... (sum of Fibonacci numbers)
  1. Fibonacci sums (Replies: 5)