# Proving $\binom{2n}{n} + \binom{2n}{n+1}= \frac{1}{2} \binom{2n+2}{n+1}$ using a combinatorial argument

I have to prove $$\binom{2n}{n} + \binom{2n}{n+1}= \frac{1}{2} \binom{2n+2}{n+1}$$ using a combinatoric argument.

My work: on the LHS I can see that I can interpret the first two terms as choosing the number of subsets of size $$n$$ from a set of size $$2n$$ and the second term as choosing all the subsets of size $$n+1$$ from a subset of size $$2n$$. I'm not sure how to interpret the RHS though

## 1 Answer

Let $$S= \{x_1,x_2, \ldots x_{2n+2} \}$$ be an arbitrary set with $$2n+2$$ elements. We can interpret the left hand side as the number of ways of choosing $$n+1$$ elements from $$S$$ such that $$x_1$$ is not chosen. To see this note $$\binom{2n}{n}$$ counts the number of ways of choosing a subset given that $$x_1$$ is not chosen AND $$x_2$$ is chosen, while $$\binom{2n}{n+1}$$ is the number of ways of choosing a subset given that $$x_1$$ is not chosen AND $$x_2$$ is not chosen either.

Now try to interpret the RHS as the same thing. Answer is hidden below:

The right hand side counts the same thing in a different way. First count all subsets containing $$n+1$$ elements, this is $$\binom{2n+2}{n+1}$$ then throw out all the subsets that contain $$x_1$$, which is half of them.

• I understand everything except the last part in the hidden answer. Why do half of the subsets contain $x_1$? – user140161 Apr 17 at 20:33
• The number of subsets containing $x_1$ is $\binom{2n+1}{n}$ while the number of subsets not containing $x_1$ is $\binom{2n+1}{n+1}$. But since $\binom{n}{k} =\binom{n}{n-k}$, we have $\binom{2n+1}{n} = \binom{2n+1}{2n+1-n} = \binom{2n+1}{n+1}$. So the number of subsets that don't contain $x_1$ equals the number of subsets that do. So the number of subsets not containing $x_1$ is just half of all the subsets. – Edgar Jaramillo Rodriguez Apr 17 at 20:41