TAOCP 1.2.6 Exercise 18
Equation (22) states that for integers $n \ge 0$ and $m \ge 0$: \sum_{k=0}^{n} \binom{k}{m} = \binom{n+1}{m+1}.
Section 1.2.6: Binomial Coefficients
Exercise 18. [M15] Prove Eq. (22) using Eqs. (21) and (6).
Verified: yes
Solve time: 34s
Solution
Equation (22) states that for integers $n \ge 0$ and $m \ge 0$:
$$ \sum_{k=0}^{n} \binom{k}{m} = \binom{n+1}{m+1}. $$
We are to prove this using Eq. (21) and the symmetry relation (6). Equation (21) is the more general summation formula
$$ \sum_{k=0}^{n} \binom{r+k}{k} = \binom{r+n+1}{n}, \qquad \text{integer } n \ge 0. $$
First, note that by Eq. (6) we have
$$ \binom{r}{k} = \binom{r}{r-k}. $$
We apply this identity to rewrite the sum $\sum_{k=0}^{n} \binom{k}{m}$ in a form suitable for Eq. (21). Set $r = m$ in Eq. (21) and observe that
$$ \sum_{k=0}^{n-m} \binom{m+k}{k} = \binom{m+(n-m)+1}{n-m} = \binom{n+1}{n-m}. $$
Then, by symmetry (6),
$$ \binom{n+1}{n-m} = \binom{n+1}{m+1}. $$
It remains to justify the index shift. In the sum $\sum_{k=0}^{n} \binom{k}{m}$, terms with $k < m$ vanish because $\binom{k}{m} = 0$ when $k < m$. Therefore,
$$ \sum_{k=0}^{n} \binom{k}{m} = \sum_{k=m}^{n} \binom{k}{m}. $$
Set $k = m + j$ with $0 \le j \le n-m$. Then $\binom{k}{m} = \binom{m+j}{m}$, and the sum becomes
$$ \sum_{j=0}^{n-m} \binom{m+j}{m}. $$
By Eq. (21) with $r = m$ and $n \mapsto n-m$, we have
$$ \sum_{j=0}^{n-m} \binom{m+j}{j} = \binom{m+(n-m)+1}{n-m} = \binom{n+1}{n-m}. $$
Finally, applying symmetry (6) gives
$$ \binom{n+1}{n-m} = \binom{n+1}{m+1}. $$
Thus we have established that
$$ \sum_{k=0}^{n} \binom{k}{m} = \binom{n+1}{m+1}. $$
This completes the proof.
∎