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

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