12
$\begingroup$

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.

  • 0
    @Auf Your last paragraph is quite wrong. It seems you miscopied something and left an $x$ which then vanished.2011-04-30

2 Answers 2

7

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

7

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

  • 0
    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.2011-04-30