In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, Zeckendorf's theorem, named after
Belgian
Belgian may refer to:
* Something of, or related to, Belgium
* Belgians, people from Belgium or of Belgian descent
* Languages of Belgium, languages spoken in Belgium, such as Dutch, French, and German
*Ancient Belgian language, an extinct languag ...
amateur mathematician
Edouard Zeckendorf
Edouard Zeckendorf (2 May 1901 – 16 May 1983) was a Belgian doctor, army officer and amateur mathematician. In mathematics, he is best known for his work on Fibonacci numbers and in particular for proving Zeckendorf's theorem, though he pu ...
, is a
theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of th ...
about the representation of
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s as sums of
Fibonacci number
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
s.
Zeckendorf's theorem states that every
positive integer
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...
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 is any positive integer, there exist positive integers , with , such that
:
where is the
th Fibonacci number. Such a sum is called the Zeckendorf representation of . The
Fibonacci coding
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 ...
of can be derived from its Zeckendorf representation.
For example, the Zeckendorf representation of 64 is
:.
There are other ways of representing 64 as the sum of Fibonacci numbers
:
:
:
:
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
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
, 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. As such, the theorem is an example of
Stigler's Law of Eponymy
Stigler's law of eponymy, proposed by University of Chicago statistics professor Stephen Stigler in his 1980 publication ''Stigler’s law of eponymy'', states that no scientific discovery is named after its original discoverer. Examples include ...
.
Proof
Zeckendorf's theorem has two parts:
#Existence: every positive integer has a Zeckendorf representation.
#Uniqueness: no positive integer has two different Zeckendorf representations.
The first part of Zeckendorf's theorem (existence) can be proven by
induction
Induction, Inducible or Inductive may refer to:
Biology and medicine
* Labor induction (birth/pregnancy)
* Induction chemotherapy, in medicine
* Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
. For it is clearly true (as these are Fibonacci numbers), for we have . If is a Fibonacci number then we're done. Else there exists such that . Now suppose each positive integer has a Zeckendorf representation (induction hypothesis) and consider . Since , has a Zeckendorf representation by the induction hypothesis. At the same time, (we apply the definition of Fibonacci number in the last equality), so the Zeckendorf representation of does not contain , and hence also does not contain . As a result, can be represented as the sum of and the Zeckendorf representation of , such that the Fibonacci numbers involved in the sum are distinct.
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 is strictly less than the next larger Fibonacci number .
The lemma can be proven by induction on .
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 and the largest member of
be . Because
and
contain no common elements, .
Without loss of generality
''Without loss of generality'' (often abbreviated to WOLOG, WLOG or w.l.o.g.; less commonly stated as ''without any loss of generality'' or ''with no loss of generality'') is a frequently used expression in mathematics. The term is used to indicate ...
, suppose . 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.
Fibonacci multiplication
One can define the following operation
on natural numbers , : 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
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name o ...
operation; however,
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
proved the surprising fact that this operation is also
associative
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
.
Representation with negafibonacci numbers
The Fibonacci sequence can be extended to negative index using the rearranged recurrence relation
:
which yields the sequence of "
negafibonacci" numbers satisfying
:
Any integer can be uniquely represented
as a sum of negafibonacci numbers in which no two consecutive negafibonacci numbers are used. For example:
*
*
*
*
* 0 is represented by the
empty sum
In mathematics, an empty sum, or nullary sum, is a summation where the number of terms is zero.
The natural way to extend non-empty sums is to let the empty sum be the additive identity.
Let a_1, a_2, a_3, ... be a sequence of numbers, and let
...
.
, 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
A system is a group of Interaction, interacting or interrelated elements that act according to a set of rules to form a unified whole. A system, surrounded and influenced by its environment (systems), environment, is described by its boundaries, ...
of coding
integers
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
, similar to the representation of Zeckendorf's theorem. In the string representing the integer , the
th digit is 1 if appears in the sum that represents ; 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 . The integer is represented by a string of odd length
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
.
See also
*
Complete sequence In mathematics, a sequence of natural numbers is called a complete sequence if every positive integer can be expressed as a sum of values in the sequence, using each value at most once.
For example, the sequence of powers of two (1, 2, 4, 8, ...) ...
*
Fibonacci coding
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 ...
*
Fibonacci nim
Fibonacci nim is a mathematical subtraction game, a variant of the game of nim. Players alternate removing coins from a pile, on each move taking at most twice as many coins as the previous move, and winning by taking the last coin. The Fibonacci ...
*
Ostrowski numeration
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 ...
References
*
External links
*
*
Zeckendorf's theoremat
cut-the-knot
Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet-born Israeli-American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow Institute of Electronics and Math ...
*
*
{{PlanetMath attribution, id=8810, title=proof that the Zeckendorf representation of a positive integer is unique
Fibonacci numbers
Theorems in number theory
Articles containing proofs