Why does $\sum\limits_{i=0}^{100} \binom{100}{i} \sum\limits_{j=i+1}^{101}\binom{101}{j}$ equal $2^{200}$?
$$
\begin{align}
\sum_{i=0}^{100}\binom{100}{i}\sum_{j=i+1}^{101}\binom{101}{j}
&=\sum_{j\gt i}\binom{100}{i}\binom{101}{j}\tag1\\
&=\sum_{j\gt i}\binom{100}{i}\binom{100}{j}+\sum_{j\ge i}\binom{100}{i}\binom{100}{j}\tag2\\
&=\sum_{j\gt i}\binom{100}{i}\binom{100}{j}+\sum_{j\le i}\binom{100}{i}\binom{100}{j}\tag3\\
&=\sum_{i,j}\binom{100}{i}\binom{100}{j}\tag4\\
&=\sum_{i=0}^{100}\binom{100}{i}\sum_{j=0}^{100}\binom{100}{j}\tag{5}\\[6pt]
&=2^{100}\cdot2^{100}\tag6
\end{align}
$$
Explanation:
$(1)$: write product as a single sum
$(2)$: $\binom{101}{j}=\binom{100}{j}+\binom{100}{j-1}$
$(3)$: switch $i$ and $j$ due to symmetry
$(4)$: combine sums
$(5)$: write as product of two sums
$(6)$: evaluate sums
$$\sum_{i=0}^{100}\binom{100}{i}\sum_{j=i+1}^{101}\binom{101}{j}\stackrel{j\mapsto 101-j}{=}\sum_{i=0}^{100}\binom{100}{i}\sum_{j=0}^{100-i}\binom{101}{j} $$ and by using $[x^k]\,f(x)$ for denoting the coefficient of $x^k$ in the Taylor series of $f(x)$ at the origin, the RHS equals
$$ \sum_{i=0}^{100}\binom{100}{i} [x^{100-i}]\frac{(1+x)^{101}}{1-x}=\sum_{i=0}^{100}[x^i](1+x)^{100}\cdot [x^{100-i}]\frac{(1+x)^{101}}{1-x} $$ which is just the coefficient of $x^{100}$ in $f(x)=\frac{(1+x)^{201}}{1-x}$, i.e. $$ \sum_{k=0}^{100}\binom{201}{k}\stackrel{\text{symmetry}}{=}\frac{1}{2}\sum_{k=0}^{201}\binom{201}{k} = \frac{2^{201}}{2}\stackrel{\color{green}{\checkmark}}{=}2^{200}.$$
Besides $\binom{n}{k}=\binom{n}{n-k}$, I have used the following wel-known fact: $$\text{if}\quad g(x)=a_0+a_1 x+a_2x^2+a_3 x^3+\ldots $$ $$\text{then}\quad\frac{g(x)}{1-x}=A_0+A_1 x+ A_2 x^2+A_3 x^3+\ldots\quad\text{where}\quad A_m = \sum_{k=0}^{m}a_k. $$
The OP asks:
Can anyone tell me why that is?
An approach with almost zero computation, which yields a clear explanation of the result, starts by noting that the sum to be computed is $P(A_n)$ for $n=100$, with $$A_n=[S_n<T_{n+1}]$$ where $S_n$ is binomial $(n,\frac12)$, $T_{n+1}$ is binomial $(n+1,\frac12)$, and $S_n$ and $T_{n+1}$ are independent. Then, we make use of the two following elementary facts:
- $T_{n+1}=T_n+R$ where $R$ is Bernoulli independent of $(S_n,T_n)$, with $P(R=0)=P(R=1)=\frac12$.
- $[S_n<T_{n+1}]=[S_n<T_n]\cup[S_n=T_n,R=1]$
Thus, $$P(A_n)=P(S_n<T_n)+P(S_n=T_n,R=1)=P(S_n<T_n)+\tfrac12P(S_n=T_n)$$ By symmetry, $P(S_n<T_n)=P(S_n>T_n)$ hence $$2P(A_n)=P(S_n<T_n)+P(S_n=T_n)+P(S_n>T_n)=1$$ hence, irrespectively of the value of $n$,
$$P(A_n)=\tfrac12$$
that is, $$\sum_{i=0}^n\binom{n}{i}\sum_{j=i+1}^{n+1}\binom{n+1}{j}=2^{2n}$$
Edit: An even shorter proof starts with the fact that $$(S_n,T_{n+1})=^d(n-S_n,n+1-T_{n+1})$$ hence $P(A_n)=P(B_n)$ with $$B_n=[n-S_n<n+1-T_{n+1}]=[T_{n+1}<S_n+1]=[T_{n+1}\leqslant S_n]=(A_n)^c$$ hence $P(B_n)=1-P(A_n)$ and we are done.