Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|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 :( –  proqwe 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
add comment

2 Answers

up vote 13 down vote accepted

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

share|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.