<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 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}$.
</s>