1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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
    2017 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted