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?

Update

I placed the right calculations as an answer below.

Solution 1:

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

Solution 2:

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