TAOCP 1.2.8 Exercise 34
We prove existence and uniqueness separately.
Section 1.2.8: Fibonacci Numbers
Exercise 34. [M24] (The Fibonacci number system.) Let the notation $k \gg m$ mean that $k \ge m+2$. Show that every positive integer $n$ has a unique representation
$$ n = F_{k_1} + F_{k_2} + \cdots + F_{k_r}, $$
where $k_1 \gg k_2 \gg \cdots \gg k_r \gg 0$.
Verified: no
Solve time: -
Solution
We prove existence and uniqueness separately.
Define the relation $k \gg m$ by
$$ k \gg m \iff k \ge m+2. $$
Thus the condition
$$ k_1 \gg k_2 \gg \cdots \gg k_r \gg 0 $$
means
$$ k_1 \ge k_2+2,\quad k_2 \ge k_3+2,\quad \ldots,\quad k_r \ge 2. $$
We first establish the identity
$$ F_k = 1+\sum_{j=2}^{k-1} F_j \qquad (k\ge2). \tag{1} $$
For $k=2$, the right-hand side is $1$, equal to $F_2$.
Assume (1) holds for $k$. Then
$$ 1+\sum_{j=2}^{k}F_j = \left(1+\sum_{j=2}^{k-1}F_j\right)+F_k = F_k+F_k = 2F_k. $$
Since
$$ F_{k+1}=F_k+F_{k-1}, $$
and by (1),
$$ F_k = 1+\sum_{j=2}^{k-1}F_j = F_{k-1}+\sum_{j=2}^{k-2}F_j, $$
we obtain
$$ F_k-F_{k-1} = \sum_{j=2}^{k-2}F_j \ge0. $$
Hence
$$ 2F_k = F_{k+1}+\bigl(F_k-F_{k-1}\bigr). $$
Using (1) again,
$$ F_k-F_{k-1} = \sum_{j=2}^{k-2}F_j, $$
therefore
$$ 2F_k = F_{k+1}+\sum_{j=2}^{k-2}F_j = 1+\sum_{j=2}^{k}F_j. $$
Thus
$$ 1+\sum_{j=2}^{k}F_j=F_{k+1}, $$
and (1) follows by induction.
Now let
$$ S_k=\sum_{j=0}^{\lfloor (k-2)/2\rfloor}F_{k-2j}. $$
We claim that
$$ S_k=F_{k+1}-1. \tag{2} $$
The terms occurring in $S_k$ are precisely
$$ F_k,F_{k-2},F_{k-4},\ldots . $$
Using the recurrence repeatedly,
$$ F_{k+1} = F_k+F_{k-1} = F_k+F_{k-2}+F_{k-3} = F_k+F_{k-2}+F_{k-4}+F_{k-5} = \cdots . $$
Continuing until the indices reach $2$ or $1$, we obtain
$$ F_{k+1} = S_k+1, $$
since $F_2=1$ and $F_1=1$. Hence (2) holds.
We now prove existence by strong induction on $n$.
For $n=1$,
$$ 1=F_2, $$
and the representation satisfies the required conditions.
Assume that every positive integer less than $n$ has such a representation. Let $k$ be the largest integer such that
$$ F_k\le n. $$
Then
$$ F_k\le n<F_{k+1}. \tag{3} $$
Set
$$ m=n-F_k. $$
By (2),
$$ \sum_{j=0}^{\lfloor (k-3)/2\rfloor}F_{k-1-2j} = F_k-1. $$
Therefore every sum of Fibonacci numbers whose largest index is at most $k-1$ and whose indices differ by at least $2$ is at most $F_k-1$. Since $n<F_{k+1}=F_k+F_{k-1}$ by (3),
$$ m=n-F_k<F_{k-1}. \tag{4} $$
If $m=0$, then
$$ n=F_k $$
is already a valid representation.
Suppose $m>0$. By the induction hypothesis,
$$ m=F_{k_2}+\cdots+F_{k_r}, $$
where
$$ k_2 \gg k_3 \gg \cdots \gg k_r \gg 0. $$
Since $m<F_{k-1}$ by (4), the largest index in this representation satisfies
$$ k_2\le k-2. $$
Hence
$$ k\gg k_2. $$
Therefore
$$ n=F_k+F_{k_2}+\cdots+F_{k_r} $$
is a representation of the required form. Existence follows.
We now prove uniqueness.
Suppose
$$ n=F_{k_1}+F_{k_2}+\cdots+F_{k_r} = F_{\ell_1}+F_{\ell_2}+\cdots+F_{\ell_s}, $$
where
$$ k_1 \gg k_2 \gg \cdots \gg k_r \gg 0, $$
and
$$ \ell_1 \gg \ell_2 \gg \cdots \gg \ell_s \gg 0. $$
Assume, without loss of generality, that
$$ k_1<\ell_1. $$
Then
$$ k_1\le \ell_1-2. $$
Using (2),
$$ F_{k_1}+F_{k_2}+\cdots+F_{k_r} \le F_{k_1+1}-1. $$
Since $k_1+1\le \ell_1-1$,
$$ F_{k_1+1}-1<F_{\ell_1}. $$
Therefore
$$ n<F_{\ell_1}, $$
contradicting
$$ n\ge F_{\ell_1}. $$
Hence
$$ k_1=\ell_1. $$
Subtracting $F_{k_1}$ from both representations gives
$$ F_{k_2}+\cdots+F_{k_r} = F_{\ell_2}+\cdots+F_{\ell_s}. $$
Repeating the argument inductively yields
$$ k_i=\ell_i $$
for all $i$, and consequently $r=s$.
Thus the representation is unique.
This completes the proof.
∎