How to find $\sum_{k=1}^n 2^kC(n,k)$?

How to find the sum of series, $$\sum_{k=1}^n 2^kC(n,k)$$

Solutions Collecting From Web of "How to find $\sum_{k=1}^n 2^kC(n,k)$?"

Substitute $x=2$ into the binomial expansion of $(1+x)^n$ and then rearrange.

While Jasper Loy’s answer is the canonical one, I thought folks might like to see a different one.

Suppose you are interested, for some function $f(k)$, in the binomial sum

$$B(n) = \sum_{k=0}^n \binom{n}{k} f(k).$$

Then, taking $\Delta f(k) = f(k+1) – f(k)$, denote $A(n)$ by

$$A(n) = \sum_{k=0}^n \binom{n}{k} \Delta f(k).$$

It’s fairly easy to prove that $B(n+1) – 2B(n) = A(n)$ with initial condition $B(0) = f(0)$. See, for example, Theorem 2 in my paper “Combinatorial Sums and Finite Differences,” Discrete Mathematics, 307 (24): 3130-3146, 2007.

In the OP’s question, $f(k) = 2^k$, and, of course, $\Delta f(k) = 2^k$ as well. So $A(n) = B(n)$, and thus the sum $B(n) = \sum_{k=0}^n \binom{n}{k} 2^k$ can be found by solving the simple recurrence $B(n+1) = 3B(n)$ with initial condition $B(0) = 1$.


Incidentally, this approach can also be used to prove the binomial theorem itself for nonnegative integer values of $n$. See Identity 1 in the paper.

For two more examples of using finite differences to evaluate binomial sums, see this answer and this answer to previous math.SE questions.