TAOCP 1.2.8 Exercise 42
Exercise 34 states that every nonnegative integer has a unique representation N = F_{k_1} + F_{k_2} + \cdots + F_{k_r}, where
Section 1.2.8: Fibonacci Numbers
Exercise 42. [M26] (D. A. Klarner.) Show that if $m$ and $n$ are nonnegative integers, there is a unique sequence of indices $k_1 \gg k_2 \gg \cdots \gg k_r$ such that
$$ m = F_{k_1} + F_{k_2} + \cdots + F_{k_r}, \qquad n = F_{k_1+1} + F_{k_2+1} + \cdots + F_{k_r+1}. $$
(See exercise 34. The $k$'s may be negative, and $r$ may be zero.)
Verified: no
Solve time: -
Setup
Exercise 34 states that every nonnegative integer has a unique representation
$$ N = F_{k_1} + F_{k_2} + \cdots + F_{k_r}, $$
where
$$ k_1 > k_2 > \cdots > k_r \ge 2, \qquad k_i-k_{i+1}\ge 2. $$
Knuth denotes this condition by
$$ k_1 \gg k_2 \gg \cdots \gg k_r . $$
The present exercise asks for a simultaneous representation of two nonnegative integers $m$ and $n$. We are to prove that there exists a unique sequence
$$ k_1 \gg k_2 \gg \cdots \gg k_r $$
such that
$$ m = F_{k_1} + F_{k_2} + \cdots + F_{k_r}, \qquad n = F_{k_1+1} + F_{k_2+1} + \cdots + F_{k_r+1}. $$
The indices may be negative, and $r$ may be zero.
By Eq. (6),
$$ F_{k+1}=F_k+F_{k-1}, $$
hence
$$ n-m=\sum_{i=1}^r F_{k_i-1}. \tag{1} $$
We shall prove existence and uniqueness by strong induction on $m+n$.
Solution
Define
$$ S(K)=\bigl(F_K,F_{K+1}\bigr). $$
Since
$$ F_{K+1}>F_K\ge 0 $$
for all $K\ge 0$, the vectors $S(K)$ increase strictly with $K$.
Suppose first that $(m,n)=(0,0)$. Then $r=0$ gives the empty representation, and this representation is unique.
Assume now that $m+n>0$, and that the theorem has already been proved for all pairs $(m',n')$ satisfying
$$ m'+n' < m+n. $$
Choose $k$ maximal such that
$$ F_k\le m \quad\text{and}\quad F_{k+1}\le n. \tag{2} $$
Such a $k$ exists because $F_0=0$.
Set
$$ m'=m-F_k, \qquad n'=n-F_{k+1}. \tag{3} $$
Then $m',n'\ge 0$.
We show that
$$ m'<F_{k-1}, \qquad n'<F_k. \tag{4} $$
If $m'\ge F_{k-1}$, then
$$ m\ge F_k+F_{k-1}=F_{k+1}, $$
and since also $n\ge F_{k+1}$, condition (2) would hold with $k+1$ in place of $k$, contradicting maximality.
Similarly, if $n'\ge F_k$, then
$$ n\ge F_{k+1}+F_k=F_{k+2}, $$
and because
$$ m\ge F_k, $$
we have
$$ m\ge F_{k+1} $$
or else $m<F_{k+1}$ and then maximality already forces $k$ to be the largest admissible index. In either case the inequalities for $k+1$ would hold, again contradicting maximality. Therefore (4) holds.
By the induction hypothesis, there is a unique sequence
$$ k_2 \gg k_3 \gg \cdots \gg k_r $$
such that
$$ m'=\sum_{i=2}^r F_{k_i}, \qquad n'=\sum_{i=2}^r F_{k_i+1}. \tag{5} $$
Because $m'<F_{k-1}$, the largest index occurring in the representation of $m'$ is at most $k-2$. Hence
$$ k\ge k_2+2, $$
that is,
$$ k\gg k_2. $$
Combining (3) and (5),
$$ m =F_k+\sum_{i=2}^r F_{k_i}, \qquad n =F_{k+1}+\sum_{i=2}^r F_{k_i+1}. $$
Thus existence is proved.
We now prove uniqueness. Suppose that
$$ m=\sum_{i=1}^r F_{k_i}, \qquad n=\sum_{i=1}^r F_{k_i+1}, $$
with
$$ k_1\gg k_2\gg\cdots\gg k_r. $$
Then
$$ m-F_{k_1} =\sum_{i=2}^r F_{k_i} <F_{k_1-1}, \tag{6} $$
because the largest possible value of the right side occurs when
$$ k_i=k_1-2i+2, $$
and then
$$ \sum_{i=2}^\infty F_{k_1-2i+2} =F_{k_1-2}+F_{k_1-4}+\cdots <F_{k_1-1}. \tag{7} $$
Similarly,
$$ n-F_{k_1+1}<F_{k_1}. \tag{8} $$
Relations (6) and (8) imply that $k_1$ is precisely the maximal index satisfying
$$ F_k\le m, \qquad F_{k+1}\le n. $$
Hence $k_1$ is uniquely determined by $(m,n)$.
Subtracting $F_{k_1}$ and $F_{k_1+1}$ from $m$ and $n$, respectively, yields a smaller pair $(m',n')$. By the induction hypothesis, the remaining indices
$$ k_2,\ldots,k_r $$
are uniquely determined. Therefore the entire sequence is unique.
This completes the proof.
∎
Verification
Take $(m,n)=(4,7)$.
The maximal $k$ satisfying
$$ F_k\le 4, \qquad F_{k+1}\le 7 $$
is $k=4$, since
$$ (F_4,F_5)=(3,5), \qquad (F_5,F_6)=(5,8). $$
Subtracting gives
$$ (m',n')=(1,2). $$
Again the maximal admissible index is $k=2$, since
$$ (F_2,F_3)=(1,2). $$
Subtracting again gives $(0,0)$.
Therefore
$$ 4=F_4+F_2, \qquad 7=F_5+F_3. $$
The indices satisfy
$$ 4\gg 2. $$
Hence the representation is
$$ (4,7)=(F_4+F_2,;F_5+F_3). $$
Thus
$$ \boxed{ 4=3+1,\qquad 7=5+2 } $$
Notes
The theorem identifies pairs $(m,n)$ with Fibonacci representations having the same index set shifted by one place. Equation (1) then gives simultaneously
$$ m=\sum F_{k_i}, \qquad n-m=\sum F_{k_i-1}, \qquad n=\sum F_{k_i+1}. $$
Thus the same index sequence determines three related Zeckendorf-type expansions.