2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I understand everything except the last part in the hidden answer. Why do half of the subsets contain $x_1$? $\endgroup$ – user140161 Apr 17 at 20:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Edgar Jaramillo Rodriguez Apr 17 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.