# Evaluate the sum $\sum_{k=0}^n 2^k \cdot \binom{n}{k}$

Evaluate the sum $\sum_{k=0}^n 2^k \cdot \dbinom{n}{k}$

I think the problem calls for some application of Vandermonde's identity as the author previously proved this identity,however I can't see right away how to apply it.

Another thing of interest might be the idenity $\dbinom{n}{0} +\dbinom{n}{1} +\cdots +\dbinom{n}{n}=2^{n}$

Indeed,my first idea was to manipulate this last one in some way ,like:

$\dbinom{n}{0} +\dbinom{n}{1} +\cdots +\dbinom{n}{n}=2^{n}$

$2\left(\dbinom{n}{1} \dbinom{n}{2} +\cdots +\dbinom{n}{n}\right)=2^{n+1}-2$

and from this one I thought that if I could multiply each chain starting with $\dbinom{n}{2},\dbinom{n}{3},\dbinom{n}{n}$ by a power of $2$ and then add I would get something usefull but actually it's a pretty bad idea,I still get in the left hand side binomial coefficients....

Any hint to point me in the right route is appreciated.

• Binomial theorem? – Ron Gordon Jan 17 '16 at 19:00

Apply the binomial expansion of $(1+x)^n$ and substitute $x=2$.
By the binomial theorem, $$\sum_{k=0}^{n}\binom{n}{k}2^k = (2+1)^n = \color{red}{3^n}.\tag{1}$$
A combinatorial intepretation is the following: we are counting the functions from $\{1,2,3,\ldots,n\}$ to $\{0,1,2\}$ according to the inverse image of $\{0,1\}$: we select the elements that are mapped into $\{0,1\}$, for any of them we choose if the value of the function is $0$ or $1$, then we map the remaining elements into $2$.