I have a hard time showing that that

$$ \frac{1}{2^{2n+1}}\sum_{i=0}^n \left[\binom{n}{i} \cdot \sum_{j=i+1}^{n+1} \binom{n+1}{j} \right]= \frac{1}{2}$$

Namely, I try to show hat

$$\sum_{i=0}^n \left[\binom{n}{i} \cdot \sum_{j=i+1}^{n+1} \binom{n+1}{j}\right] = 2^{2n} $$

Any help would be appreciated. Thank you all.

Online demo: https://www.desmos.com/calculator/cjo7zggjlf

  • 1
    $\begingroup$ What is $k$? Are you sure you copied the problem correctly? Even if you replace $k$ with $i$ you don't get equality. $\endgroup$
    – Matthew H.
    Jan 3 at 0:36
  • $\begingroup$ Thanks for pointing it out. I edited it. It is index "i". $\endgroup$
    – Gavin
    Jan 3 at 0:39
  • $\begingroup$ I just updated the question in case there were typos. If you still think the equality doesn't hold, could you briefly explain why or give a counterexample for n? I range n from 1 to 100 as a sanity check. It seems like the equality holds. $\endgroup$
    – Gavin
    Jan 3 at 0:51
  • $\begingroup$ Hah, thanks again! I was so negligent when translating code to latex. "i" range from 0 to n $\endgroup$
    – Gavin
    Jan 3 at 0:58
  • $\begingroup$ I'm still not getting equality, even if you change the lower index of $i$ to $0$. Check here: desmos.com/calculator/4ddioz2ztg $\endgroup$
    – Matthew H.
    Jan 3 at 0:59

2 Answers 2


We have $$ \begin{split} S=\sum_{0\le i<j\le n+1}\binom{n}{i}\binom{n+1}{j}&=\sum_{0\le i\le n}\sum_{0\le j\le n+1}\binom{n}{i}\binom{n+1}{j}-\sum_{0\le j\le i\le n+1}\binom{n}{i}\binom{n+1}{j}\\ &=2^n\cdot 2^{n+1}-\sum_{0\le j\le i\le n+1}\binom{n}{n-i}\binom{n+1}{n-j+1}\\ &=2^{2n+1}-\sum_{0\le i'<j'\le n+1}\binom{n}{i'}\binom{n+1}{j'}\\ &=2^{2n+1}-S, \end{split} $$ where $i'=n-i$ and $j'=n-j+1$. Therefore, $2S=2^{2n+1}$, i.e. $S=2^{2n}$.


We will show that $\sum_{i=0}^n \left[\binom{n}{i} \cdot \sum_{j=i+1}^{n+1} \binom{n+1}{j} \right]=4^n$

Note that $\sum_{j=i+1}^{n+1}\binom{n+1}{j}=\sum_{j=0}^{n-i}\binom{n+1}{j}$.

Now consider the power series $(1+x)^{n+1}=\binom{n+1}{0}+\binom{n+1}{1}x+\binom{n+1}{2}x^2+\ldots+\binom{n+1}{n+1}x^{n+1}$. We have that the partial sum $\sum_{j=0}^{n-i}\binom{n+1}{j}$ is the coefficient of $x^{n-i}$ in $\frac{(1+x)^{n+1}}{1-x}$.

Now going back to our original sum, we can extend the index to infinity to get that this is equivalent to $$\sum_{i=0}^\infty \binom{n}{i}\sum_{j=i+1}^{n+1} \binom{n+1}{j}$$ Since $\binom{n}{i}$ is the coefficient of $x^i$ in $(1+x)^n$ and $\sum_{j=i+1}^{n+1} \binom{n+1}{j}$ is the coefficient of $x^{n-i}$ in $\frac{(1+x)^{n+1}}{1-x}$, this cauchy product is the coefficient of $x^n$ in $$\frac{(1+x)^{2n+1}}{1-x}$$ which is $$\sum_{i=0}^n \binom{2n+1}{i}$$ We can easily verify that this is just half of $\sum_{i=0}^{2n+1}\binom{2n+1}{i}=2^{2n+1}$, which is $2^{2n}=\boxed{4^n}$


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.