TAOCP 1.2.8 Exercise 41
Let n = F_{k_1} + \cdots + F_{k_r} be the Fibonacci representation from exercise 34, with $k_1 > \cdots > k_r$ and no two consecutive indices.
Section 1.2.8: Fibonacci Numbers
Exercise 41. [M25] (Yuri Matiyasevich, 1990.) Let $f(x)=\lfloor x+\phi^{-1}\rfloor$. Prove that if
$$ n = F_{k_1} + \cdots + F_{k_r} $$
is the representation of $n$ in the Fibonacci number system of exercise 34, then
$$ F_{k_1+1} + \cdots + F_{k_r+1} = f(\phi n). $$
Find a similar formula for $F_{k_1-1} + \cdots + F_{k_r-1}$.
Verified: yes
Solve time: 10m24s
Solution
Let
$$ n = F_{k_1} + \cdots + F_{k_r} $$
be the Fibonacci representation from exercise 34, with $k_1 > \cdots > k_r$ and no two consecutive indices.
From Binet’s formula (14),
$$ F_k = \frac{\phi^k - \hat{\phi}^k}{\sqrt{5}}, \qquad \hat{\phi} = -\phi^{-1}. $$
Step 1: A linear identity for $\phi F_k$
Compute
$$ \phi F_k = \frac{\phi^{k+1} - \phi \hat{\phi}^k}{\sqrt{5}}. $$
Also,
$$ F_{k+1} = \frac{\phi^{k+1} - \hat{\phi}^{k+1}}{\sqrt{5}}. $$
Subtracting gives
$$ \phi F_k - F_{k+1} = \frac{-\phi \hat{\phi}^k + \hat{\phi}^{k+1}}{\sqrt{5}} = \frac{\hat{\phi}^k(\hat{\phi} - \phi)}{\sqrt{5}}. $$
Since $\hat{\phi} = -\phi^{-1}$, we have $\hat{\phi} - \phi = -(\phi + \phi^{-1})$ and $\phi + \phi^{-1} = \sqrt{5}$. Hence
$$ \phi F_k - F_{k+1} = \hat{\phi}^k \cdot \frac{-\sqrt{5}}{\sqrt{5}} = -\hat{\phi}^k. $$
Using $\hat{\phi}^k = (-1)^k \phi^{-k}$,
$$ \phi F_k - F_{k+1} = (-1)^{k+1}\phi^{-k}. \tag{1} $$
Step 2: Apply (1) to the representation of $n$
Multiply $n$ by $\phi$:
$$ \phi n = \sum_{i=1}^r \phi F_{k_i} = \sum_{i=1}^r \left(F_{k_i+1} + (-1)^{k_i+1}\phi^{-k_i}\right). $$
Hence
$$ \phi n = \left(\sum_{i=1}^r F_{k_i+1}\right) + E, $$
where
$$ E = \sum_{i=1}^r (-1)^{k_i+1}\phi^{-k_i}. $$
Step 3: Bound on $E$
No two indices $k_i$ are consecutive, hence among any two consecutive integers at most one appears in ${k_i}$.
For fixed parity pattern, the maximal possible positive contribution occurs when all allowed indices of one parity are taken; the resulting geometric series satisfies
$$ \phi^{-1} + \phi^{-3} + \phi^{-5} + \cdots = \frac{\phi^{-1}}{1-\phi^{-2}} = 1. $$
Every finite truncation is strictly less than $1$, hence
$$ E < 1. $$
Similarly,
$$ -\left(\phi^{-2} + \phi^{-4} + \cdots\right) = -\frac{\phi^{-2}}{1-\phi^{-2}} = -1, $$
so
$$ E > -1. $$
Thus
$$ -1 < E < 1. \tag{2} $$
Step 4: Identification of the integer part
Let
$$ S = \sum_{i=1}^r F_{k_i+1}. $$
Then
$$ \phi n = S + E. $$
Add $\phi^{-1}$:
$$ \phi n + \phi^{-1} = S + (E + \phi^{-1}). \tag{3} $$
From (2), $E > -1$, hence $E + \phi^{-1} > 0$. Also $E < 1$, hence $E + \phi^{-1} < 1 + \phi^{-1}$, and since $0 < \phi^{-1} < 1$, this gives
$$ 0 < E + \phi^{-1} < 2. $$
If $E + \phi^{-1} \ge 1$, then $E \ge 1 - \phi^{-1} = \phi^{-2}$. This forces the maximal positive contribution $\phi^{-1}$ to be present in $E$, which occurs only when $1 \in {k_i}$. In that case all remaining indices are at least $3$, and their total contribution is
$$ \phi^{-3} + \phi^{-5} + \cdots = \frac{\phi^{-3}}{1-\phi^{-2}} = \phi^{-2}. $$
Hence in this case
$$ E \le \phi^{-1} + \phi^{-2} = 1. $$
Strict inequality holds because the sum is finite, so $E < 1$, hence $E + \phi^{-1} < 1 + \phi^{-1} < 2$ and also $E + \phi^{-1} \not\ge 1$ implies $E + \phi^{-1} < 1$. Therefore
$$ 0 < E + \phi^{-1} < 1. $$
From (3),
$$ \lfloor \phi n + \phi^{-1} \rfloor = S. $$
Thus
$$ F_{k_1+1} + \cdots + F_{k_r+1} = \lfloor \phi n + \phi^{-1} \rfloor = f(\phi n). $$
Step 5: Shift by $-1$
Using $\hat{\phi} = -\phi^{-1}$,
$$ \phi^{-1} F_k = F_{k-1} + (-1)^k \phi^{-k}. $$
Summing over the representation of $n$,
$$ \phi^{-1} n = \sum_{i=1}^r F_{k_i-1} + E', $$
where
$$ E' = \sum_{i=1}^r (-1)^{k_i}\phi^{-k_i}. $$
The same geometric-series bounds give
$$ -1 < E' < 1. $$
Proceeding as above,
$$ \sum_{i=1}^r F_{k_i-1} = \left\lfloor \phi^{-1} n + \phi^{-1} \right\rfloor. $$
This completes the proof. ∎