This question is from the book Discrete mathematics and its applications, by K. Rosen, 6th chapter and 27th question.
Show that if n is a positive
integers $2C(2n, n+1) + 2C(2n, n) =
C(2n+2,n+1)$
I know how to prove this algebraically, applying the formula and this is how it is also given in hints. Since I want to understand counting arguments I am thinking to give a proof of this using combinatorial arguments (double counting).
The right side is the number of ways to select n+1 elements from 2n+2 elements. But I am not able to get an argument for the left side. I'm not getting how can I argue that I need to choose n or n+1 elements from 2n elements twice.
Any other (counting) approaches are also fine. Thank you.
Best Answer
Right Hand Side
Alex, Mary, and $2n$ other children attend a class. The teacher want to choose $n+1$ children to join a competition. The number of possible teams are given by the right hand side:
$$ \binom{2n+2}{n+1} $$
Left Hand Side
There are four possibilities: both Alex and Mary not in the team, both Alex and Mary in the team, Alex in the team but not Mary, Mary in the team but not Alex. The number of such team, respectively, are given by the following:
$$ \binom{2n}{n+1}+\binom{2n}{n-1}+\binom{2n}{n}+\binom{2n}{n} $$
Conclusion
Since both left and right hand side counts the same objects they must be equal
$$ \binom{2n}{n-1}+\binom{2n}{n+1}+2\binom{2n}{n}=\binom{2n+2}{n+1} $$
Additional Remarks
The left hand side is Vandermonde’s identity:
$$ \sum_{j=0}^{2}{\binom{2}{j}\cdot\binom{2n}{n+1-j}} $$