# 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.

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}.$$

• Do you know a combinatorial proof of the statement? – mathpadawan Dec 8 '18 at 20:33
• @mathnoob I think I have a combinatorial argument, see my answer below. – Ned Dec 8 '18 at 21:18
• That's cool! Thanks! – mathpadawan Dec 8 '18 at 21:22

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|$$).

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 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*}