Combinatorial Proof (Wanting a Second Opinion)

Question

Let's say we have $$\binom{n+1}{r+1} = \sum_{j=r}^{n}\binom{j}{r}$$

The story is going to be, We are choosing a group with a leader.

The LHS is saying, out of $n+1$ people, we pick $r+1$ people to be in the group. The $+1$ is the leader is already chosen.

RHS is saying, out of all cases we choose a leader and then choose the remaining people to join the group.

The righthand side is making me second guess what I have written.

If wrong, what is it? Also, if anyone has any tips to reading what a summation means in a proof like this, that would be greatly appreciated!

Answer 1

Others have pointed out why your story doesn’t match the identity. Here’s a different story that does. $\binom{n+1}{r+1}$ is of course the number of ways to choose a team of $r+1$ people from a pool of $n+1$ people. Now imagine that no two of the $n+1$ people are the same height, line them up from shortest to tallest, and number them from $0$ through $n$. How many ways are there to choose your team so that the tallest person on it is number $j$? Your team will consist of number $j$ and $r$ of the $j$ shorter people, the ones with numbers $0$ through $j-1$. You can choose those $r$ people in $\binom{j}r$ ways, so there are $\binom{j}r$ teams whose tallest member is number $j$, and summing over the possible values of $j$ will then give us the total number of possible teams. Clearly $j$ must be at least $r$, as otherwise there aren’t $r$ shorter people available, and $j$ cannot exceed $n$, the number of the tallest person, so

$$\binom{n+1}{r+1}=\sum_{j=r}^n\binom{j}r\,.$$

Answer 2

Your story is wrong.

If I have $n$ people, I choose a leader, then I make a decision with $k$ possibilities, then the total number of possibilities I have is $nk$. So choosing an unordered set, then choosing a leader out of it, is going to have an additional term on top of the binomial coefficient.

To answer your second question, the role of a summation in a combinatorial proof like this is to cover different disjoint cases. Counting a set which may be partitioned is the sum of the counts of each of the partitions.

---

The proof using team-making is, in my view, rather non-obvious. Are you familiar with stars and bars?

Answer 3

The left side is the number of ways to put $n-r$ items into $r+2$ bins: $\binom{\text{items}+\text{bins}-1}{\text{bins}-1}$

The right side is the number of ways to put $k=0$ to $k=n-r$ items into $r+1$ bins, saving the other $n-r-k$ items for bin $r+2$.