Zeckendorf's theorem

Last updated
The first 89 natural numbers in Zeckendorf form. Each rectangle has a Fibonacci number Fj as width (blue number in the center) and Fj-1 as height. The vertical bands have width 10. Zeckendorf representations 89px.png
The first 89 natural numbers in Zeckendorf form. Each rectangle has a Fibonacci number Fj as width (blue number in the center) and Fj−1 as height. The vertical bands have width 10.

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.

Contents

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.

History

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.

Proof

Zeckendorf's theorem has two parts:

  1. Existence: every positive integer n has a Zeckendorf representation.
  2. Uniqueness: no positive integer n has two different Zeckendorf representations.

The first part of Zeckendorf's theorem (existence) can be proven by induction. For n = 1, 2, 3 it is clearly true (as these are Fibonacci numbers), for n = 4 we have 4 = 3 + 1. If n is a Fibonacci number then there is nothing to prove. Otherwise there exists j such that Fj < n < Fj + 1. Now suppose each positive integer a < n has a Zeckendorf representation (induction hypothesis) and consider b = nFj. Since b < n, b has a Zeckendorf representation by the induction hypothesis. At the same time, b = nFj < Fj + 1Fj = Fj − 1 (we apply the definition of Fibonacci number in the last equality), so the Zeckendorf representation of b does not contain Fj − 1, and hence also does not contain Fj. As a result, n can be represented as the sum of Fj and the Zeckendorf representation of b, such that the Fibonacci numbers involved in the sum are distinct [2] .

The second part of Zeckendorf's theorem (uniqueness) requires the following lemma:

Lemma: The sum of any non-empty set of distinct, non-consecutive Fibonacci numbers whose largest member is Fj is strictly less than the next larger Fibonacci number Fj + 1.

The lemma can be proven by induction on j.

Now take two non-empty sets and of distinct non-consecutive Fibonacci numbers which have the same sum, . Consider sets and which are equal to and from which the common elements have been removed (i. e. and ). Since and had equal sum, and we have removed exactly the elements from from both sets, and must have the same sum as well, .

Now we will show by contradiction that at least one of and is empty. Assume the contrary, i. e. that and are both non-empty and let the largest member of be Fs and the largest member of be Ft. Because and contain no common elements, FsFt. Without loss of generality, suppose Fs < Ft. Then by the lemma, , and, by the fact that , , whereas clearly . This contradicts the fact that and have the same sum, and we can conclude that either or must be empty.

Now assume (again without loss of generality) that is empty. Then has sum 0, and so must . But since can only contain positive integers, it must be empty too. To conclude: which implies , proving that each Zeckendorf representation is unique [2] .

Fibonacci multiplication

One can define the following operation on natural numbers a, b: given the Zeckendorf representations and we define the Fibonacci product

For example, the Zeckendorf representation of 2 is , and the Zeckendorf representation of 4 is ( is disallowed from representations), so

(The product is not always in Zeckendorf form. For example, )

A simple rearrangement of sums shows that this is a commutative operation; however, Donald Knuth proved the surprising fact that this operation is also associative. [3]

Representation with negafibonacci numbers

The Fibonacci sequence can be extended to negative index n using the rearranged recurrence relation

which yields the sequence of "negafibonacci" numbers satisfying

Any integer can be uniquely represented [4] as a sum of negafibonacci numbers in which no two consecutive negafibonacci numbers are used. For example:

0 = F−1 + F−2, for example, so the uniqueness of the representation does depend on the condition that no two consecutive negafibonacci numbers are used.

This gives a system of coding integers, similar to the representation of Zeckendorf's theorem. In the string representing the integer x, the nth digit is 1 if F−n appears in the sum that represents x; that digit is 0 otherwise. For example, 24 may be represented by the string 100101001, which has the digit 1 in places 9, 6, 4, and 1, because 24 = F−1 + F−4 + F−6 + F−9. The integer x is represented by a string of odd length if and only if x > 0.

See also

Related Research Articles

<span class="mw-page-title-main">Binomial coefficient</span> Number of subsets of a given size

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers nk ≥ 0 and is written It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n; this coefficient can be computed by the multiplicative formula

In mathematics, the Bernoulli numbersBn are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in the Taylor series expansions of the tangent and hyperbolic tangent functions, in Faulhaber's formula for the sum of m-th powers of the first n positive integers, in the Euler–Maclaurin formula, and in expressions for certain values of the Riemann zeta function.

In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is countable if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements.

<span class="mw-page-title-main">Fibonacci sequence</span> Numbers obtained by adding the two previous ones

In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted Fn. The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes from 1 and 2. Starting from 0 and 1, the sequence begins

In mathematics, the branch of real analysis studies the behavior of real numbers, sequences and series of real numbers, and real functions. Some particular properties of real-valued sequences and functions that real analysis studies include convergence, limits, continuity, smoothness, differentiability and integrability.

<span class="mw-page-title-main">Sequence</span> Finite or infinite ordered list of elements

In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members. The number of elements is called the length of the sequence. Unlike a set, the same elements can appear multiple times at different positions in a sequence, and unlike a set, the order does matter. Formally, a sequence can be defined as a function from natural numbers to the elements at each position. The notion of a sequence can be generalized to an indexed family, defined as a function from an arbitrary index set.

In mathematics and computing, Fibonacci coding is a universal code which encodes positive integers into binary code words. It is one example of representations of integers based on Fibonacci numbers. Each code word ends with "11" and contains no other instances of "11" before the end.

In mathematics, an infinite series of numbers is said to converge absolutely if the sum of the absolute values of the summands is finite. More precisely, a real or complex series is said to converge absolutely if for some real number Similarly, an improper integral of a function, is said to converge absolutely if the integral of the absolute value of the integrand is finite—that is, if A convergent series that is not absolutely convergent is called conditionally convergent.

A mathematical symbol is a figure or a combination of figures that is used to represent a mathematical object, an action on mathematical objects, a relation between mathematical objects, or for structuring the other symbols that occur in a formula. As formulas are entirely constituted with symbols of various types, many symbols are needed for expressing all mathematics.

In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus differentialis (1730). They were rediscovered and given a combinatorial meaning by Masanobu Saka in 1782.

In mathematics, a function from a set X to a set Y assigns to each element of X exactly one element of Y. The set X is called the domain of the function and the set Y is called the codomain of the function.

In mathematics, summation is the addition of a sequence of numbers, called addends or summands; the result is their sum or total. Beside numbers, other types of values can be summed as well: functions, vectors, matrices, polynomials and, in general, elements of any type of mathematical objects on which an operation denoted "+" is defined.

In mathematics, a series is the sum of the terms of an infinite sequence of numbers. More precisely, an infinite sequence defines a series S that is denoted

<span class="mw-page-title-main">Polite number</span> Type of integer in number theory

In number theory, a polite number is a positive integer that can be written as the sum of two or more consecutive positive integers. A positive integer which is not polite is called impolite. The impolite numbers are exactly the powers of two, and the polite numbers are the natural numbers that are not powers of two.

In mathematics, the Fibonacci numbers form a sequence defined recursively by:

In mathematics, negafibonacci coding is a universal code which encodes nonzero integers into binary code words. It is similar to Fibonacci coding, except that it allows both positive and negative integers to be represented. All codes end with "11" and have no "11" before the end.

In arithmetic, a complex-base system is a positional numeral system whose radix is an imaginary or complex number.

In mathematics, the Wythoff array is an infinite matrix of integers derived from the Fibonacci sequence and named after Dutch mathematician Willem Abraham Wythoff. Every positive integer occurs exactly once in the array, and every integer sequence defined by the Fibonacci recurrence can be derived by shifting a row of the array.

In mathematics, Ostrowski numeration, named after Alexander Ostrowski, is either of two related numeration systems based on continued fractions: a non-standard positional numeral system for integers and a non-integer representation of real numbers.

In mathematics, the fibbinary numbers are the numbers whose binary representation does not contain two consecutive ones. That is, they are sums of distinct and non-consecutive powers of two.

References

  1. "Fibonacci bases and Other Ways of Representing Numbers". r-knott.surrey.ac.uk. Retrieved 2024-03-16.
  2. 1 2 Henderson, Nik (July 23, 2016). "What Is Zeckendorf's Theorem?" (PDF). Ohio State University. Retrieved August 23, 2024.
  3. Knuth, Donald E. (1988). "Fibonacci multiplication" (PDF). Applied Mathematics Letters. 1 (1): 57–60. doi: 10.1016/0893-9659(88)90176-0 . ISSN   0893-9659. Zbl   0633.10011.
  4. Knuth, Donald (2008-12-11). Negafibonacci Numbers and the Hyperbolic Plane. Annual meeting, Mathematical Association of America. The Fairmont Hotel, San Jose, CA.

This article incorporates material from proof that the Zeckendorf representation of a positive integer is unique on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.