Provide a combinatorial argument to prove

Question

$$1+\binom{n}{1}2+\binom{n}{2}4 +...+ \binom{n}{n-1}2^{n-1} + \binom{n}{n}2^n=3^n$$

Im sorry, for some reason its not writing the equation properly but 2^(n-1) should be in the exponent

Answer 1

HINT: $3^n$ is the number of ways to distribute the numbers $1,2,\ldots,n$ amongst boxes labelled $A,B$, and $C$. And the lefthand side can be written

$$\sum_{k=0}^n\binom{n}k2^k=\sum_{k=0}^n\binom{n}{n-k}2^k=\sum_{\ell=0}^n\binom{n}\ell2^{n-\ell}\;,$$

where $\ell=n-k$.

Find a way to interpret the term $\binom{n}\ell2^{n-\ell}$ as counting a certain subset of the distributions of the numbers $1,2,\ldots,n$ amongst boxes labelled $A,B$, and $C$.

Answer 2

Try to count the number of strings in $\{0,1,2\}^n$. Proceed by the number of $0$s in the string. If there the number of $0$s is $k$, then there are $\binom{n}{n-k}$ options on where to place the nonzero entries, each of which can be either $1$ or $2$. Thus the total number with is $\binom{n}{n-k} 2^{n-k}$, for each $k$. Sum over all $k$ to get your identity. This number must be equal to $3^n$.

Answer 3

Here is a combinatorial proof using the following:

Given $n$ numbered balls, how many ways are there to paint them all in red, green and blue?

The right-hand side clearly counts the number of ways this can be done. The left-hand side also does this, but only after some analysing:

First, choose a $k \in \{0,1,\ldots,n-1,n\}$, and then pick $k$ balls. This can be done in $\bibnom nk$ ways. Now, for each of the chosen balls, paint it either green or red. This can be done in $2^k$ ways. Paint all the $n-k$ balls blue. This gives $$ \underbrace{1}_{k = 0} + \underbrace{\binom{n}22^1}_{k = 1} + \cdots + \underbrace{\binom nn2^n}_{k = n} $$ Since these two count the same thing, the numbers must be equal.