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

  • I
  • Thread starter rumborak
  • Start date
  • #1
706
154
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.
 

Answers and Replies

  • #3
706
154
Awesome, thanks. I figured there would be some ancient proof of this. 1970s is surprisingly young actually!
 
  • #5
35,714
12,293
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.
 
  • Like
Likes dkotschessaa

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

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
8
Views
2K
Replies
2
Views
1K
  • Last Post
Replies
6
Views
13K
  • Last Post
Replies
5
Views
9K
Replies
9
Views
4K
  • Last Post
Replies
7
Views
8K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
3
Replies
66
Views
32K
Top