Prove that $\sum\limits_{n=1}^\infty \frac{n^2(n-1)}{2^n} = 20$

Question

This sum $\displaystyle \sum_{n=1}^\infty \frac{n^2(n-1)}{2^n} $showed up as I was computing the expected value of a random variable. My calculator tells me that $\,\,\displaystyle \sum_{n=1}^\infty \frac{n^2(n-1)}{2^n} = 20$. How can I show that?

I know how to find the value of the sum $\,\displaystyle \sum_{n=1}^\infty \frac{n^2}{2^n},\,$ but I can't deal with $\displaystyle \sum_{n=1}^\infty \frac{n^3}{2^n}$

Answer 1

Note that $\sum\limits_nt^n=\frac1{1-t}$ for every $|t|\lt1$ hence, differentiating this twice and three times, $$\sum_nn(n-1)t^{n-2}=\frac2{(1-t)^3},\qquad\sum_nn(n-1)(n-2)t^{n-3}=\frac6{(1-t)^4}.$$ For $t=\frac12$, this reads $$\sum_nn(n-1)\frac1{2^{n-2}}=2\cdot2^3,\qquad\sum_nn(n-1)(n-2)\frac1{2^{n-3}}=6\cdot2^4,$$ which implies $$\sum_nn(n-1)\frac1{2^{n}}=\frac14\cdot2\cdot2^3=\color{red}{4},\qquad\sum_nn(n-1)(n-2)\frac1{2^{n}}=\frac18\cdot6\cdot2^4=\color{blue}{12}.$$ Finally, $$n^2(n-1)=\color{green}{2}\cdot n(n-1)+n(n-1)(n-2),$$ hence $$\sum_nn^2(n-1)\frac1{2^{n}}=\color{green}{2}\cdot\sum_nn(n-1)\frac1{2^{n}}+\sum_nn(n-1)(n-2)\frac1{2^{n}}=\color{green}{2}\cdot\color{red}{4}+\color{blue}{12}.$$ This approach can be made shorter if one notices once and for all that, for every nonnegative $k$, $$\sum_nn(n-1)\cdots(n-k)\frac1{2^{n}}=2\cdot(k+1)!.$$

Answer 2

prove by induction that $\sum_{n=1}^m\frac{n^2(n-1)}{2^n}=-4\, \left( 1/2 \right) ^{m+1} \left( m+1 \right) ^{2}-14\, \left( 1/2 \right) ^{m+1} \left( m+1 \right) -20\, \left( 1/2 \right) ^{m+1}-2\, \left( 1/2 \right) ^{m+1} \left( m+1 \right) ^{3}+20 $

Answer 3

For $\lvert x\rvert<1$ we have that $\displaystyle\sum_{n=0}^\infty x^n=\frac{1}{1-x},$ hence differentiating both sides we get $$ \sum_{n=0}^\infty (n+1)x^{n}=\sum_{n=1}^\infty nx^{n-1}=\frac{1}{(1-x)^2}, $$ while differentiating once more $$ \sum_{n=0}^\infty (n+2)(n+1)x^{n}=\frac{2}{(1-x)^3}, $$ and once again $$ \sum_{n=0}^\infty (n+3)(n+2)(n+1)x^{n}=\frac{6}{(1-x)^4}. $$ Next, we express $n^2(n-1)$ as a linear combination of $(n+3)(n+2)(n+1)$, $(n+2)(n+1)$, $(n+1)$ and $1$: $$ n^2(n-1)=(n+3)(n+2)(n+1)-7(n+2)(n+1)+10(n+1)-2, $$ and hence $$ \sum_{n=0}^\infty n^2(n-1)x^n=\frac{6}{(1-x)^4}-\frac{14}{(1-x)^3}+\frac{10}{(1-x)^2}-\frac{2}{1-x}, $$ and setting $x=1/2$ we obtain that $$ \sum_{n=0}^\infty \frac{n^2(n-1)}{2^n}=6\cdot 16-4\cdot 8+10\cdot 4-4=20. $$

Answer 4

Say $f(x) = \sum_0^{\infty} \frac{x^n}{2^n} = \frac{1}{1-\tfrac{x}{2}}$. The first three derivatives of $f$ will be linear combinations of $a_k(x)=\sum^{\infty} \frac{n^k x^n}{2^n}$ for $k=1...3$ and are easy to calculate using $f$'s closed form.

Solve your system of equations in $a_k$ and you can compute your sum.

Answer 5

I like the triangle sum technique:

Take for instance:

$\displaystyle \sum_{n=1}^\infty \frac{n^2}{2^n}$

$\frac{1}{2}+2\cdot\frac{1}{4}+3\cdot\frac{1}{8}+...=\displaystyle \sum_{n=1}^\infty \frac{n}{2^n}=2$

$\hspace{20pt} 2\cdot\frac{1}{4}+3\cdot\frac{1}{8}+...=\frac{1}{2}{\displaystyle \sum_{n=1}^\infty \frac{n+1}{2^n}}=\frac{1}{2}{\displaystyle \sum_{n=1}^\infty \frac{n}{2^n}+\frac{1}{2^n}}=\frac{1}{2}\cdot (2+1)$

$\hspace{53pt} 3\cdot\frac{1}{8}+...$=$\frac{1}{4}{\displaystyle \sum_{n=1}^\infty \frac{n+2}{2^n}}$=$\frac{1}{4}{\displaystyle \sum_{n=1}^\infty \frac{n}{2^n}+2\cdot\frac{1}{2^n}}=\frac{1}{4}\cdot (2+2)$

$\hspace{100pt} .......$

$ 2+\frac{1}{2}\cdot (2+1)+\frac{1}{4}\cdot (2+2)+...=\displaystyle \sum_{n=0}^\infty \frac{2+n}{2^n}=2\cdot \displaystyle \sum_{n=0}^\infty \frac{1}{2^n}+\displaystyle \sum_{n=1}^\infty \frac{n}{2^n}=4+2=6$

Try it now?

$\displaystyle \sum_{n=1}^\infty \frac{n^3}{2^n}$

$\frac{1}{2}+4\cdot\frac{1}{4}+9\cdot\frac{1}{8}+...=\displaystyle \sum_{n=1}^\infty \frac{n^2}{2^n}$

$\hspace{20pt} 4\cdot\frac{1}{4}+9\cdot\frac{1}{8}+...=\frac{1}{2}{\displaystyle \sum_{n=1}^\infty \frac{(n+1)^2}{2^n}}$

$\hspace{53pt} 9\cdot\frac{1}{8}+...=\frac{1}{4}{\displaystyle \sum_{n=1}^\infty \frac{(n+2)^2}{2^n}}$

Hint: $\displaystyle \sum_{m=0}^\infty \frac{1}{2^m}\displaystyle \sum_{n=1}^\infty \frac{(n+m)^2}{2^n}$

Answer 6

As this post is intended to justify the answer of @Dr.Sonnhard Graubner, I make this CW.
The starting points are that, defining $S_k(m)=\sum_{n=1}^m\frac{n^k}{2^n},$ we can easily compute $S_0(m)$ and $S_k(1),$ and that we can use recursive relations to obtain $S_3(m)$ from $S_0(m)$ and $S_3(1).$
Thus we divide the post into four steps:
I. $k=0$
$S_0(m)=\sum_{n=1}^m\frac{1}{2^n}=1-\frac{1}{2^m}$ (Geometric series)
II. $k=1$
Since $S_1(m)-\frac{1}{2}=\frac{1}{2}(\sum_{n=1}^{m-1}\frac{n+1}{2^n})=\frac{1}{2}S_1(m-1)+\frac{1}{2}S_0(m-1),$ we find that $S_1(m)=\frac{1}{2}S_1(m-1)+1-2^{-m}=\frac{1}{2}(\frac{1}{2}S_1(m-2)+1-2^{-m+1})+1-2^{-m}=\cdots=\frac{1}{2^{m-1}}S_1(1)+\sum_{n=0}^{m-2}\frac{1}{2^{n}}(1-\frac{1}{2^{m-n}})=\frac{1}{2^m}+\frac{1-(1/2)^{m-1}}{1/2}-\frac{(m-1)}{2^m}=2-\frac{1}{2^m}(m+2).$
III. $k=2$
By similar token, one finds the recursive relation $S_2(m)=\frac{1}{2}S_2(m-1)+3-\frac{2m+3}{2^m}.$ Then we deduce the formular for $S_2(m):$
$$S_2(m)=\frac{1}{2^m}+\sum_{n=0}^{m-2}\frac{1}{2^n}(3-\frac{2(m-n)+3}{2^{m-n}})=\frac{1}{2^m}+6-\frac{12}{2^m}-\frac{1}{2^m}(m^2+4m-5)$$$$=6-\frac{1}{2^m}(m^2+4m+6).$$
IV. $k=3$
Again we have the resursive relation $S_3(m)=\frac{1}{2}S_3(m)+13-\frac{1}{2^m}(3m^2+9m+13),$ from which we deduce the formula:
$$S_3(m)=\frac{1}{2^{m-1}}S_3(1)+\sum_{n=0}^{m-2}\frac{1}{2^n}(13-\frac{3(m-n)^2+9(m-n)+13}{2^{m-n}})$$
$$=\cdots=\frac{1}{2^m}+26-\frac{52}{2^m}-\frac{m^3+6m^2+18m-25}{2^m}=26-\frac{m^3+6m^2+18m+26}{2^m}.$$
Here the dots mean a process of simplification.
Hence we see that $\lim_{m\rightarrow\infty}S_3(m)-S_2(m)=26-6=20.$
So I am wondering where do those $(1/2)^{m+1}$ terms in the answer by @Dr.Sonnhard Graubner appear.

Finally I would like to say something, in reply to @Did: Indeed no simple functional equation holds for $S_k(m),$ but one doesn't expect there to be one at all: instead one looks for a recursive relation, to which one is used in dealing with discrete relations, such as finding the partial sums.

Hope this helps still.

Answer 7

As hinted by @AlexandreHalm, $$\sum_{k=0}^\infty x^k=\frac1{1-x}.$$

Then deriving on $x$ and multiplying by $x$,

$$\sum_{k=0}^\infty kx^k=\frac x{(1-x)^2},$$ $$\sum_{k=0}^\infty k^2x^k=\frac{2x^2}{(1-x)^3}+\frac x{(1-x)^2},$$ $$\sum_{k=0}^\infty k^3x^k=\frac{6x^3}{(1-x)^4}+\frac{6x^2}{(1-x)^3}+\frac x{(1-x)^2}.$$

Evaluating at $x=\frac12$,

$$\sum_{k=0}^\infty\frac{k^3}{2^k}-\sum_{k=0}^\infty\frac{k^2}{2^k}=26-6=20.$$