# Finite Double Sum $\sum_{j=0}^n\sum_{i=0}^j \binom {n+1}{j+1}\binom ni =2^{2n}$

The problem is given in a combinatorics class study sheet. I cannot prove, and actually I am not sure if there was a mistake in the question or not. I tried for a few small n's e.g. 1, 2 and it holds. $\\$
I need to show that $\\$ $\mathop{\sum_{j=0}^{n}\sum_{i=0}^{j}}$ $n+1 \choose j+1$ $n \choose i$ = $2^{2n}$ $\forall n$ $\in$ $\mathbb{Z}^{+}$

• $\sum_{j=0}^{n} \sum_{i=0}^{n} \binom{n}{j} \binom{n}{i}$ is certainly equal to $2^{2n}$ – Alex Feb 15 '16 at 17:00

We give a probabilistic interpretation. By changing from probabilities to counts, we get a combinatorial interpretation.

Alicia tosses a fair coin $n+1$ times, and Beti tosses a fair coin $n$ times. Alicia wins if she has more heads than Beti.

Our double sum, divided by $2^{2n+1}$, gives the probability that Alicia wins. We will show that this probability is $\frac{1}{2}$. Then multiplying by $2^{2n+1}$ yields our desired result.

Imagine that the two players each toss their coins simultaneously $n$ times. If Alicia is leading after $n$ tosses, she will win. If Beti is leading after $n$ tosses, then Beti will win. By symmetry these two events are equally likely.

And if they are tied after $n$ tosses, then with probability $\frac{1}{2}$, Alicia will get a head on the $(n+1)$-th toss, and win. And with probability $\frac{1}{2}$ she will get a tail and lose.

Here is another variation of the theme based upon two observations.

The first observation is the calculation of the double sum of the complete region $$0\leq i,j\leq n$$ is simple.

\begin{align*} \sum_{j=0}^n\sum_{i=0}^{n}&\binom{n+1}{j+1}\binom{n}{i}\\ &=\sum_{j=1}^{n+1}\binom{n+1}{j}\sum_{i=0}^{n}\binom{n}{i}\tag{1}\\ &=\left(2^{n+1}-1\right)2^n\\ &=2\cdot4^n-2^n \end{align*}

Comment:

• In (1) we rearrange the double sum and shift the index $j$ by one.

The second observation is based upon symmetry. We could expect the expression of the double sum with the upper triangle $$0\leq j < i\leq n$$ as index range is very similar to the expression with the lower triangle $$0\leq i\leq j \leq n$$ as index range. Indeed, we obtain \begin{align*} \sum_{j=0}^{n}&\sum_{i=j+1}^n\binom{n+1}{j+1}\binom{n}{i}\\ &=\sum_{j=0}^{n}\sum_{i=n-j+1}^n\binom{n+1}{n-j+1}\binom{n}{i}\tag{2}\\ &=\sum_{j=0}^{n}\sum_{i=0}^{j-1}\binom{n+1}{n-j+1}\binom{n}{i+n-j+1}\tag{3}\\ &=\sum_{j=1}^{n}\sum_{i=0}^{j-1}\binom{n+1}{j}\binom{n}{i}\tag{4}\\ &=\sum_{j=0}^{n-1}\sum_{i=0}^{j}\binom{n+1}{j+1}\binom{n}{i}\tag{5}\\ &=\sum_{j=0}^{n}\sum_{i=0}^{j}\binom{n+1}{j+1}\binom{n}{i}-2^n\tag{6}\\ \end{align*}

Comment:

• In (2) we replace $j\rightarrow n-j$

• In (3) we shift the index $i$ to start from $0$

• In (4) we use $\binom{n}{k}=\binom{n}{n-k}$ and we replace $i\rightarrow j-1-i$. We also note that $j$ starts with $j=1$ due to the upper index of $i$ equal to $j-1$.

• In (5) we shift the index $j$ by one.

• In (6) we add $j=n$ to the double sum and subtract $2^n$ accordingly.

We see, the double sum with the upper triangle as index range can be transformed to the double sum with the lower triangle as index range. Putting all together we obtain

\begin{align*} \sum_{j=0}^n&\sum_{i=0}^j\binom{n+1}{j+1}\binom{n}{i}+ \sum_{j=0}^n\sum_{i=j+1}^n\binom{n+1}{j+1}\binom{n}{i}\\ &=2\sum_{j=0}^n\sum_{i=0}^j\binom{n+1}{j+1}\binom{n}{i}-2^n \end{align*}

We obtain with (1)

\begin{align*} 2\sum_{j=0}^n\sum_{i=0}^j\binom{n+1}{j+1}\binom{n}{i}-2^n&=2\cdot 4^n-2^n\\ \end{align*}

resp.

\begin{align*} \sum_{j=0}^n\sum_{i=0}^j\binom{n+1}{j+1}\binom{n}{i}&=4^n\\ \end{align*}

and the claim follows.

• Good exploitation of symmetry and nice solution! (+1). – hypergeometric Feb 17 '16 at 15:23

The identity as shown in the question is correct.

\begin{align} \sum_{j=0}^n\sum_{i=0}^j\binom {n+1}{j+1}\binom ni &=\sum_{j=0}^n\sum_{i=0}^j\binom {n+1}{j+1}\binom n{n-i}\\ &=\sum_{j=0}^n\sum_{r=0}^j\binom {n+1}{j+1}\binom n{n+r-j} &&\text{(putting }r=j-i)\\ &=\sum_{r=0}^n\sum_{j=r}^n\binom {n+1}{j+1}\binom n{n+r-j} &&\text{(swapping order of indices)(}0\le r\le j\le n )\\ &=\sum_{r=0}^n\binom {2n+1}{n+1+r} &&\text{(Vandermonde)}\\ &\color{lightgrey}{=\frac 12 \sum_{r=0}^n\binom {2n+1}{n-r}+\binom {2n+1}{n+1+r}}\\ &\color{lightgrey}{=\frac 12 \sum_{r=0}^{2n+1} \binom {2n+1}r}\\ &=\frac 12 \cdot 2^{2n+1}\\ &=2^{2n}\qquad\blacksquare\end{align}

Another approach:

\begin{align} \sum_{j=0}^n\sum_{i=0}^j\binom {n+1}{j+1}\binom ni &=\sum_{j=0}^n\sum_{i=0}^j \left[\binom nj+\binom n{j+1}\right]\binom ni\\ &=\underbrace{\sum_{\large 0\le i\color{red}\le j\le n}\binom nj\binom ni}_*+\binom n{j+1}\binom ni\\ &=\overbrace{\sum_{\large 0\le i\color{red}= j\le n}\binom nj\binom ni+\sum_{\large 0\le i\color{red}<j\le n}\binom nj\binom ni}^*+\sum_{\large 0\le i\color{red}< j\le n}\binom nj\binom ni\\ &=\sum_{\large 0\le i\color{red}=j\le n}\binom nj\binom ni+2\sum_{\large 0\le i\color{red}< j\le n}\binom nj\binom ni\\ &=\sum_{\large 0\le i\color{red}=j\le n}\binom nj\binom ni+\sum_{\large 0\le i\color{red}\neq j\le n}\binom nj\binom ni&&\text{(by symmetry)}\\ &=\sum_{j=0}^n\sum_{i=0}^n\binom nj\binom ni&&\text{(**)}\\ &=\sum_{j=0}^n\binom nj\sum_{i=0}^n\binom ni\\\\ &=2^n\cdot 2^n\\\\ &=2^{2n}\qquad\blacksquare \end{align}

** as pointed out by Alex in a comment on the original question!

• Should further clarification be added? Comments welcome. – hypergeometric Feb 17 '16 at 15:15
• Time for upvote! :-) (+1) – Markus Scheuer Feb 17 '16 at 15:16
• @MarkusScheuer - Thanks for the encouragement! – hypergeometric Feb 17 '16 at 15:24

Define $$F_n:=\sum_{j=0}^n\sum_{i=0}^j\binom {n+1}{j+1}\binom ni$$where $n\ge0.$

Then keeping in mind the symmetry of binomial coefficients,\begin{align}F_n &=\sum_{j=0}^n\sum_{i=0}^j \left[\binom nj+\binom n{j+1}\right]\binom ni\\ &=\sum_{j=0}^n\sum_{i=0}^j \binom n{j}\binom ni + \sum_{j=0}^n\sum_{i=0}^{j+1} \binom n{j+1}\binom ni-\sum_{j=0}^n\binom n{j+1}^2\\ &=\sum_{j=0}^n\sum_{i=0}^j \binom n{j}\binom ni + \sum_{j=1}^n\sum_{i=0}^{j} \binom n{j}\binom ni-\sum_{j=1}^n\binom n{j}^2\\ &=2\sum_{j=0}^n\sum_{i=0}^j \binom n{j}\binom ni -\sum_{j=0}^n\binom n{j}^2\\ &=\left(\sum_{i=0}^n \binom ni\right)^2\\\\ &=2^{2n} \end{align} Q.E.D.