Can every natural number be a sum of unique Fibonacci numbers?

[rumborak]

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.

 

[jedishrfu]

I think this thereom covers it:

https://en.wikipedia.org/wiki/Zeckendorf's_theorem

 

[rumborak]

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

 

[jedishrfu]

Actually try 1950's as the original author was overlooked:

While the theorem is named after the eponymous author who published his paper in 1972, the same result had been published 20 years earlier by Gerrit Lekkerkerker.[1] As such, the theorem is an example of Stigler's Law of Eponymy.

from https://en.wikipedia.org/wiki/Zeckendorf's_theorem

 

[mfb]

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 a₁=1
• Induction step: If you can write 1 to a_i-1 as such a sum, not using a_i (obviously), then you can write a_i to a_i+a_i-1= 2a_i-1 $\geq$ a_i+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.