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?
 A: $$
\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).
A: See robjohn's answer for the problem in your attempt.
However, a good way to start these problems is to stop and think what the sum actually represents. $\binom ni\binom ij$ is the number of ways to choose a committee of $i$ people out of $n$, and then a subcommittee of $j$ people from those $i$. If you sum this over all possible values $i\geq j$ you get the number of ways to divide $n$ people into three groups (those on the subcommittee, those on the main committee only, those on neither) with groups allowed to be any size (including empty). What is a simpler way to calculate that?
A: Change the order of summation (overall there are only finitely many summands). For that note that
\begin{align*}
M:&=\{ (i,j)\in\mathbb{N}^2~:~j=0,...,n~~i=j,...,n\}\\
 &= \{(i,j)\in \mathbb{N}^2~:~i=0,...,n~~j=0,...,i\}.
\end{align*}
Therefore we can change the representation of $M$ and obtain
\begin{align*}
\sum_{j=0}^n \sum_{i=j}^n {n\choose i}{i\choose j} &= \sum_{(i,j)\in M} {n \choose i}{i \choose j}= \sum_{i=0}^n \sum_{j=0}^i {n \choose i}{i \choose j}\\
&=  \sum_{i=0}^n {n \choose i} \sum_{j=0}^i {i\choose j} = \sum_{i=0}^n {n\choose i} 2^i = (1+2)^n = 3^n.
\end{align*}
