How could I find the partial sum of this function?

Question

$$\displaystyle\sum_{k = 0}^{n}\dfrac{k^2}{2^k}$$

What are the steps to finding the partial sum formula?

Answer 1

Let $$S(x)=1^2 x+2^2x^2+3^2x^3+\cdots +n^2x^n.$$ Then $$\frac{S(x)}{x}=1^2 +2^2 x +3^2 x^2 +\cdots +n^2 x^{n-1}.$$

Note that $\frac{S(x)}{x}$ is the derivative of $T(x)$, where $$T(x)=x+2x^2+3x^3+\cdots +nx^n.$$ We have $$\frac{T(x)}{x}=1+2x+3x^2+\cdots +nx^{n-1}.$$ Note that $\frac{T(x)}{x}$ is the derivative of $1+x+x^2+x^3+\cdots +x^n$. And this sum is $\frac{1-x^{n+1}}{1-x}$.

Now work backwards. Find the derivative of $\frac{1-x^{n+1}}{1-x}$. Multiply by $x$ to get $T(x)$. Differentiate. That gives us $\frac{S(x)}{x}$. Multiply by $x$ to get $S(x)$. Finally, put $x=\frac{1}{2}$.

Remark: If calculus is unfamiliar, there are simpler ways! But the calculation above is a useful technique.

Answer 2

There are several ways. One way is to use the recursive formula for $\displaystyle S_n = \sum_{k=0}^n \dfrac{k^2}{2^k}$. The recursive formula is obviously $S_{n+1} = S_n + \dfrac{(n+1)^2}{2^{n+1}}$. There are many ways to get a closed form for a series given a recursive formula.

Answer 3

Let $S = \displaystyle\sum_{k = 0}^{n}\dfrac{k^2}{2^k}$.

Multiply by $\dfrac{1}{2}$ and shift indices: $\dfrac{1}{2}S = \displaystyle\sum_{k = 0}^{n}\dfrac{k^2}{2^{k+1}} = \displaystyle\sum_{k = 1}^{n+1}\dfrac{(k-1)^2}{2^k}$.

Subtract the 2nd equation from the 1st to get: $\dfrac{1}{2}S = -\dfrac{n^2}{2^{n+1}} + \displaystyle\sum_{k = 1}^{n}\dfrac{2k-1}{2^k}$

Multiply by $\dfrac{1}{2}$ and shift indices: $\dfrac{1}{4}S = -\dfrac{n^2}{2^{n+2}} + \displaystyle\sum_{k = 1}^{n}\dfrac{2k-1}{2^{k+1}} = -\dfrac{n^2}{2^{n+2}} + \displaystyle\sum_{k = 2}^{n+1}\dfrac{2k-3}{2^k}$.

Subtract the 4th equation from the 3rd: $\dfrac{1}{4}S = -\dfrac{n^2}{2^{n+2}}+\dfrac{1}{2}-\dfrac{2n-1}{2^{n+1}} + \displaystyle\sum_{k = 2}^{n}\dfrac{2}{2^k}$.

The last summation is a geometric series, so $\displaystyle\sum_{k = 2}^{n+1}\dfrac{2}{2^k} = \dfrac{\dfrac{2}{2^2} - \dfrac{2}{2^{n+1}}}{1-\dfrac{1}{2}} = 1 - \dfrac{1}{2^{n-1}}$.

Hence, $\dfrac{1}{4}S = -\dfrac{n^2}{2^{n+2}}+\dfrac{1}{2}-\dfrac{2n-1}{2^{n+1}} + 1 - \dfrac{1}{2^{n-1}}$.

Multiply by $4$ and simplify to get $S = 6 - \dfrac{n^2+4n+6}{2^n}$

Answer 4

Let $$f_2(n)=\sum_{k = 0}^{n}\frac{k^2}{2^k},f_1(n)=\sum_{k = 0}^{n}\frac{k}{2^k},f_0(n)=\sum_{k = 0}^{n}\frac{1}{2^k}$$ Since $f_1,f_0$ are known: $$\begin{align*}f_2(n)&=\sum_{k = 0}^{n}\frac{k^2}{2^k}=\sum_{k = 0}^{n-1}\frac{(k+1)^2}{2^{k+1}}\\ &=\sum_{k = 0}^{n-1}\frac{k^2}{2^{k+1}}+\sum_{k = 0}^{n-1}\frac{2k}{2^{k+1}}+\sum_{k = 0}^{n-1}\frac{1}{2^{k+1}}\\ &=\sum_{k = 1}^{n}\frac{k^2}{2^{k+1}}-\frac{n^2}{2^{n+1}}+f_1(n-1)+\frac{f_0(n-1)}{2}\\ \implies f_2(n)&=\frac{f_2(n)}{2}-\frac{n^2}{2^{n+1}}+f_1(n-1)+\frac{f_0(n-1)}{2} \end{align*}$$

Solving for $f_2(n)$: $$f_2(n)=-\frac{n^2}{2^{n}}+2f_1(n-1)+f_0(n-1)$$

---

If $f_1$ was not known, it can be obtained with the same method as above from $f_0$. Moreover, this lets us know $f_k$ for every $k\in \mathbb{N}$. Also, I bet this was one of the methods André Nicolas was talking about.

Answer 5

For the time being, let us consider $$S_n=\displaystyle\sum_{k = 0}^{n}{k^2}x^k=\sum_{k = 0}^{n}{k(k-1)}x^k+\sum_{k = 0}^{n}kx^k=x^2\sum_{k = 0}^{n}{k(k-1)}x^{k-2}+x\sum_{k = 0}^{n}kx^{k-1}$$ and now define $$T_n=\sum_{k = 0}^{n}x^{k}$$ So,we have $$S_n=x^2 \frac{dT^2_n}{dx^2}+x\frac{dT_n}{dx}$$ But $$T_n=\frac{x^{n+1}-1}{x-1}$$ so $$\frac{dT_n}{dx}=\frac{n x^{n+1}-(n+1) x^n+1}{(x-1)^2}$$ $$\frac{dT^2_n}{dx^2}=\frac{2 \left(n^2-1\right) x^n-n (n+1) x^{n-1}+(1-n) n x^{n+1}+2}{(x-1)^3}$$ and so $$S_n=\frac{x (x+1)-x^{n+1} \left(n^2 x^2-\left(2 n^2+2 n-1\right) x+(n+1)^2\right)}{(1-x)^3}$$ Replace now $x$ by $\frac{1}{2}$ to get the final answer $$S_n=\displaystyle\sum_{k = 0}^{n}\dfrac{k^2}{2^k}=6-2^{-n}(6+4n+n^2)$$