4

I am trying to calculate the following using binomial coefficients and summation, but my memory is standing in the way:

$$ \sum_{k=1}^n {k} * 2 ^ {k - 1} $$

Thanks!

With great help I got to:

$$ (n - 1)* 2 ^{n} - 1 $$

Can you please confirm this?

flavian
  • 293
  • 2
  • 11

4 Answers4

5

Hint: switch to polynomial functions. $$ P(x)=\sum_{k=1}^n kx^{k-1} $$

Clement C.
  • 67,323
  • Integrate $P$, get a closed-form "nice" expression of its antiderivative, differentiate this expression to get a "nice" expression of $P$; use this to evaluate $P(2)$. – Clement C. May 12 '13 at 15:10
  • I find something different (namely, $(n-1)2^n+1$). To test whether your answer is right, do a sanity check by computing it for small values of $n$ (0, 1, 2 or even 3.) – Clement C. May 12 '13 at 15:30
3

Clement C's solution is the best approach. There is another approach, however.

Notice that $$ \sum_{k=1}^n k2^{k-1} = \sum_{k=1}^n \sum_{i=1}^k 2^{k-1} $$ because $k=\sum_{i=1}^k 1$. By reversing the order of summation, you get $$ \sum_{k=1}^n k2^{k-1} = \sum_{i=1}^n \sum_{k=i}^n 2^{k-1} $$ A closed form solution can now be found easily for the inner sum, which will produce a form that can be used to find a closed form solution for the outer sum.

Glen O
  • 12,425
1

Here is another approach, using $$ \sum_{k=0}^n\binom{n}{k}=2^n $$ and $$ \sum_{k=j}^n\binom{k}{j}=\binom{n+1}{j+1} $$ to get $$ \begin{align} \sum_{k=1}^nk\,2^{k-1} &=\sum_{k=1}^nk\,\sum_{j=0}^{k-1}\binom{k-1}{j}\\ &=\sum_{j=0}^{n-1}\sum_{k=j+1}^n(j+1)\binom{k}{j+1}\\ &=\sum_{j=0}^{n-1}(j+1)\binom{n+1}{j+2}\\ &=\sum_{j=1}^nj\binom{n+1}{j+1}\\ &=\sum_{j=1}^n(j+1)\binom{n+1}{j+1}-\binom{n+1}{j+1}\\ &=\sum_{j=1}^n(n+1)\binom{n}{j}-\binom{n+1}{j+1}\\ &=(n+1)(2^n-1)-(2^{n+1}-n-2)\\[12pt] &=(n-1)2^n+1 \end{align} $$

Verification

Of course, to verify, we can try induction.

The formula works for $n=1$: $1=1$.

Assume the formula works for $n-1$, then $$ \begin{align} \sum_{k=1}^nk\,2^{k-1} &=n\,2^{n-1}+\sum_{k=1}^{n-1}k\,2^{k-1}\\ &=n\,2^{n-1}+(n-2)2^{n-1}+1\\[9pt] &=(n-1)2^n+1 \end{align} $$ Thus, it is true for all $n\ge1$.

robjohn
  • 345,667
0

Here is another approch

∑k.2^(k-1)

Let f(x)=∑k.x^(k-1)

∫f(x) dx=∑∫k.x^(k-1)dx

∫f(x) dx=∑x^k

∫f(x)dx= x +x^2 + x^3 + …………………. X^n

∫f(x) dx= x(x^n-1)/(x-1)

Differentiating both sides

f(x)= ( nx^(n+1) –(n+1)x^n + 1)/(x-1)^2

put x=2 f(2)=(n-1)2^n +1

raman unni
  • 1