Why does $\sum\limits_{i=0}^{100} \binom{100}{i} \sum\limits_{j=i+1}^{101}\binom{101}{j}$ equal $2^{200}$? According to WolframAlpha, the following is true:
$$\sum_{i=0}^{100} \frac{ \binom{100}{i} }{2^{100}}\sum_{j=i+1}^{101}\frac{ \binom{101}{j} }{2^{101}} = \frac{1}{2}$$
Can anyone tell me why that is?
I'm quessing it has something to do with the hypergeometric function.
 A: $$
\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
A: $$\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. $$
A: 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.
A: Note that 
$\displaystyle \binom ni\binom {n+1}j=\binom n{n-i}\binom {n+1}{n+1-j}$.
Hence
$$\begin{align}
&\sum_{i=0}^n\binom ni\sum_{j=i+1}^{n+1}\binom {n+1}j\\
&=\sum_{i=0}^n\sum_{j=i+1}^{n+1}\binom ni\binom {n+1}j\\
&=\frac 12\left[\sum_{i=0}^n\sum_{j=i+1}^{n+1}\binom ni\binom {n+1}j+\binom n{n-i}\binom {n+1}{n+1-j}\right]\\
&=\frac 12\left[\sum_{i=0}^n\sum_{j=i+1}^{n+1}\binom ni\binom {n+1}j+\sum_{r=0}^n\sum_{s=0}^r \binom nr\binom {n+1}s\right]
&&\scriptsize r=n-i;\atop \scriptsize s=n+1-j\\
&=\frac 12\left[\sum_{i=0}^n\sum_{j=i+1}^{n+1}\binom ni\binom {n+1}j+\sum_{i=0}^n\sum_{j=0}^i \binom ni\binom {n+1}j\right]\\
&=\frac 12\sum_{i=0}^n\sum_{j=0}^{n+1}\binom ni\binom {n+1}j\\
&=\frac 12\sum_{i=0}^n \binom ni\sum_{j=0}^{n+1}\binom {n+1}j\\
&=\frac 12\cdot 2^n\cdot 2^{n+1}\\
&=\color{red}{2^{2n}}
\end{align}$$
Putting $n=100$ gives the proof required.
A: Here's a simple combinatorial argument.  Note that $\sum_{i=0}^{100} \binom{100}{i} \sum_{j=i+1}^{101}\binom{101}{j}$ is the cardinality of the set $S$ of pairs $(A,B)$ where $A\subseteq\{1,\dots,100\}$, $B\subseteq\{1,\dots,101\}$, and $|A|<|B|$ (here $i$ corresponds to $|A|$ and $j$ corresponds to $|B|$).  On the other hand, $2^{200}$ is the cardinality of the set $T$ of pairs $(C,D)$ where $C,D\subseteq\{1,\dots,100\}$.
We define a bijection $f:T\to S$ as follows.  If $|C|<|D|$, then we define $f(C,D)=(C,D)$.  If $|C|\geq |D|$, we define $f(C,D)=(D,C\cup\{101\})$.  It is easy to verify that this is a bijection, with inverse $g(A,B)=(A,B)$ if $101\not\in B$ and $g(A,B)=(B\setminus\{101\},A)$ if $101\in B$.
