Why does this sum equal to (4^n -1)

Question

How do I get to this solution?

$\sum _{k=1}^n\left(\binom nk 3^{n-k}\right)=\left(4^n-1\right)$

I believe it's connected to this, which I know is true:

$\sum \:_{k=1}^n\binom nk=2^n-1$

Answer 1

(Notice that the identity as stated is not correct.)

Suppose we want to form an n-letter word using the letters A,B,C,D

and we want to have at least one A in our word.

If we have $k$ A's in our word, where $1\le k\le n$, then we can choose the places for the A's in $\binom{n}{k}$ ways and we can fill the remaining places in $3^{n-k}$ ways. Therefore there are $\displaystyle \sum_{k=1}^{n}\binom{n}{k}3^{n-k}$ such words.

On the other hand, there are $4^n$ total words, and $3^n$ of these do not use an A, so there are $4^n-3^n$ such words and hence $\displaystyle \sum_{k=1}^{n}\binom{n}{k}3^{n-k}=4^n-3^n$.

---

Alternatively, the Binomial Formula yields $\displaystyle(1+3)^n=\sum_{k=0}^{n}\binom{n}{k}1^k3^{n-k}$, so

$\displaystyle 4^n=\binom{n}{0}3^n+\sum_{k=1}^{n}\binom{n}{k}3^{n-k}\implies \sum_{k=1}^{n}\binom{n}{k}3^{n-k}=4^n-3^n$.

Answer 2

By the Binomial Theorem

$$4^n=(3+1)^n= \sum_{k=0}^n \binom{n}{k} 3^k=1+ \sum_{k=1}^n \binom{n}{k} 3^k$$