Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Is this a homework problem or an exam problem in progress? – TCL Jan 5 '11 at 18:26
No i came across this problem when solving another problem :( – amit.codename13 Jan 5 '11 at 18:28
This is most likely a dupe. We have had at least a dozen problems very similar to this. – Aryabhata Jan 5 '11 at 19:21
up vote 13 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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