# Proving combinatoric identity using vote casting example.

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.

• Commented Jul 27, 2021 at 15:02
• @Robert Z The previous one was closed but I'm still struggling with this problem
– IGY
Commented Jul 27, 2021 at 15:23

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 $$(*)$$.

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$$.

• Thanks for the hint, on the first line--should that be the right-hand side? For the left side, could you give me a bit more hint about which cases I may want to discuss?
– IGY
Commented Jul 27, 2021 at 15:49
• For a given $k$, how many ways are there to cast $m$ votes for $n+1$ candidates such that exactly $m-k$ vote for candidate $n+1$? Commented Jul 27, 2021 at 15:54
• Thanks, but I'm still a bit confused, can I understand the right-hand side as how many casts are left for the candidate $n+1$? So this is equivalent to sum over all given $k$ in the possible range?
– IGY
Commented Jul 27, 2021 at 16:09