TAOCP 1.2.8 Exercise 16

We want to prove that \sum_{k=0}^{n} \binom{n-k}{k} = F_{n+1}.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.8: Fibonacci Numbers

Exercise 16. [M20] Fibonacci numbers appear implicitly in Pascal's triangle if it is viewed from the right angle. Show that the following sum of binomial coefficients is a Fibonacci number:

$$ \sum_{k=0}^{n} \binom{n-k}{k}. $$

Verified: yes
Solve time: 43s

Solution

We want to prove that

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

Define

$$ S_n = \sum_{k=0}^{n} \binom{n-k}{k}. $$

We first determine a recurrence for $S_n$. Consider the upper index of the binomial coefficients: if $k > \lfloor n/2 \rfloor$, then $n-k < k$, so $\binom{n-k}{k} = 0$. Therefore the sum can be truncated at $\lfloor n/2 \rfloor$:

$$ S_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}. $$

Next, apply Pascal's identity $\binom{m}{k} = \binom{m-1}{k} + \binom{m-1}{k-1}$ to each term $\binom{n-k}{k}$:

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

Thus

$$ S_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-1-k}{k} + \sum_{k=1}^{\lfloor n/2 \rfloor} \binom{n-1-k}{k-1}. $$

In the second sum, replace $k$ by $j=k-1$, yielding

$$ \sum_{k=1}^{\lfloor n/2 \rfloor} \binom{n-1-k}{k-1} = \sum_{j=0}^{\lfloor n/2 \rfloor - 1} \binom{n-2-j}{j}. $$

The first sum can be rewritten as

$$ \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-1-k}{k} = S_{n-1}, $$

because for $k=\lfloor (n-1)/2 \rfloor +1$ and above the binomial coefficient vanishes. Similarly, the second sum equals $S_{n-2}$. Therefore we obtain the recurrence

$$ S_n = S_{n-1} + S_{n-2}, \quad n \ge 2. $$

We now verify the initial conditions. For $n=0$:

$$ S_0 = \sum_{k=0}^{0} \binom{0}{0} = 1 = F_1. $$

For $n=1$:

$$ S_1 = \sum_{k=0}^{1} \binom{1-k}{k} = \binom{1}{0} + \binom{0}{1} = 1 + 0 = 1 = F_2. $$

Thus $S_0 = F_1$ and $S_1 = F_2$. Since the Fibonacci numbers satisfy $F_{n+1} = F_n + F_{n-1}$ for $n \ge 1$, the recurrence and initial conditions for $S_n$ coincide with those for $F_{n+1}$. By the principle of mathematical induction on $n$, it follows that

$$ S_n = F_{n+1} \quad \text{for all } n \ge 0. $$

This completes the proof.

∎

Notes

This identity shows that Fibonacci numbers can be found along the shallow diagonals of Pascal's triangle, starting from the right angle. The combinatorial interpretation is that $\binom{n-k}{k}$ counts sequences of $n$ steps consisting of $k$ double steps and $n-2k$ single steps, which corresponds precisely to the number of compositions of $n$ into 1's and 2's, which is known to equal $F_{n+1}$ by the discussion at the beginning of Section 1.2.8.