Exercise 4.4.14* (Zeckendorf representation of positive integers)

Proof. Let $n$ be a positive integer. We prove that there is a unique sequence of integers $(j_0,j_1,\dots ,j_k)$ such that

where $2\le j_0$ and $j_{i+1}>j_i+1$ for all indices $i\in [[0,k[[$.

Such a decomposition is named the Zeckendorf representation of $n$ (see Wikipedia).

• Existence. We prove the existence of such a representation by induction. First, $1=F_2$, so the property is true for $n=1$. Now suppose that every positive integer less than $n$ has a Zeckendorf representation. We define $j$ as the largest integer such that $F_j\le n$ $(j\ge 2)$, i.e.

  $$j=\max <!--\; FUNCTION\; APPLICATION\; -->\{i\in \mathbb{N}\setminus \{0,1\}\mid F_i\le n\}.$$

  Such an integer exists because $F_2=1$, and the sequence ${(F_i)}_{i\ge 2}$ is strictly increasing.

  If $F_j=n$, then $n$ has a Zeckendorf decomposition with one term. Otherwise, $F_j<n<F_{j+1}$, thus

  $$\begin{array}{lll}\hfill 0<n-F_j<F_{j+1}-F_j=F_{j-1}.& & \hfill \text{(1)}\end{array}$$

  By the induction hypothesis, since $1\le n-F_j<n$, $n-F_j$ has a Zeckendorf representation

  $$n-F_j=F_{j_0}+F_{j_1}+\cdots +F_{j_k},2\le j_0,j_{i+1}>j_i+1(i=0,1,\dots k-1).$$

  We define $j_{k+1}=j$. Then $n=F_{j_0}+F_{j_1}+\cdots +F_{j_k}+F_{j_{k+1}}$.

  Moreover, by (1), $F_{j_k}\le n-F_j<F_{j-1}$. Since ${(F_i)}_{i\ge 2}$ is strictly increasing, $j_k<j-1=j_{k+1}-1$, so $n=F_{j_0}+F_{j_1}+\cdots +F_{j_k}+F_{j_{k+1}}$ is a Zeckendorf representation of $n$. The induction is done, which proves that every positive integer has a Zeckendorf representation.

• Unicity. We prove first that if $n=F_{j_0}+F_{j_1}+\cdots +F_{j_k}$ is a Zeckendorf representation of $n$, then $j_k=\max <!--\; FUNCTION\; APPLICATION\; -->\{i\in \mathbb{N}\setminus \{0,1\}\mid F_i\le n\}.$

  First $F_{j_k}\le {\sum <!--\; FUNCTION\; APPLICATION\; -->}_{l=0}^k{F}_{j_l}=n$.

  Next, we proved in Problem 13 that for all positive integers $m$,

  $$\begin{array}{lll}\hfill F_{2m}& =F_1+F_3+\cdots +F_{2m-1},& \hfill \text{(2)}\\ \hfill F_{2m+1}& =1+F_2+F_4+\cdots +F_{2m}.& \hfill \text{(3)}\end{array}$$

  • If $j_k$ is odd, say $j=2m-1$ (where $m\ge 2$), then using $j_i\le j_{i+1}-2$, we obtain

    $$j_{k-1}\le j_k-2,j_{k-2}\le j_k-4,\cdots ,j_{k-i}\le j_k-2i(i=0,1,\dots ,k).$$

    In particular, for $i=k$, $2\le j_0\le j_k-2k$. Since ${(F_i)}_{i\ge 2}$ is increasing

    $$\begin{array}{llll}\hfill n& =F_{j_0}+F_{j_1}+\cdots +F_{j_k}& \hfill & \\ \hfill & \le F_{j_k-2k}+F_{j_k-2(k-1)}+\cdots +F_{j_k}.& \hfill & \end{array}$$

    Since $j_k,j_k-2,\dots ,j_k-2k$ are distinct odd numbers in $]]2,2m[[$,

    $$\begin{array}{llllll}\hfill n& \le F_3+F_5+\cdots +F_{2m-1}& \hfill & & \hfill & \\ \hfill & =F_{2m}-1& \hfill (\text{by (2)}).& & \hfill & & \hfill \end{array}$$

    Therefore $n<F_{2m}=F_{j_k+1}$.

  • If $j_k$ is even, say $j_k=2m$, then similarly

    $$\begin{array}{llllll}\hfill n& =F_{j_0}+F_{j_1}+\cdots +F_{j_k}& \hfill & & \hfill & \\ \hfill & \le F_{j_k-2k}+F_{j_k-2(k-1)}+\cdots +F_{j_k}& \hfill & & \hfill & \\ \hfill & \le F_2+F_4+\cdots +F_{2m}& \hfill & & \hfill & \\ \hfill & =F_{2m+1}-1& \hfill (\text{by (3)})& & \hfill & & \hfill \end{array}$$

    Therefore $n<F_{2m+1}=F_{j_k+1}$.

  In both cases,

  $$F_{j_k}\le n<F_{j_k+1},$$

  thus

  $$j_k=\max <!--\; FUNCTION\; APPLICATION\; -->\{i\in \mathbb{N}\setminus \{0,1\}\mid F_i\le n\}.$$

  There is only one Zeckendorf representation of $1$, which is $1=F_2$. Suppose that the Zeckendorf representation of any $m<n$ is unique. We want to show that the representation of $n$ is unique.

  Assume that

  $$n=F_{j_0}+F_{j_1}+\cdots +F_{j_k}=F_{l_0}+F_{l_1}+\cdots +F_{l_p}$$

  are two Zeckendorf representations of $n$. By the first part of the proof,

  $$F_{j_k}=\max <!--\; FUNCTION\; APPLICATION\; -->\{i\in \mathbb{N}\setminus \{0,1\}\mid F_i\le n\}=F_{l_p}.$$

  Then

  $$n-F_{j_k}=F_{j_0}+F_{j_1}+\cdots +F_{j_{k-1}}=F_{l_0}+F_{l_1}+\cdots +F_{l_{p-1}}$$

  are two Zeckendorf representations of $m=n-F_{j_k}<n$. By the induction hypothesis $k=p$ and $(j_0,j_1,\dots ,j_{k-1})=(l_0,l_1,\dots ,l_{p-1})$, so $(j_0,j_1,\dots ,j_k)=(l_0,l_1,\dots ,l_p)$. There is only one Zeckendorf representation of $n$.

  The induction is done.

We can conclude:

There is a unique sequence of integers $(j_0,j_1,\dots ,j_k)$ such that

where $2\le j_0$ and $j_{i+1}>j_i+1$ for all indices $i\in [[0,k[[$. □