# combinatorial proof of Zeckendorf’s theorem

###### Theorem 1.

Every nonnegative integer has a unique representation as a sum of nonconsecutive Fibonacci numbers^{}, where we do not use ${F}_{\mathrm{1}}$ and instead use

$${F}_{2}=1,{F}_{3}=2,{F}_{4}=3,{F}_{5}=5,{F}_{6}=8,\mathrm{\dots}$$ |

(Ignoring ${F}_{1}$ is necessary only to prevent the trivial counterexamples such as $6={F}_{5}+{F}_{2}={F}_{5}+{F}_{1}$).

###### Proof.

Given a sum ${\sum}_{i=2}^{n}{Z}_{i}{F}_{i}$ where ${Z}_{i}\in \{0,1\}$, we write that as a sequence^{} of binary digits; thus ${F}_{4}+{F}_{2}$ is written as $101$, while ${F}_{7}+{F}_{5}+{F}_{2}$ is $101001$. Arrange such sequences with no two consecutive $1$’s (i.e. those sequences corresponding to sums of nonconsecutive Fibonacci numbers) in increasing lexicographic order^{} starting from $0$, and assign each one a rank corresponding to its order in the list:

$$\begin{array}{cccccc}\hfill 5\hfill & \hfill 4\hfill & \hfill 3\hfill & \hfill 2\hfill & \hfill 1\hfill & \hfill rank\hfill \\ & & & & \hfill 0\hfill & \hfill 0\hfill \\ & & & & \hfill 1\hfill & \hfill 1\hfill \\ & & & \hfill 1\hfill & \hfill 0\hfill & \hfill 2\hfill \\ & & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 3\hfill \\ & & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 4\hfill \\ & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 5\hfill \\ & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 6\hfill \\ & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 7\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 8\hfill \end{array}$$ |

Note that the rank is *not* the value of the string as a binary string. In fact, it is the sum of the string when interpreted as a sum of Fibonacci numbers, but we do not assume this; as far as we know up to this point, all the rank is is the row number in this table.

We say that such a sequence has length $n$ if the leftmost $1$ is in position $n$; thus $100$ has length $3$.

Claim that the number of representations with length $\le n$ is ${F}_{n+2}$. We prove this by induction^{} on $n$; note that it is true for $n=0$ and for $n=1$. Now, given any representation of length $\le n$, it either has length $\le n-1$ or it has length exactly $n$. The number of representations of length $\le n-1$ is, by induction, ${F}_{n+1}$. To compute the number of representations of length exactly $n$, note that any such representation starts with $10$ since we cannot have two consecutive $1$’s. The digits after the $10$ are arbitrary as long as there are not two consecutive $1$’s, so that the number of such representations is precisely the number of representations of length $\le n-2$, or ${F}_{n}$. Thus the number of representations of length $\le n$ is ${F}_{n+1}+{F}_{n}={F}_{n+2}$. This proves the claim.

We will now prove the theorem by counting the number of rows preceding row $n$ in two different ways. First, the number of such rows is obviously $n$ (since we just numbered the row consecutively). We now count the number of predecessors by looking at the corresponding sequence. Given a sequence $s$, each of its predecessors $p$ first differs from it in some position $k$; since $s>p$ lexicographically, $s$ must be $1$ in that position while $p$ is zero. Since $p$ has a zero in position $k$, the remaining $k-1$ digits of $p$ are arbitrary subject to the consecutivity condition, so the number of possibilities for $p$ is the number of representations of length $\le k-1$, which is ${F}_{k+1}$. We can do this for each possible point of difference^{} with $s$ (which occur at the positions in which $s$ has a $1$, and thus must have nonconsecutive indices). This counts each predecessor of $s$ once and only once, and gives a representation of the number of predecessors as a sum of nonconsecutive Fibonacci numbers. But there are $n$ predecessors, so we have written $n$ as the required sum.

As an example of this process, consider the row numbered $7$, which is the sequence $1010$. If a predecessor differs from it at the first $1$, it is of the form $0***$ where the $*$’s are arbitrary (so long as there are no two consecutive $1$’s, so there are ${F}_{5}$ of them. If a predecessor differs from it at the second $1$, it is of the form $100*$ and again the $*$’s are arbitrary, so there are ${F}_{3}$ of them. Thus $7={F}_{5}+{F}_{3}$.

This argument shows existence; uniqueness follows as well from this construction since every possible sum is represented in the list, and each one represents a different integer.

∎

Title | combinatorial proof of Zeckendorf’s theorem |
---|---|

Canonical name | CombinatorialProofOfZeckendorfsTheorem |

Date of creation | 2013-03-22 19:05:53 |

Last modified on | 2013-03-22 19:05:53 |

Owner | rm50 (10146) |

Last modified by | rm50 (10146) |

Numerical id | 5 |

Author | rm50 (10146) |

Entry type | Proof |

Classification | msc 11B39 |

Classification | msc 11A63 |