Find $\sum_{j=0}^{n}\sum_{i=j}^{n} {n \choose i}{i \choose j}$. Find $\sum_{j=0}^{n}\sum_{i=j}^{n} {n \choose i}{i \choose j}$.
I don't know how to double summations like this very well. Can someone expand this to show how the $i=j$ thing works?
I tried the following:
${n \choose i}{i \choose j}={n \choose j}{n-j \choose i-j}$
$\sum_{j=0}^{n}\sum_{i=j}^{n} {n \choose i}{i \choose j}=\sum_{j=0}^{n}\sum_{i=j}^{n} {n \choose j}{n-j \choose i-j}=\sum_{j=0}^{n} {n \choose j}{n-j \choose 0}=2^n$
Where am I going wrong?

$$
\begin{align}
\sum\limits_{i=j}^n\binom{n-j}{i-j}
&=\sum\limits_{i=0}^{n-j}\binom{n-j}{i}\tag1\\[3pt]
&=2^{n-j}\tag2
\end{align}
$$
Explanation:
$(1)$: subsitute $i\mapsto i+j$
$(2)$: evaluate $(1+1)^{n-j}$ with the Binomial Theorem
If step $(1)$ is confusing, break it into two steps:

*

*$i\mapsto k+j$: since $i$ ranges from $j$ to $n$, $k=i-j$ ranges from $0$ to $n-j$

*$k\mapsto i$: simply change the variable of summation back

Thus, this sum is $2^{n-j}$, not $\binom{n-j}{0}$.
Now, the rest is evaluating either
$$
2^n\sum_{j=0}^n\color{#C00}{\binom{n}{j}}2^{-j}=2^n\left(1+2^{-1}\right)^n\tag{3a}
$$
or
$$
\sum_{j=0}^n\color{#C00}{\binom{n}{n-j}}2^{n-j}=(1+2)^n\tag{3b}
$$
with the Binomial Theorem (the parts in red are equal).
