Proving combinatoric identity using vote casting example.

Question

I'm still having trouble giving a combinatorial proof of this identity using the vote casting example: $$ \sum_{k=0}^m \left(\!\!\binom{n}k\!\!\right) = \left(\!\!\binom{n+1}m\!\!\right), n\geq0 $$

To me, the right-hand side represents casting m votes for n+1 candidates, since it's a multiset, that seems like we could cast multiple votes for the same candidate. This is equivalent to sum over all the votes each candidate has received, as on the left-hand side.

Is my interpretation correct? I'm still not pretty sure about why the right-hand side has n+1 candidates, while the left side has n. Thanks:)

Note: $\displaystyle\left(\!\!\binom{n}{k}\!\!\right)$ stands for multiset.

Answer 1

Let's look at a specific case; you want to show $$\newcommand\mchoose[2]{\left(\!\!\left({#1}\atop{#2}\right)\!\!\right)}\mchoose74=\mchoose60+\mchoose61+\mchoose62+\mchoose63+\mchoose 64\tag{$*$}$$

Imagine candy shop has $7$ types of candy bar, and you want to buy four candy bars. The number of ways to do this is $\mchoose 74$, on the one hand. On the other had, consider the number of chocolate bars you buy:

• You could buy $0$ chocolate bars, and then buy four bars from the remaining six flavors in $\mchoose 64$ ways.
• You could buy $1$ chocolate bars, and then buy three bars from the remaining six flavors in $\mchoose 63$ ways.
• You could buy $2$ chocolate bars, and then buy two bars from the remaining six flavors in $\mchoose 62$ ways.
• You could buy $3$ chocolate bars, and then buy one bar from the remaining six flavors in $\mchoose 61$ ways.
• You could buy $4$ chocolate bars, and then buy zero bars from the remaining six flavors in $\mchoose 60$ ways.

Adding up all of these ways, you get the summation on the right hand side of $(*)$.

Answer 2

Hint:

The right side means -- as you've suggested -- the number of ways to cast $m$ votes for $n+1$ candidates (when repetition is allowed).

Break this down into cases based on how many votes go to candidate $n+1$.