A combinatorial proof for $\binom mk$+$\binom m{k-1}$=$\binom {m+1}k$

Question

I do realize that there is a elementary proof of this result which follows from applying the formula $$\binom mk=\frac{m \cdot (m-1) \cdot \ldots \cdot (m-k+1)}{k!}.$$

I do wonder if there is an elegant counting trick that leads to this?

$$\binom mk+\binom m{k-1}=\binom {m+1}k$$

Answer 1

Let $M = \{1,2,\ldots,m+1\}$ and $X$ be the set of all $k$-subsets (subsets of size $k$) of $M$. We are going to count the elements of $X$ in two ways.

(1) The obvious answer is $$\#X = \binom{m+1}{k}.$$

(2) Now we count by making the distinction if the $k$-subsets contain the element $m+1$ or not: There are $\binom{m}{k-1}$ $k$-subsets of $M$ containing the element $m+1$ , and $\binom{m}{k}$ $k$-subsets of $M$ not containing the element $m+1$. So $$\#X = \binom{m}{k-1} + \binom{m}{k}.$$

Equaling those two expressions for $\#X$ yields the considered identity.

Answer 2

Intuitively you may think about it this way: Picking $k$ elements from a set $X$ of $m+1$ elements can be done by first picking an element $x$ from $X$. Then you may either proceed by picking $k-1$ elements from $X\backslash \{x\}$ or you may "forget" about the first element you picked and pick $k$ elements from $X \backslash \{x\}$.

Answer 3

How many $5$-card poker hands are there? $\binom{52}{5}$.

---

How many $5$-card poker hands are there that exclude the ace of spades? $\binom{51}{5}$.

How many $5$-card poker hands are there that include the ace of spades? Since the ace of spades is one of the $5$, there are $\binom{51}{4}$ such hands.

---

Hence, $$\binom{52}{5}=\binom{51}{5}+\binom{51}{4}$$

Answer 4

V. Chvátal usually presents it this way:

Think of a room with $m+1$ persons. One of them is wearing a red hat!

Now you want to invite $k$ persons to your place. The obvious number of possibilities is $m+1 \choose k$.

Let us count it in another way. You can either invite the guy with the hat and pick $k-1$ persons among the $m$ others in $m \choose k-1$ ways. Or you do not invite the guy with the hat and pick your $k$ guests among the $m$ others in $m \choose k$ ways.

We have counted the same thing twice so the results are equal.

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

Most of the binomial equalities can be found with a few people and some hats.