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

• I
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.

Awesome, thanks. I figured there would be some ancient proof of this. 1970s is surprisingly young actually!

mfb
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.

• dkotschessaa