How to prove this combinatorially $\binom{n}{k}+\binom{n+1}{k}+\binom{n+2}{k}+\cdots+\binom{n+m}{k} = \binom{n+m+1}{k+1}-\binom{n}{k+1}$?

Question

$n,m,k$ are natural numbers.

$$\binom{n}{k}+\binom{n+1}{k}+\binom{n+2}{k}+\cdots+\binom{n+m}{k} = \binom{n+m+1}{k+1}-\binom{n}{k+1}$$

I need to prove this combinatorially but I can't think of a story, how can I approach this? I thought about starting from the left side

Answer 1

You could re-arrange as follows:

$$\binom{n}{k+1}+\binom{n}{k}+\binom{n+1}{k}+\binom{n+2}{k}+...+\binom{n+m}{k} = \binom{n+m+1}{k+1}$$

Then repeatedly apply Pascal's rule to the first two terms on the left side, until you are left with only one term. Since Pascal's rule has a combinatorial proof, this should qualify as a combinatorial proof (no algebraic expansion of the binomial coefficient used).

Answer 2

This should work. As to whether it's 'combinatorial', I leave that to others.

Choose $k+1$ different integers from $[1..n+m+1]$. That is the one term from the right-hand side, $\binom{n+m+1}{k+1}$. Let $x$ be the largest of these integers. There are $\binom{n}{k+1}$ ways to choose the numbers if $x\leq n$. If $x=n+i$ then there are $\binom{n+i-1}{k}$ ways to choose the others. Sum and you get it.

Answer 3

${n \choose r} + {n \choose r+1} = {n+1 \choose r+1}$

---

${n \choose k} = {n+1 \choose k+1} - {n \choose k+1}$ .....(1)

${n+1 \choose k} = {n+2 \choose k+1} - {n+2 \choose k+1}$.....(2) .

.

.

.

.

${n+m \choose k} = {n+m+1 \choose k+1} - {n+m\choose k}$.....(m)

---

(1) + (2).............(m) implies

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

Answer 4

First, note that $\binom{n}{k+1}$ is the number of size $k+1$ subsets of $\{\color{green}1,\color{green}2,\dots\color{green}n\}$, and $\binom{n+m+1}{k+1}$ is the number of size $k+1$ subsets of $S=\{\color{green}1, \color{green}2,\dots\color{green}n,\color{orange}1,\color{orange}2\dots\color{orange}{m+1}\}$. [If you can’t see the colors, the first $n$ elements listed are green, and the remaining $m+1$ are orange.]

Then (think about it), $C=\binom{n+m+1}{k+1}-\binom{n}{k+1}$ is the number of size $k+1$ subsets of $S$ that contain at least one orange element. Therefore in any particular one of the sets $C$ enumerates, there is a largest orange element between $\color{orange}1$ and $\color{orange}{m+1}$

Let $C_g$ be the number of subsets of $S$ in which the largest orange element is $g$. The sets $C_g$ are disjoint, and $|C|=|C_1|+\cdots+|C_{m+1}|$.

Finally, $|C_s|=\binom{n+s-1}{k}$, because each size $k+1$ subset of $S$ with largest orange element $\color{orange}s$ corresponds to a size $k$ subset of the first (in the listing above) $n+s-1$ elements of $S$ (the ones listed before the orange $\color{orange}s$) together with the orange $\color{orange}s$.

Putting the last two paragraphs together, the proof is completed.