<s>[INST] 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
 [/INST] 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}$
</s>