Combinatorial proof of a binomial coefficient summation.

The Combinatorial Proof goes as follows:

Consider three boxes $A$,$B$ and $C$.

Box $A$ contains $n$ balls, Box $B$ contains $n$ balls, and Box $C$ contains $2$ balls.

We want to choose $n+1$ balls out of these three boxes.

The total number of ways is $C(2n+2,n+1)$.

This can be split as follows.

You choose $2$ balls from box $C$ and the remaining $n-1$ balls from boxes $A$ and $B$ or you choose $1$ ball from box $C$ and the remaining $n$ balls from boxes $A$ and $B$ or you choose all the $n+1$ balls from boxes $A$ and $B$.

$\textbf{Case 1:}$

Suppose you choose $2$ balls from box $C$.

There is only one way of choosing these $2$ balls from the box $C$.

We now need the number of ways of choosing $n-1$ balls from boxes $A$ and $B$.

Say if you choose $k$ balls from box $A$, you need to choose $n-k-1$ balls from box $B$.

Number of ways of choosing $k$ balls from box $A$ and $n-k-1$ balls from box $B$ is given by $C(n,k)C(n,n-k-1)$.

Now summing over all possible values of $k$ from $0$ to $n-1$ we get,

Total number of ways is $\displaystyle \sum_{k=0}^{n-1} C(n,k)C(n,n-k-1)$.

Now, $C(n,r) = C(n,n-r)$. (For a combinatorial argument of this see the bottom of the post).

Hence, Total number of ways for the current case is $1 \times \displaystyle \sum_{k=0}^{n-1} C(n,k)C(n,k+1) = \displaystyle \sum_{k=1}^{n} C(n,k-1)C(n,k)$.

$\textbf{Case 2:}$

Suppose you choose $1$ ball from the box $C$. You need to now choose the remaining $n$ balls from boxes $A$ and $B$.

Number of ways of choosing $1$ ball from box $C$ is given by $C(2,1) = 2$.

There are $2n$ balls in total in boxes $A$ and $B$ and hence the total number of ways of choosing $n$ balls from boxes $A$ and $B$ is $C(2n,n)$.

Hence, the total number of ways for the current case is $2 \times C(2n,n)$.

$\textbf{Case 3:}$

Suppose you choose all the $n+1$ balls from boxes $A$ and $B$.

Number of ways of choosing no balls from box $C$ is $1$.

We now need to count the number of ways of choosing $n+1$ balls from boxes $A$ and $B$.

This is similar to Case 1 and we get the total number of ways for this case is $1 \times \displaystyle \sum_{k=1}^{n} C(n,k)C(n,n+1-k) = \displaystyle \sum_{k=1}^{n} C(n,k)C(n,k-1)$.

(Note: Here $k$ goes from $1$ to $n$ since we need to choose atleast $1$ from one of the boxes and we can choose atmost $n$ from each box).

(Also Note: You could directly state that Case 1 and Case 3 should be the same since $C(2n,n-1)=C(2n,n+1)$)

Combine all the three cases to get

$2 \times \displaystyle \sum_{k=1}^{n} C(n,k)C(n,k-1) + 2 \times C(2n,n) = C(2n+2,n+1)$.

Now do the desired algebraic manipulation to get the result.

$\textbf{APPENDIX:}$

The combinatorial argument of $C(n,r) = C(n,n-r)$ is that the number of ways of selecting $r$ out of $n$ things is the same as the number of ways of discarding $n-r$ out of $n$ things.

Using standard binomial identities, this can be proven as follows: $$ \begin{align} \sum_{k=1}^n \binom{n}{k}\binom{n}{k-1}&=\sum_{k=1}^n \binom{n}{n-k}\binom{n}{k-1}\\ &=\binom{2n}{n-1}\\ &=\binom{2n+1}{n}-\binom{2n}{n}\\ &=\frac{n+1}{2n+2}\binom{2n+2}{n+1}-\binom{2n}{n}\\ &=\frac{1}{2}\binom{2n+2}{n+1}-\binom{2n}{n} \end{align} $$ Each identity can be given a simple combinatorial justification.

1. $$ \binom{n}{k}=\binom{n}{n-k} $$ The number of ways to choose $k$ items from $n$ is the number of ways to choose the complement of a set of $k$ items from $n$.

2. $$ \sum_{k=1}^n \binom{n}{n-k}\binom{n}{k-1}=\binom{2n}{n-1} $$ Given a set of green marbles, numbered $1...n$ and red marbles numbered $1...n$, count the choices of $n-1$ marbles from the aggregate $2n$ by counting the choices of $n-k$ green marbles and $k-1$ red marbles.

3. $$ \binom{2n}{n-1}+\binom{2n}{n}=\binom{2n+1}{n} $$ Given a set of green marbles numbered $1...2n$ and $1$ red marble, a choice $n$ marbles from the aggregate $2n+1$ either has the red marble, and thus $n-1$ of the $2n$ green marbles, or doesn't have the red marble, and thus $n$ of the $2n$ green marbles.

4. $$ (2n+2)\binom{2n+1}{n}=(n+1)\binom{2n+2}{n+1} $$ Putting $n+1$ marbles from a bag of $2n+2$ into a box and then choosing $1$ from the box is the same as choosing $1$ from the bag of $2n+2$ marbles and then putting $n$ of the remaining $2n+1$ marbles into the box.

Hint: Use $\displaystyle {n \choose k} = {n \choose n-k}$ and try to count something which equals $\displaystyle {n \choose n-k}{n \choose k-1}$