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

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.

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