1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Again? math.stackexchange.com/questions/4208089/… $\endgroup$
    – Robert Z
    Commented Jul 27, 2021 at 15:02
  • $\begingroup$ @Robert Z The previous one was closed but I'm still struggling with this problem $\endgroup$
    – IGY
    Commented Jul 27, 2021 at 15:23

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – IGY
    Commented Jul 27, 2021 at 15:49
  • 1
    $\begingroup$ 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$? $\endgroup$ Commented Jul 27, 2021 at 15:54
  • $\begingroup$ 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? $\endgroup$
    – IGY
    Commented Jul 27, 2021 at 16:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .