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

• I
• rumborak
In summary, we discussed the possibility of writing any natural number as a sum of unique Fibonacci numbers, and it was confirmed by a C program. While there is no formal proof, Zeckendorf's theorem states that every natural number can be written as a sum of unique numbers in a set with specific conditions. This theorem was originally published in the 1950s by Gerrit Lekkerkerker, but is now named after Zeckendorf. The proof can be shown through induction, and it applies to the Fibonacci numbers as they start at 1 and do not increase by more than a factor of 2.
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.

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

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

## 1. What is the "sum of Fibonacci numbers" theorem?

The "sum of Fibonacci numbers" theorem states that the sum of the first n Fibonacci numbers is equal to the (n+2)th Fibonacci number minus 1.

## 2. How do you prove the "sum of Fibonacci numbers" theorem?

The theorem can be proved using mathematical induction. The base case (n=1) can be easily verified, and then the inductive step can be used to prove that the theorem holds for all positive integers n.

## 3. Are there any real-world applications of the "sum of Fibonacci numbers" theorem?

Yes, the theorem has been applied in various fields such as computer science, finance, and biology. For example, it can be used to analyze the efficiency of algorithms, calculate the number of possible genetic codes, and understand the growth of certain plant populations.

## 4. What is the significance of the "sum of Fibonacci numbers" theorem?

The theorem is significant because it provides a mathematical relationship between the sum of consecutive Fibonacci numbers and the (n+2)th Fibonacci number. It also helps us understand the properties and patterns of the Fibonacci sequence, which appears in many natural phenomena.

## 5. Can the "sum of Fibonacci numbers" theorem be generalized?

Yes, the theorem can be generalized to other number sequences with similar properties to the Fibonacci sequence. It has also been extended to include negative and non-integer values for n.

Replies
1
Views
288
Replies
7
Views
2K
Replies
12
Views
2K
Replies
6
Views
3K
Replies
5
Views
303
Replies
16
Views
2K
Replies
7
Views
10K
Replies
27
Views
5K
Replies
14
Views
3K
Replies
37
Views
3K