Prove the identity $\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} = 3^n$ Prove the identity $\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} = 3^n$. I believe I need to use the binomial theorem here, but I don't know how to deal with the double summations.
 A: We will use the identity
$$
\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}\quad (n\geq k\geq r\geq 0).
$$
Interchange the order of summation and use the identity above to get that
$$
\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k}
=\sum_{r=0}^{n}\binom{n}{r}\sum_{k=r}^{n}\binom{n-r}{k-r}=\sum_{r=0}^n\binom{n}{r}2^{n-r}=(1+2)^n=3^n 
$$
where we used the fact that
$$
\sum_{k=r}^{n}\binom{n-r}{k-r}=\sum_{u=0}^{n-r}\binom{n-r}{u}=2^{n-r}.
$$
A: You know that $\displaystyle(1+x)^n=\sum_{k=0}^n\binom nkx^k$
$\displaystyle\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} =\sum_{k=0}^{n}\binom{n}{k}\sum_{r=0}^{k} \binom{k}{r}=\sum_{k=0}^{n}\binom{n}{k}\sum_{r=0}^{k} \binom{k}{r}1^r$
Since $\displaystyle\sum_{r=0}^{k} \binom{k}{r}1^r=(1+1)^k=2^k$, we have
$\displaystyle\implies\sum_{k=0}^{n} \binom nk2^k=(1+2)^n=3^n$
A: Let $|X|=n$, so $3^n$ is the number of functions from $X$ to {$1,2,3$}. 
Each such function corresponds uniquely to a pair of subsets $(A,B)$ with $A$ a subset of $B$ and $B$ a subset of $X$ by taking $B$ = {$x$ | $f(x)=2$ or $f(x)=3$} and $A$ = {$x$ | $f(x)=2$}. 
The number of such pairs of nested subsets of $X$ is the double sum on the right hand side of the formula (where $k$ = $|B|$ and $r$ = $|A|$).
A: 
A convenient aspect is the index of the inner sum affects only one binomial coefficient. Setting parenthesis we might observe
\begin{align*}
\color{blue}{\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r}\binom{n}{k}}
&=\sum_{k=0}^{n}\left(\sum_{r=0}^{k} \binom{k}{r} \right)\binom{n}{k}\\
&=\sum_{k=0}^{n}2^k \binom{n}{k}\\
&\,\,\color{blue}{=3^n}
\end{align*}

