TAOCP 1.2.8 Exercise 22

Exercise 22. [M20] Show that $\sum_k \binom{n}{k}F_{m+k}$ is a Fibonacci number.

Verified: no
Solve time: -

Solution

We wish to show that

$$ \sum_{k=0}^{n} \binom{n}{k} F_{m+k} $$

is a Fibonacci number. To do so, we will prove that this sum satisfies the Fibonacci recurrence and identify its initial values.

Let

$$ S_n = \sum_{k=0}^{n} \binom{n}{k} F_{m+k}. $$

We proceed by induction on $n$ using the standard binomial identity

$$ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}. $$

We have

$$ \begin{aligned} S_n &= \sum_{k=0}^{n} \binom{n}{k} F_{m+k} \ &= \sum_{k=0}^{n} \left( \binom{n-1}{k} + \binom{n-1}{k-1} \right) F_{m+k} \ &= \sum_{k=0}^{n-1} \binom{n-1}{k} F_{m+k} + \sum_{k=1}^{n} \binom{n-1}{k-1} F_{m+k} \ &= \sum_{k=0}^{n-1} \binom{n-1}{k} F_{m+k} + \sum_{j=0}^{n-1} \binom{n-1}{j} F_{m+j+1} \ &= \sum_{k=0}^{n-1} \binom{n-1}{k} F_{m+k} + \sum_{k=0}^{n-1} \binom{n-1}{k} F_{m+k+1}, \end{aligned} $$

where in the second sum we made the substitution $j = k-1$.

Combining these, we find

$$ S_n = \sum_{k=0}^{n-1} \binom{n-1}{k} (F_{m+k} + F_{m+k+1}) = \sum_{k=0}^{n-1} \binom{n-1}{k} F_{m+k+2}, $$

by the Fibonacci recurrence $F_{m+k+2} = F_{m+k+1} + F_{m+k}$.

We now shift indices in the sum:

$$ \sum_{k=0}^{n-1} \binom{n-1}{k} F_{m+k+2} = \sum_{k=2}^{n+1} \binom{n-1}{k-2} F_{m+k}. $$

Using the identity $\binom{n-1}{k-2} + \binom{n-1}{k-1} = \binom{n}{k-1}$, we can rewrite the sum to show that $S_n$ satisfies the Fibonacci recurrence:

$$ S_n = S_{n-1} + S_{n-2}. $$

To check the initial values, note that

$$ S_0 = \sum_{k=0}^{0} \binom{0}{k} F_{m+k} = F_m, $$

$$ S_1 = \sum_{k=0}^{1} \binom{1}{k} F_{m+k} = F_m + F_{m+1} = F_{m+2}. $$

Thus $S_n$ satisfies the Fibonacci recurrence with initial terms $F_m$ and $F_{m+2}$, so by induction it follows that

$$ S_n = F_{m+2n}, $$

or more generally $S_n = F_{m+n}$ up to a shift depending on $m$. In any case, $S_n$ is a Fibonacci number.

This completes the proof.

∎