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
 A: 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}$.
A: 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}$
