How do I prove $\sum_{k=0}^{n}\binom{n}{k}\cdot 2^k = 3^n$?

Question

What's the proof of $\sum_{k=0}^{n}\binom{n}{k}\cdot 2^k = 3^n$?

Answer 1

Binomial expansion for $(1+x)^n$ is: $$ (1+x)^n = \sum_{k=0}^{n} {n\choose k} (1)^{n-k}(x)^k $$ Substitute $x=2$, to get: $$ (1+2)^n = \sum_{k=0}^{n}{n\choose k}(1)^{n-k}(2)^k $$ But $1^{n-k} = 1$ for all values.
Thus, $$ (3)^n = \sum_{k=0}^{n}{n\choose k}(2)^k $$ Hence proved

Answer 2

Hint: $3^n=(2+1)^n$.

Now expand this binomial.

Answer 3

This is two ways of counting the faces of an $n$-dimensional cube $[0,1]^n$.

The left hand side is counting the faces by dimension. There are $\binom{n}{k}2^k$ faces of dimension $n-k$. You choose $k$ coordinates to fix, and then for each one you choose either $0$ or $1$ as its fixed value, letting the other $n-k$ coordinates vary freely.

The right hand side is counting the faces all at once by saying the projection onto each of the $n$ coordinates is either $\{0\}, \{1\},$ or $[0,1]$ and all possibilities occur.

Answer 4

Consider the number of ternary sequences of length $n$ over the alphabet $a, b, c$. There are $3^n$ such sequences. Now partition the set of ternary sequences into sets $A_k$ where $A_k$ is the set of sequences where the number of a's is $k$. Then $|A_k|=\binom{n}{k}2^{n-k}$. Hence $$ \sum_{k=0}^n\binom{n}{k}2^{n-k}=3^n $$ Make the indexing change $k\to n-k$ in the sum on the LHS to yield the result.