How can I calculate $\sum_{i=0}^{n}\sum_{j=i}^{n} \binom{n+1}{j+1}\binom{n}{i}$

Question

I tried Google and various ways, including walking the list questions in the chronological order as far. How can I show

$$\sum_{i=0}^{n}\sum_{j=i}^{n} \binom{n+1}{j+1}\binom{n}{i}=2^{2n}$$

Please guide me. Thank you for your help!

Answer 1

Here is a combinatorial proof.

Consider two rows of lamps, the left one with $n$ and the right with $n+1$ lamps; all the lamps are off to start with. Let's count the number of ways to turn a subset of them on.

First look at the left row, and choose $i$ lamps to turn on. Then, from the right row choose $j$ lamps such that $j>i$.

The number of ways to do this is exactly your summation.

But obviously, we didn't count all ways to turn a subset of the $2n+1$ lamps on (that would be $2^{2n+1}$). We only counted the situations where the right row has more lamps turned on then the left row has.

However, there is a bijection between the situations we did count and the ones we didn't count: taking the complement of the chosen lamps in both rows, we will obtain all situations where the number of lamps turned on in the right row is less than or equal the number of lamps turned on in the left row. (Consider the map $(i,j)\mapsto(n-i,n+1-j)$, which tells what happens with the number of lamps in each row. Note that $i<j$ if and only if $n-i\geq n+1-j$.)

Thus, we counted exactly half of the possibilities, that is $\frac{2^{2n+1}}{2}=2^{2n}$.

Answer 2

Here's an algebraic version of barto's combinatorial proof: we'll show that twice your expression is equal to $2^{2n+1}$. \begin{align*} 2 \sum_{i=0}^n \sum_{j=i}^n \binom{n+1}{j+1} \binom ni &= \sum_{i=0}^n \sum_{j=i}^n \binom{n+1}{j+1} \binom ni + \sum_{i=0}^n \sum_{j=i}^n \binom{n+1}{j+1} \binom ni\\ &= \sum_{i=0}^n \sum_{k=i+1}^{n+1} \binom{n+1}k \binom ni + \sum_{i=0}^n \sum_{j=i}^n \binom{n+1}{n-j} \binom n{n-i} \\ &= \sum_{i=0}^n \binom ni \sum_{k=i+1}^{n+1} \binom{n+1}k + \sum_{i=0}^n \binom n{n-i} \sum_{k=0}^{n-i} \binom{n+1}k \\ &= \sum_{i=0}^n \binom ni \sum_{k=i+1}^{n+1} \binom{n+1}k + \sum_{i=0}^n \binom ni \sum_{k=0}^i \binom{n+1}k \\ &= \sum_{i=0}^n \binom ni \sum_{k=0}^{n+1} \binom{n+1}k = 2^n \cdot 2^{n+1}. \end{align*} In the second line, we changed variables $k=j+1$ in the first double sum and used the symmetry of the binomial coefficients in the second double sum. In the third line, we made the change of variables $k=n-j$. And in the fourth line, we replaced $i$ by $n-i$.