proof of summation using $\displaystyle \binom{n}{r}$

Question

Prove that $\sum_{r=0}^{n} \binom{n}{r}2^r = 3^n$ for $n \in \mathbb P$. "Hint: give me an argument having to do with the number of strings of length $n$ with $3$ symbols."

Answer 1

There is one way to do this using the expansion $(2+1)^n=3^n$. Then the sum of the terms will be the one in the left and the result will be the one at the right.

But I'll now give the answer involving the hint.

For example we want to form a string of $n$ beads using beads of $3$ colors. Then there are $3^n$ ways. We will now count it in another way. Consider the first color. Then count the number of ways that it is possible to be done using $n-k$ copies of that first color bead. It will be nCk*2^k. $(nC(n-k)=nCk$ to determine the locations and then $2^k$ to decide between the other 2 colors for the other $k$ beads.

Answer 2

Hint: use the binomial expansion of (x+y)^n

Answer 3

This is a straightforward application of the formula: $(a+b)^n = \displaystyle \sum_{r=0}^n \binom{n}{r}a^rb^{n-r}$. Put $a = 2, b = 1$ to get the answer.

Answer 4

An argument like the one hinted at would be something with the binomial coefficient describing the number of ways to choose $r$ places for ...