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

I want to evaluate this sum $$\sum_{k=0}^{n}k^{2}2^{k}$$ by summation by parts (two times) and I need to know, if my approach was right.

I know the formula for summation by parts is $$\sum u\Delta v=uv-\sum\left(Ev\right)\Delta u$$ where $E\left(v\left(x\right)\right)=v\left(x+1\right)$ and $(v(x))=v(x+1)-vx)$.

Further if $f$ is a Antiderivative of $g$ I know the formula $$\sum_{k=a}^{b}g\left(k\right)=f\left(b+1\right)-f\left(a\right)$$

First I choose $u=x^{2}$. This means $\Delta u=\Delta x^{2}=2x+1$. Choose $v=2^{x}$. That means $\Delta v=2^{x}$. Then I get

$$\begin{eqnarray*} \sum_{k=0}^{n}k^{2}2^{k} &=& \sum_{0}^{n+1}x^{2}2^{x} \\ &=& \left.x^{2}*2^{x}\right|_{0}^{n+1}-\sum_{0}^{n+1}2^{x+1}(2x+1) \\ &=& (n+1)^2 2^{n+1}-\sum_{0}^{n+1}2x2^{x+1}+2^{x+1} \\ &=& (n+1)^2 2^{n+1}-4\sum_{0}^{n+1}x2^{x} - 2\sum_{0}^{n+1}2^{x} \end{eqnarray*}$$

Now choose $u(x)=x$. This means $\Delta u=\Delta x=1$. Chose $v=2^{x}$. This means $\Delta v=2^{x}$ and $E(v(x))=2^{x+1}$. I get then

$$\begin{eqnarray*} \sum_{x=0}^{n+1}x2^{x+1} &=& \left[x2^{x}-2^{x+1}\right]_{0}^{n+1} \\ &=& ((n+1)-1)2^{(n+1)+1}+2 \\ &=& n2^{n+2}+2 \end{eqnarray*}$$

Putting those two calculations together resolves in $$\begin{eqnarray*} \sum_{k=0}^{n}k^{2}2^{k} &=&(n+1)^2 2^{n+1}-2\sum_{0}^{n+1}x2^{x+1} - \sum_{0}^{n+1}2^{x+1} \\ &=& (n+1)^2 2^{n+1}-2(n2^{n+2}+2) - (n+2)2^{x} \\ &=& 2^{n+1}(n^2+2n+1) -4(n2^{n+2}+2) - 2(n+2)2^{x} \\ &=& 2^{n+1}(n^2+2n+1-8n-(n+2))-8 \\ &=& 2^{n+1}(n^2-7n-1)-8 \\ \end{eqnarray*}$$

But Mathematica says $$2^{n+1} ((n-2) n+3)-6 = 2^{n+1} (n^2-2n+3)-6$$ Where is my fault?


I placed the right calculations as an answer below.

share|cite|improve this question
To format $$\begin{eqnarray*} \sum_{k=0}^{n}k^{2}2^{k} &=&2(n+1)2^{n+1}-\left( 2^{n+4}-2^{n+5}\right) =2(n+1)2^{n+1}-2^{n+4}+2^{n+5} \\ &=&2^{n+2}+2^{n+3}-2^{n+4}+2^{n+5} \end{eqnarray*}$$ you can use blacklash begin{eqnarray*} \sum_{k=0}^{n}k^{2}2^{k} &=&2(n+1)2^{n+1}-\left( 2^{n+4}-2^{n+5}\right) =2(n+1)2^{n+1}-2^{n+4}+2^{n+5} \\ &=&2^{n+2}+2^{n+3}-2^{n+4}+2^{n+5} \end{eqnarray*} – Américo Tavares Apr 30 '11 at 10:39
$2(n+1)2^{n+1}\neq 2^{n+2}+2^{n+3}$ – Américo Tavares Apr 30 '11 at 10:42
If I may start by saying "I want to solve this equation..." but an equation is something with an equals sign in it, which you don't have. Rather, "I want to evaluate this sum..." – Gerry Myerson Apr 30 '11 at 11:22
@Gerry: You are right. I corrected that. If a "nitpick" serves me to learn something new - which I appreciate every time - I am absolutely ok, with that! ;-) – Aufwind Apr 30 '11 at 11:41
+1 for trying on your own and showing what you have done. Maybe it will be a lesson to others that you got a specific answer (but I suspect not). – Ross Millikan Apr 30 '11 at 14:51

You wrongly calculated the difference of $x^2$. Plug it directly into the definition.

(And you can always check your calculation by looking at small values of $n$. In particular, you should have 0 for $n=0$. To locate the error, "binary search" is advisable: Put $n=0$ somewhere in the middle to see if the error was in the first half or the second half, etc.)

share|cite|improve this answer
I see, thanks. Of course it should be: $\Delta x^2 = (x+1)^{2}-x^{2}=x^{2}+2x+1-x^{2}=2x+1$. I'll edit it right now. – Aufwind Apr 30 '11 at 11:58
up vote 7 down vote accepted

I calculated it again by pen and paper after letting a little time passing. And I got it! I made some basic mistakes, which I am ashamed of now, that I see them. But you learn by any *kind* of mistakes, don't ya? ;-)

Here the correct calculation:

First I calculated

\begin{equation*} \sum_{k=0}^{n} k 2^{k} \end{equation*}

by summation by parts. I chose $x=u$ and $\Delta 2^x=v$. This gave me $\Delta x=1$ and $v=2^x$. I see the descrete integration of $2^x$ behaves like the analytical integration of $e^x$. (I hope the vocabular I used here is correct, English is not my native language. :-))

$$ \begin{eqnarray*} \sum_{k=0}^{n} k 2^{k} &=& \sum_{0}^{n+1}x2^{x} \\ &=& \left[x2^{x}\right]_{0}^{n+1}-\sum_{0}^{n+1}2^{x+1}\cdot 1 \\ &=& \left(n+1\right)2^{n+1}-2\sum_{0}^{n+1}2^{x} \\ &=& \left(n+1\right)2^{n+1}-2\left(2^{n+1}-1\right) \\ &=& n2^{n+1}+2^{n+1}-2\cdot2^{n+1}+2 \\ &=& n2^{n+1}-2^{n+1}+2 \\ &=& 2^{n+1}\left(n-1\right)+2 \end{eqnarray*} $$ Now I can evaluate

\begin{equation*} \sum_{k=0}^{n} k^2 2^{k} \end{equation*}

For that I chose $x^2=u$ and $\Delta 2^x=v$. This gave me $\Delta x=2x+1$ and $v=2^x$. Now summation by parts and some basic calculations yields

$$ \begin{eqnarray*} \sum_{k=0}^{n}k^{2}2^{k} &=& \sum_{0}^{n+1}x^{2}2^{x} \\ &=& \left[x^{2}2^{x}\right]_{0}^{n+1}-\sum_{0}^{n+1}2^{x+1}\left(2x+1\right) \\ &=& \left(n+1\right)^{2}2^{n+1}-\left(\sum_{0}^{n+1}2x2^{x+1}+2^{x+1}\right) \\ &=& \left(n^{2}+2n+1\right)2^{n+1}-\left(4\sum_{0}^{n+1}x2^{x}+2\sum_{0}^{n+1}2^{x}\right)\\ &=& \left(n^{2}+2n+1\right)2^{n+1}-\left(4\left(\left(n-1\right)2^{n+1}+2\right)+2\left[2^{x}\right]_{0}^{n+1}\right) \\ &=& \left(n^{2}+2n+1\right)2^{n+1}-\left(4\left(\left(n-1\right)2^{n+1}+2\right)+2\left(2^{n+1}-1\right)\right) \\ &=& \left(n^{2}+2n+1\right)2^{n+1}-\left(4\left(\left(n2^{n+1}-2^{n+1}\right)+2\right)+2\cdot2^{n+1}-2\right) \\ &=& \left(n^{2}+2n+1\right)2^{n+1}-\left(4\left(n2^{n+1}-2^{n+1}\right)+8+2\cdot2^{n+1}-2\right) \\ &=& \left(n^{2}+2n+1\right)2^{n+1}-\left(4n2^{n+1}-42^{n+1}+8+2\cdot2^{n+1}-2\right) \\ &=& \left(n^{2}+2n+1\right)2^{n+1}-4n2^{n+1}+42^{n+1}-8-2\cdot2^{n+1}+2 \\ &=& 2^{n+1}\left(\left(n^{2}+2n+1\right)-4n+4-2\right)-8+2 \\ &=& 2^{n+1}\left(n^{2}-2n+3\right)-6 \\ &=& 2^{n+1}\left((n-2)n+3\right)-6 \end{eqnarray*} $$

which is exacly what WolframAlpha proclaims. Thanks to anyone who suggested corrections. :-)

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.