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.

  • 1
    $\begingroup$ Binomial theorem? $\endgroup$ – Ron Gordon Jan 17 '16 at 19:00

Apply the binomial expansion of $(1+x)^n$ and substitute $x=2$.

  • $\begingroup$ I lack such strokes of genius,thank you. $\endgroup$ – Mr. Y Jan 17 '16 at 19:01
  • 4
    $\begingroup$ @Mr.Y not genius, experience. $\endgroup$ – Henno Brandsma Jan 17 '16 at 19:02

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.