Combinatorial proof for $n\ge1$ of $3^n = \sum_{k=0}^n \binom{n}{k}(2^{n-k})$

Question

I know that we are supposed to look at strings with n entries such that each entry lies in {0,1,2} (a ternary string), but I'm not quite sure where to go from here!

Answer 1

Hint: Try counting the number of ways to sort $n$ people into $3$ groups, where each person must be in exactly one group, in two ways.

Subhint for the right hand side:

Try using casework based on the number of people in one of the groups.

Remark: This is the same as the argument you have in mind with strings. Each of the $n$ spots in the string represents a person, and each of $0,1,$ and $2$ represent the group that person would be in.

Answer 2

For the left-hand side, the multiplication principle yields $|\{0,1,2\}|^n=3^n$ strings. For the right-hand side, condition on the number $k$ of $0$s. There are $\binom{n}{k}$ choices of $k$ entries for the $0$s and $|\{1,2\}|^{n-k}=2^{n-k}$ choices for the remaining $n-k$ nonzero entries.

Answer 3

$(1+2)^n=\Sigma_{k=0}^{k=n}\binom{n}{k}2^{n-k}$ using the Binomial theorem expansion of $(1+x)^{n}$ using $x=2$.