How to prove the double sum of combinations is $3^n$

Question

I have a double sum of combinations as follow $$S = \sum_{i=0}^{n}\sum_{k=i}^{n}{n \choose k}{k \choose i}.$$

I guessed and tested that $S = 3^n$, but I have no idea how to prove this. Any help is appreciated.

Answer 1

Consider $n$ distinguishable balls which we wish to colour one of three colours, and count the number of ways to do so. One way is as follows: we first choose $k$ to colour blue or green, everything else is coloured red. We then choose $i$ of these $k$ to colour blue, and the others are coloured green. This gives $S$ possible colourings.

But clearly the number of colourings is also $3^n$ because each ball can independently take one of $3$ colours; thus the two are equal as required.

Answer 2

Using the binomial theorem $\displaystyle \sum_{k=0}^{n}{n \choose k}x^k=(1+x)^n$.

\begin{align*} \sum_{i=0}^{n}\sum_{k=i}^{n}{n \choose k}{k \choose i}&=\sum_{k=0}^{n}\sum_{i=0}^{k}{n \choose k}{k \choose i}\\ &=\sum_{k=0}^{n}{n \choose k}\sum_{i=0}^{k}{k \choose i}1^i\\ &=\sum_{k=0}^{n}{n \choose k}(1+1)^k\\ &=\sum_{k=0}^{n}{n \choose k}2^k\\ &=(1+2)^n\\ &=3^n \end{align*}

Answer 3

Let us denote the sum by $S$ and use the property that $${n \choose k}{k\choose i}={n \choose i}{n-i \choose k-i}.$$ Then $$S=\sum_{i=0}^{n} {n \choose i} \sum_{k=i}^{n} {n-i \choose k-i}=\sum_{i=0}^n \sum_{p=0}^{n-i} {n-i \choose p}= \sum_{i=0}^n 2^{n-i}=2^n \sum_{i=0}^n 2^{-i}=2^n(1+1/2)^n=3^n. $$