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

Question

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

Answer 1

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.