0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.