Zeckendorf's theorem
On the unique representation of integers as sums of non-consecutive Fibonacci numbers / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Zeckendorf's theorem?
Summarize this article for a 10 year old
In mathematics, Zeckendorf's theorem, named after Belgian amateur mathematician Edouard Zeckendorf, is a theorem about the representation of integers as sums of Fibonacci numbers.
Zeckendorf's theorem states that every positive integer can be represented uniquely as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. More precisely, if N is any positive integer, there exist positive integers ci ≥ 2, with ci + 1 > ci + 1, such that
where Fn is the nth Fibonacci number. Such a sum is called the Zeckendorf representation of N. The Fibonacci coding of N can be derived from its Zeckendorf representation.
For example, the Zeckendorf representation of 64 is
- 64 = 55 + 8 + 1.
There are other ways of representing 64 as the sum of Fibonacci numbers
- 64 = 55 + 5 + 3 + 1
- 64 = 34 + 21 + 8 + 1
- 64 = 34 + 21 + 5 + 3 + 1
- 64 = 34 + 13 + 8 + 5 + 3 + 1
but these are not Zeckendorf representations because 34 and 21 are consecutive Fibonacci numbers, as are 5 and 3.
For any given positive integer, its Zeckendorf representation can be found by using a greedy algorithm, choosing the largest possible Fibonacci number at each stage.