# Show 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}$

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

• What is $k$? Are you sure you copied the problem correctly? Even if you replace $k$ with $i$ you don't get equality. Jan 3 at 0:36
• Thanks for pointing it out. I edited it. It is index "i". Jan 3 at 0:39
• 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. Jan 3 at 0:51
• Hah, thanks again! I was so negligent when translating code to latex. "i" range from 0 to n Jan 3 at 0:58
• I'm still not getting equality, even if you change the lower index of $i$ to $0$. Check here: desmos.com/calculator/4ddioz2ztg Jan 3 at 0:59

We have $$\begin{split} S=\sum_{0\le i 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}$$