Proving an identity relating to binomial coefficients

Question

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.

Answer 1

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

Answer 2

Here we show the validity of the binomial identity \begin{align*} \color{blue}{2\binom{2n}{n+1}+2\binom{2n}{n}=\binom{2n+2}{n+1}}\tag{1} \end{align*} by counting lattice paths. We consider lattice paths with horizontal steps $(1,0)$ and vertical steps $(0,1)$. The binomial coefficient \begin{align*} \binom{n}{k}\tag{2} \end{align*} gives the number of lattice paths of length $n$ from $(0,0)$ to $(k,n-k)$ consisting of $k$ horizontal $(1,0)$ steps and $n-k$ vertical $(0,1)$ steps.

Let's have a look at the graphic below. We see an $(n+1)\times(n+1)$ rectangle where we study lattice paths from the origin $(0,0)$ to $(n+1,n+1)$.

                                                

We observe

• The number of lattice paths from $(0,0)$ to $(n+1,n+1)$ is according to (2) equal to \begin{align*} \color{blue}{\binom{2n+2}{n+1}}\tag{3.1} \end{align*}

• A lattice path from $(0,0)$ to $(n+1,n+1)$ has to cross either the blue point $(n,n)$ or one of the orange points $(n-1,n+1)$ or $(n+1,n-1)$ respectively. This way we can partition the lattice paths into three sets.

  • Blue point $(n,n)$: The number of lattice path from $(0,0)$ to the blue point $(n,n)$ is $\binom{2n}{n}$. From the blue point $(n,n)$ there are two ways to go to $(n+1,n+1)$. Either by a horizontal step $(n,n)\to(n+1,n)\to (n+1,n+1)$ or by a vertical step $(n,n)\to(n,n+1)\to(n+1,n+1)$. So we have two possibilities giving a total of \begin{align*} \color{blue}{2\binom{2n}{n}}\tag{3.2} \end{align*} lattice paths.

  • Orange point $(n+1,n-1)$: The number of lattice paths from $(0,0)$ to the orange point $(n+1,n-1)$ is \begin{align*} \binom{2n}{n-1}=\color{blue}{\binom{2n}{n+1}}\tag{3.3} \end{align*} From $(n+1,n-1)$ there is just one possibility to go to $(n+1,n+1)$: namely $(n+1,n-1)\to(n+1,n)\to(n+1,n+1)$. The total number of lattice paths from $(0,0)$ to $(n+1,n+1)$ crossing $(n+1,n-1)$ is therefore $\binom{2n}{n-1}=\binom{2n}{n+1}$.

  • Orange point $(n-1,n+1)$: A symmetrical situation. The number of lattice paths from $(0,0)$ to the orange point $(n-1,n+1)$ is \begin{align*} \color{blue}{\binom{2n}{n+1}}\tag{3.4} \end{align*} Since there is just one possibility to go from $(n-1,n+1)$ to $(n+1,n+1)$: namely $(n-1,n+1)\to(n,n+1)\to(n+1,n+1)$, the total number of lattice paths from $(0,0)$ to $(n+1,n+1)$ crossing $(n-1,n+1)$ is $\binom{2n}{n+1}$.

Putting (3.1) to (3.4) together we see \begin{align*} \color{blue}{2\binom{2n}{n+1}+2\binom{2n}{n}=\binom{2n+2}{n+1}} \end{align*} and the claim (1) follows.

Answer 3

Perhaps this answer is cheating?

First use a counting argument to prove: $$ \binom{m}{r} = \binom{m - 1}{r} + \binom{m - 1}{r - 1} \qquad (m > r \geqslant 1). $$ Apply this identity twice, first taking $m = 2n + 2$ and $r = n + 1$: $$ \binom{2n + 2}{n + 1} = \binom{2n + 1}{n + 1} + \binom{2n + 1}{n} = 2\binom{2n + 1}{n + 1}, $$ and then taking $m = 2n + 1$ and $r = n + 1$: $$ \binom{2n + 1}{n + 1} = \binom{2n}{n + 1} + \binom{2n}{n}. $$

We used the result that $$ \binom{2n + 1}{n} = \binom{2n + 1}{n + 1}. $$ This is a special case of $$ \binom{m}{r} = \binom{m}{m - r} \qquad (m \geqslant r \geqslant 0), $$ which can also be proved by a counting argument.

I'll get me coat. :)