# The identity with sum of binomial coefficients

Is this formula true?

$$\sum_{m=k}^n {m \choose k}={n+1 \choose k+1}$$

If yes how to prove it?

• What are your thoughts? What have you tried? – Sloan Mar 28 '15 at 14:46
• Try induction on $n$ – Elaqqad Mar 28 '15 at 14:48
• You can also do a combinatorial proof by counting the number of subsets of $\{0,\dots,n\}$ which have $k+1$ elements. In the first sum, $m$ is the largest element of the subset. – Michael Burr Mar 28 '15 at 14:49
• I strongly believe this is a duplicate, now looking for it. – Jack D'Aurizio Mar 28 '15 at 15:07
• Almost duplicate: math.stackexchange.com/questions/619940/… – Jack D'Aurizio Mar 28 '15 at 15:09

Combinatorial proof

Let $A=\{0,\cdots,n\}$. This set has $n+1$ elements, so $\begin{pmatrix}n+1\\k+1\end{pmatrix}$ counts the number of subsets of size $k+1$.

On the other hand, for any subset of size $k+1$, let $m$ be its largest element. It is certainly true that $k\leq m\leq n$. Since $\begin{pmatrix}m\\k\end{pmatrix}$ is the number of subsets of $\{0,\cdots,m-1\}$ with $k$ elements, it is also the number of subsets of $\{0,\cdots,n\}$ with $k+1$ elements and $m$ as the largest element.

These two counts count the same thing, and, therefore, are equal.

there is also a straightforward inductive proof based on $$\sum_{m=k}^{n+1} {m \choose k}= \sum_{m=k}^n {m \choose k}+{n+1 \choose k} = {n+1 \choose k+1}+{n+1 \choose k}={n+2 \choose k+1}$$

Observe that when we introduce the integral representation $${m\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{k+1}}\; dz$$

we get for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{m=k}^n \frac{(1+z)^m}{z^{k+1}}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \sum_{m=k}^n (1+z)^m \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \frac{(1+z)^{n+1}-(1+z)^k}{1+z-1} \;dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+2}} \left((1+z)^{n+1}-(1+z)^k\right) \; dz.$$

This has two pieces, the first of which is $${n+1\choose k+1}$$ and the second, which is zero, thus concluding the proof.

This MSE link has another computation in the same spirit.