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

1. Jan 23, 2017

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

2. Jan 23, 2017

### Staff: Mentor

3. Jan 23, 2017

### rumborak

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

4. Jan 23, 2017

### Staff: Mentor

5. Jan 23, 2017

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