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

  • $\begingroup$ Is this a homework problem or an exam problem in progress? $\endgroup$ – TCL Jan 5 '11 at 18:26
  • $\begingroup$ No i came across this problem when solving another problem :( $\endgroup$ – amitkarmakar Jan 5 '11 at 18:28
  • $\begingroup$ This is most likely a dupe. We have had at least a dozen problems very similar to this. $\endgroup$ – Aryabhata Jan 5 '11 at 19:21

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

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

| cite | improve this answer | |

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.