How do you prove that $\sum\limits_{r=0}^{n}\binom{n}{r}\binom{n+r}{r} =\sum\limits_{r=0}^{n}( -1)^{n-r} 2^{r}\binom{n}{r}\binom{n+r}{r}$?

Question

While proving this on Quora, I came across this equality:

$\displaystyle \sum _{r=0}^{n}\binom{n}{r}\binom{n+r}{r} =\sum _{r=0}^{n}( -1)^{n-r} 2^{r}\binom{n}{r}\binom{n+r}{r}\tag*{}$

Like how did $2^r$ and $(-1)^{n-r}$ just pop up out of no where? Though I could prove it using calculus, is there any alternate solution or any intuition to why these sums are equal?

$\displaystyle \begin{align*} & \sum _{r=0}^{n}\binom{n}{r}\binom{n+r}{r}\tag{01}\\ & =\frac{1}{n!}\sum _{r=0}^{n}\binom{n}{r}\frac{\mathrm{d}^{n} \ x^{n+r}}{\mathrm{d} x^{n}}\Bigl|_{x=1}\tag{02}\\ & =\frac{1}{n!} \frac{\mathrm{d}^{n} \ x^{n}( 1+x)^{n}}{\mathrm{d} x^{n}}\Bigl|_{x=1}\tag{03}\\ & =\frac{1}{n!} \frac{\mathrm{d}^{n} \ x^{n}( 2x-1)^{n}}{\mathrm{d} x^{n}}\Bigl|_{x=1}\tag{04}\\ & =\frac{1}{n!} \frac{\mathrm{d}^{n}}{\mathrm{d} x^{n}}\left( x^{n}\sum _{r=0}^{n}\binom{n}{r}( 2x)^{r}( -1)^{n-r}\right)\Bigl|_{x=1}\tag{05}\\ & =\frac{1}{n!}\sum _{r=0}^{n}( -1)^{n-r} 2^{r}\binom{n}{r}\frac{\mathrm{d}^{n} x^{n+r}}{\mathrm{d} x^{n}}\Bigl|_{x=1}\tag{06}\\ & =\sum _{r=0}^{n}( -1)^{n-r} 2^{r}\binom{n}{r}\binom{n+r}{n}\tag{07} \end{align*}$

I am explaining some of the steps which are not obvious.

$(02)$: Look up the formula for $n^{th}$ derivative of $x^m$.

$(03)$: Pull out the derivate and $x^n$ outside the sum and apply binomial theorem.

$(04)$: I've used General Leibniz rule to get (04) and (05) equal.

Answer 1

The Equation from the Question $$ \begin{align} \sum_{r=0}^n(-1)^{n-r}2^r\binom{n}{r}\binom{n+r}{r} &=\sum_{r=0}^n(-1)^n\sum_{k=0}^n\binom{r}{k}\binom{n}{r}\binom{-n-1}{r}\tag{1a}\\ &=\sum_{k=0}^n\sum_{r=0}^n(-1)^n\binom{n-k}{n-r}\binom{n}{k}\binom{-n-1}{r}\tag{1b}\\ &=(-1)^n\sum_{k=0}^n\binom{n}{k}\binom{-k-1}{n}\tag{1c}\\ &=\sum_{k=0}^n\binom{n}{k}\binom{n+k}{n}\tag{1d} \end{align} $$ Explanation:
$\text{(1a):}$ $(-1)^r\binom{n+r}{r}=\binom{-n-1}{r}\quad$ (negative binomial coefficient)
$\phantom{\text{(1):}}$ $2^r=\sum\limits_{k=0}^r\binom{r}{k}=\sum\limits_{k=0}^n\binom{r}{k}$ since $\binom{r}{k}=0$ for $k\gt r$
$\text{(1b):}$ $\binom{r}{k}\binom{n}{r}=\binom{n-k}{n-r}\binom{n}{k}\quad$ (expand into ratios of factorials)
$\text{(1c):}$ sum in $r\qquad\qquad\quad$ Vandermonde's Identity
$\text{(1d):}$ $(-1)^n\binom{-k-1}{n}=\binom{n+k}{n}\quad$ (negative binomial coefficient)

---

The Form from Sarvesh Ravichandran Iyer's Answer $$ \begin{align} \sum_{k=0}^n\binom{n}{k}\binom{n+k}{n} &=\sum_{k=0}^n\sum_{j=0}^n\binom{n}{k}\binom{k}{j}\binom{n}{n-j}\tag{2a}\\ &=\sum_{j=0}^n\sum_{k=0}^n\binom{n-j}{k-j}\binom{n}{n-j}\binom{n}{n-j}\tag{2b}\\ &=\sum_{j=0}^n2^{n-j}\binom{n}{n-j}\binom{n}{n-j}\tag{2c}\\ &=\sum_{j=0}^n2^j\binom{n}{j}^2\tag{2d} \end{align} $$ Explanation:
$\text{(2a):}$ $\binom{n+k}{n}=\sum\limits_{j=0}^n\binom{k}{j}\binom{n}{n-j}\quad$ (Vandermonde's Identity)
$\text{(2b):}$ $\binom{n}{k}\binom{k}{j}=\binom{n-j}{k-j}\binom{n}{n-j}\quad$ (expand into ratios of factorials)
$\text{(2c):}$ $2^{n-j}=\sum\limits_{k=j}^n\binom{n-j}{k-j}=\sum\limits_{k=0}^n\binom{n-j}{k-j}$ since $\binom{n-j}{k-j}=0$ for $k\lt j$
$\text{(2d):}$ substitute $j\mapsto n-j$

Answer 2

Here's a combinatorial proof of the statement that $$ \sum_{r=0}^n \binom{n}{r}\binom{n+r}{r}=\sum_{r=0}^n (-1)^{n-r}2^r\binom{n}{r}\binom{n+r}r \tag{1} \label{1} $$

In fact, we will prove that there is a third quantity that is equal to both of them, and is probably simpler to write than both as well.

---

The set we will count is the following.

Given a set $B$ of $n$ boys and a set $G$ of $n$ girls, choose a subset $S = S_B \cup S_G$ of size $n$ consisting of $|S_B|$ boys (where $S_B \subset B$) and $|S_G|$ girls (where $S_G \subset G$). Note that both $S_B,S_G$ can be empty. After this, choose a (possibly empty) subset $S_G' \subset S_G$ of "special" girls from $S$. The number of pairs $(S,S'_G)$ are to be counted (as a function of $n$, of course).

To count the number of pairs $S_G$ as the left-hand side of \eqref{1}, let's start by labelling the special girls. Fix $0 \leq r \leq n$ and suppose that out of the $n$ girls, we exclude $r$ of them and take the rest of the $n-r$ girls to form $S_G$ so that $|S_G| = n-r$. Now, from $(B \cup G) \setminus S_G$, which is a set of size $2n-(n-r) = n+r$, we take any $r$ people to get a set $S_r \subset (B \cup G) \setminus S_G$ such that $|S_r| = r$. We then include this with $S_G$ to get $S = S_r \cup S_G$, and hence the pair $(S,S_G)$.

The number of ways of choosing $S_G$ is $\binom{n}{r}$ because we choose $r$ girls to exclude. The number of ways of choosing $S$ after this is $\binom{n+r}{r}$ because it's the same as the number of ways of choosing $S_r$, which is a choice of $r$ elements out of $n+r$. Since this is true for all $0 \leq r \leq n$, the number of pairs $(S,S_G)$ equals the right hand side of \eqref{1}.

---

Now for the other side, which is a little more tricky. The idea is that we have to play the inclusion-exclusion-principle game with some care.

For this, let's think about the terms of the summation. For $r=n$, it is $\binom{2n}{n}2^n$. This is like choosing a subset $S \subset B \cup G$ and then allowing any of two possibilities for each chosen person. However, that's a problematic assumption, because for boys already in $S$ there isn't a "second" option once they're already in $S$, such as being special in the case of girls.

One might be tempted to abandon the thinking here, but let's see : suppose we gave the boys the option of being special as well. How I wish I could be special.

Then,$\binom{2n}{n}2^n$ is the number of ways that we can create $(S , S')$ where $|S|=n$ and $S' \subset S$ is any subset of special boys and girls. Obviously, choose the subset $S$ in $\binom{2n}{n}$ ways and let each of the $n$ people in $S$ be special or not, which is two choices each giving $2^n$ ways for $S'$.

Now let's go to $r=n-1$, where we have $-n2^{n-1}\binom{2n-1}{n-1}$. This is like saying the following : choose one boy $b$ to remove from $B \cup G$ in $n$ ways. Then, from the remaining $2n-1$ people choose $n-1$ people to put in $S$. Put $b \in S$ to make it $n$ people. Make $b$ special. Then allow the other $n-1$ people to be special or not freely. It follows that $n2^{n-1}\binom{2n-1}{n-1}$ counts $(S,S')$ where $|S| = n$ and the set of special people $S' \subset S$ has at least one special boy(namely $b$ in our description).

Now for $r=n-2$, where we have $2^{n-2}\binom{n}{2}\binom{2n-2}{n-2}$. Again, let's exclude two boys $b_1,b_2$ from $B \cup G$ in $\binom{n}{2}$ ways. Then from the remaining $2n-2$ people choose $n-2$ people to put in $S$, and put $b_1,b_2 \in S$. Make $b_1,b_2$ special, and let the other $n-2$ people decide whether they want to be special or not. It follows that $2^{n-2}\binom{n}{2}\binom{2n-2}{n-2}$ counts the number of $(S,S')$ where $|S|=n$ and $S' \subset S$ has at least two special boys, namely $b_1,b_2$.

It should now be fairly clear to anyone that $2^r\binom{n}{r}\binom{n+r}{r}$ counts the number of $(S,S')$ such that $|S|=n$ and $S' \subset S$ has at least $n-r$ special boys.

This extremely intuitive line of reasoning tells us that there is good reason to believe that making boys special can be used to get an answer.

What do we want? We want the number of $(S,S')$ in which there are exactly zero special boys i.e. all the girls are special so that $S' \subset G$. How can we calculate this?

The inclusion-exclusion principle was getting warmed up on the touchline while the game , initially turgid, opened up a little. It is now time for the substitute to make its impact off the bench.

Well, we've now got the basic idea : for the boys $b_1,\ldots,b_n$, let $A_i, 1 \leq i \leq n$ be the set of all $(S,S')$ where $|S|=n$ and $b_i \in S' \subset S$ so that $b_i$ is special. Then, the answer we need is the size of $(\cup_{i=1}^n A_i)^c$ , where the complement is taken in the set of all $(S,S')$ such that $|S|=n$ and $S' \subset S$, which we know has size $\binom{2n}{n}2^{n}$. So the answer is $$ \binom{2n}{n}2^{n} - \left|\bigcup_{i=1}^n A_i\right| $$

By the inclusion-exclusion principle, $$ \left|\bigcup_{i=1}^n A_i\right| = (-1)^{1-1}\sum_i |A_i| \\+(-1)^{2-1} \sum_{i \neq j} |A_i \cap A_j| \\+ (-1)^{3-1}\sum_{i\neq j \neq k} |A_i \cap A_j \cap A_k|\\+\ldots +(-1)^{n-1} \pm |A_1\cap \ldots \cap A_n| \tag{2} \label{2} $$

Do we know these probabilities? Let's think about just $|A_i|$ for now. One special boy $b_i\in S' \subset S$ is already done, so we choose the rest of the $n-1$ people in $\binom{2n-1}{n-1}$ ways to put in $S$ and let each element of this lot be special or not in $2^{n-1}$ ways. So, $|A_i| = \binom{2n-1}{n-1}2^{n-1}$ for each $i=1,\ldots,n$. In particular , $\sum_i |A_i| = n\binom{2n-1}{n-1}2^{n-1}$. You can see where this is going!

Indeed, $|A_i \cap A_j|$ for $i \neq j$ means that both $b_i,b_j$ are special. Go for it : from the rest of the $2n-2$ people, pick $n-2$ to make up $n$ people for $S$ in $\binom{2n-2}{n-2}$ ways. Let these $n-2$ decide whether they want to be special or not in $2^{n-2}$ ways. That's the answer $|A_i \cap A_j| = \binom{2n-2}{n-2}2^{n-2}$ for each $i \neq j$. There are $\binom{n}{2}$ choices for $i \neq j$ so $$ \sum_{i \neq j} |A_i \cap A_j| = \binom{n}{2}\binom{2n-2}{n-2}2^{n-2} $$

Using similar arguments, $$ \sum_{i_1 \neq i_2 \neq \ldots \neq i_k} |A_{i_1} \cap A_{i_2}\cap \ldots A_{i_k}| = \binom{n}{k}\binom{2n-k}{n-k}2^{n-k} $$

Whence it follows by \eqref{2} that the answer is $$ \binom{2n}{n} - \sum_{k=1}^n (-1)^{k-1} \binom{n}{k}\binom{2n-k}{n-k}2^{n-k} $$ The reindexing $k \to n-k$ in the sum yields $$ 2^n\binom{2n}{n} + \sum_{k=0}^{n-1} (-1)^{n-k}2^k\binom{n}{k}\binom{n+k}{k} = \sum_{k=0}^n (-1)^{n-k}2^k\binom{n}{k}\binom{n+k}{k} $$ as desired. We have obtained the right hand side of \eqref{1} using very little algebra (which, frankly, can be avoided with a very slight adjustment that I will have an interested reader make) and excellent use of the inclusion exclusion principle.

---

Perhaps what is more surprising is that there is a third expression for both sides of \eqref{1}. To see this, let's count the same set, $(S,S')$ where $|S|=n$ and $S'$ is a subset of special girls from $S$.

Indeed, for fixed $r$, pick $r$ girls and $n-r$ boys to form $S$. This is done in $\binom{n}{r} \times \binom{n}{n-r} = \binom{n}{r}^2$ ways. Then let each girl decide if they want to be special or not, in $2^r$ ways. The set of special girls becomes $S'$. Using this argument and letting $r$ vary, the given set also has size $\sum_{r=0}^n 2^r \binom{n}{r}^2$.

In other words, \eqref{1} improves to $$ \boxed{\sum_{r=0}^n \binom{n}{r}\binom{n+r}{r}=\sum_{r=0}^n (-1)^{n-r}2^r\binom{n}{r}\binom{n+r}r = \sum_{r=0}^n 2^r \binom{n}{r}^2 } $$

This is a far easier expression than the other two (in my humble opinion). However, the use of IEP is perhaps the highlight of this exposition, along with how you'd go about thinking about the RHS and implementing the IEP.