# Combinatorial proof of a binomial coefficient summation.

Let $n$ and $k$ be integers with $1 \leq k \leq n$. Show that:

$$\sum_{k=1}^n {n \choose k}{n \choose k-1} = \frac12{2n+2 \choose n+1} - {2n \choose n}$$

I was told this is supposed to use a combinatorial proof and while I'm not that comfortable with that, many similar proofs use a mathematical proof that shows equality. Any guidance would be much appreciated.

-

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.

-
Sorry if I'm being really naive but I don't see where you get that from the equation above. –  Planeman Nov 23 '10 at 4:33
@Planeman: Sorry I have not yet completed my answer yet. Will do so in the next 10 minutes. –  user17762 Nov 23 '10 at 4:35
Wow that was a lot thank you. Give me a little time to process, usually this stuff comes back on tests so I want to understand it. –  Planeman Nov 23 '10 at 4:50
(though I would suggest giving hints first(rather than complete solutions), to homework/exam practice problems). –  Aryabhata Nov 23 '10 at 16:38
@ Moron: I do understand that in learning it isn't always beneficial to be given the answer up front but in this case I had already been looking at this for several hours and the setup for the combinatorial proof is what was key to me making past that. Everything in the remaining cases is counting that I was already doing but I just couldn't connect it all. –  Planeman Nov 24 '10 at 4:59

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

-

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.

-
This explanation is very interesting; it helped me very much. I would like to add the following remark: $\sum_{k=1}^n \binom{n}{n-k}\binom{n}{k-1}=\binom{2n}{n-1}$ is a special form of Vandermonde's identity. This identity is: $\binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{r-k}\binom{n}{k}$. The aforesaid special form is obtained by doing $m = n$ and $r = n - 1$. This yields: $\binom{2n}{n-1} = \sum_{k=0}^{n-1}\binom{m}{n-1-k}\binom{n}{k}$, which is the same as $\binom{2n}{n-1} = \sum_{k=1}^{n}\binom{m}{n-k}\binom{n}{k-1}$; this can be seen by replacing $k$ with $k - 1$. –  anonymous Jan 26 '12 at 23:38
Continuing from the comment above: Vandermonde's identity can be justified as follows: suppose there are m elements in one set and n elements in another set. Then the number of ways to choose r elements from the union of these sets is $\binom{m+n}{r}$. Another way is to choose k elements from the first set and then r - k elements from the second set (where k is an integer with $0 \leq k \leq r$), which can be done in $\binom{m}{r-k}\binom{n}{k}$ ways. –  anonymous Jan 26 '12 at 23:40


Note that \begin{align}\color{#c00000}{\half\,{2n + 2 \choose n + 1} - {2n \choose n}}&= \half\,{\pars{2n + 2}! \over \pars{n + 1}!\pars{n + 1}!} -{\pars{2n}! \over n!\,n!} ={\pars{2n + 2}! - 2\pars{n + 1}^{2}\pars{2n}!\over 2\bracks{\pars{n + 1}!}^{2}} \\[3mm]&={2\pars{n + 1}\pars{2n + 1}\pars{2n}! - 2\pars{n + 1}^{2}\pars{2n}!\over 2\pars{n + 1}n\pars{n - 1}!\pars{n + 1}!} \\[3mm]&={\pars{n + 1}\pars{2n + 1} - \pars{n + 1}^{2} \over \pars{n + 1}n}\, {\pars{2n}! \over \pars{n - 1}!\pars{n + 1}!} \\[3mm]&={\pars{n + 1}\bracks{\pars{2n + 1} - \pars{n + 1}} \over \pars{n + 1}n}\, {2n \choose n - 1} = \color{#c00000}{{2n \choose n - 1}} \end{align}

-