6
$\begingroup$

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}^{+}$

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

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.

$\endgroup$
2
$\begingroup$

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.

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

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!

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.