# How to prove $\sum_{n=0}^{\infty} \frac{n^2}{2^n} = 6$?

I'd like to find out why

\begin{align} \sum_{n=0}^{\infty} \frac{n^2}{2^n} = 6 \end{align}

I tried to rewrite it into a geometric series

\begin{align} \sum_{n=0}^{\infty} \frac{n^2}{2^n} = \sum_{n=0}^{\infty} \Big(\frac{1}{2}\Big)^nn^2 \end{align}

But I don't know what to do with the $n^2$.

-

First observe that the sum converges (by, say, the root test).

We already know that $\displaystyle R := \sum_{n=0}^\infty \frac{1}{2^n} = 2$.

Let $S$ be the given sum. Then $\displaystyle S = 2S - S = \sum_{n=0}^\infty \frac{2n+1}{2^n}$.

Now use the same trick to compute $\displaystyle T := \sum_{n=0}^\infty \frac{n}{2^n}$: we have $\displaystyle T = 2T - T = \sum_{n=0}^\infty \frac{1}{2^n} = R = 2$. Hence $S = 2T + R = 6$.

One can continue like this to compute $\displaystyle X:= \sum_{n=0}^\infty \frac{n^3}{2^n}$. We have $\displaystyle X = 2X-X = \sum_{n=0}^\infty \frac{3n^2+3n+1}{2^n} = 3S+3T+R = 26$. Sums with larger powers can be computed in the same way.

-
+1 Very elegant! – nbubis Dec 6 '13 at 2:40

If Calculus is allowed, using infinite geometric series formula for $|r|<1$ $$\sum_{0\le n<\infty}r^n=\frac1{1-r}$$

Differentiating wrt $r$ $$\sum_{0\le n<\infty}nr^{n-1}=\frac1{(1-r)^2}$$

$$\implies \sum_{0\le n<\infty}nr^n=\frac r{(1-r)^2}=\frac{1-(1-r)}{(1-r)^2}=\frac1{(1-r)^2}-\frac1{(1-r)}$$

Differentiating wrt $r$ (fixed sign error!)

$$\implies \sum_{0\le n<\infty}n^2r^{n-1}=\frac2{(1-r)^3}-\frac1{(1-r)^2}$$

$$\implies \sum_{0\le n<\infty}n^2r^n=\frac{2r}{(1-r)^3}-\frac r{(1-r)^2}$$

Here $\displaystyle r=\frac12$

-
You had a sign error after you differentiated, but it is fixed! – trb456 Dec 6 '13 at 2:17
@trb456, thanks for your rectification – lab bhattacharjee Dec 6 '13 at 3:48

There is an elementary and visually appealing solution, which is to think "matrix-like".

Knowing that $\sum_{n=0}^{\infty} 2^{-n}=2$, the sum $\sum_{n=0}^{\infty}n/2^n$ can be rewritten as:

\begin{align} && 0/2^0 && + && 1/2^1 && + && 2/2^2 && + && 3/2^3 && + && \cdots && = \\ = && && + && 2^{-1} && + && 2^{-2} && + && 2^{-3} && + && \cdots && + \\ + && && && && + && 2^{-2} && + && 2^{-3} && + && \cdots && + \\ + && && && && && && + && 2^{-3} && + && \cdots && + \\ + && && && && && && && && + && \ddots \end{align}

summed first in the columns, then in the rows. It doesn't matter which direction you sum first, because all sums in both directions converge absolutely. So we can sum first in the rows, and then in the columns. Each row-sum is just a geometric series; the $m$-th row-sum is $r_m=\sum_{n=m}^{\infty} 2^{-n}=2^{1-m}$. Now summing up all rows, we have $\sum r_m = 2$.

What we just did is equivalent to:

$$\sum_{n=0}^{\infty} \frac{n}{2^n} = \sum_{n=0}^{\infty} \sum_{m=1}^{n} \frac{1}{2^n} = \sum_{m=1}^{\infty} \sum_{n=m}^{\infty} 2^{-n}= \sum_{m=1}^{\infty} 2^{1-m} = 2$$

It's not hard to do it for a three-dimensional matrix, unless you try to draw it :)

$$\sum_{n=0}^{\infty} \frac{n^2}{2^n} = \sum_{n=0}^{\infty} \sum_{m=1}^{n} \frac{n}{2^n} = \sum_{m=1}^{\infty} \sum_{n=m}^{\infty} \frac{n}{2^n} = \sum_{m=1}^{\infty} \left\{ \sum_{n=0}^{\infty} \frac{n}{2^n} - \sum_{n=0}^{m-1} \frac{n}{2^n} \right\}$$

We can work out $\sum_{n=0}^{m-1} \frac{n}{2^n}$ in the same way we did for $\sum_{n=0}^{\infty} \frac{n}{2^n}$:

$$\sum_{n=0}^{m-1} \frac{n}{2^n} = \sum_{n=0}^{m-1} \sum_{l=1}^{n} \frac{1}{2^n} = \sum_{l=1}^{m-1} \sum_{n=l}^{m-1} 2^{-n} = \sum_{l=1}^{m-1} \left\{ 2^{1-l} - 2^{1-m} \right\} = 2 - \left(m+1\right)2^{1-m}$$

Substituting:

$$\sum_{n=0}^{\infty} \frac{n^2}{2^n} = \sum_{m=1}^{\infty} \left\{ 2 - \left[ 2 - \left(m+1\right)2^{1-m} \right] \right\} = \sum_{m=1}^{\infty} \left(m+1\right)2^{1-m} = \\ \sum_{m=1}^{\infty} \left\{ \left(m-1\right)2^{1-m} + 2\cdot 2^{1-m} \right\} = \sum_{m=0}^{\infty} m\cdot 2^{-m} + 4\sum_{m=1}^{\infty} 2^{-m} = 2 + 4 = 6$$

Again, you can change the order of summations because all inner sums converge absolutely.

-

First we compute the sum $S_1=\sum_{n=1}^\infty \frac{n}{2^n}$ using the identity $n=\sum_{k=1}^n1$ $$S_1=\sum_{n=1}^\infty \frac{n}{2^n}=\sum_{n=1}^\infty \sum_{k=1}^n \frac{1}{2^n}=\sum_{ k \leq n }\frac{1}{2^n}=\sum_{k=1}^\infty \sum_{n=k}^\infty \frac{1}{2^n}=\sum_{k=1}^\infty \frac{1/2^k}{1-1/2}=2 \sum_{k=1}^\infty \frac{1}{2^k}=2.$$ Next we compute the sum $S_2=\sum_{n=1}^\infty \frac{n+n^2}{2^{n+1}}$ using the identity $\frac{n+n^2}{2}=\sum_{k=1}^n k$ $$S_2=\sum_{n=1}^\infty \sum_{k=1}^n \frac{k}{2^n}=\sum_{k \leq n} \frac{k}{2^n}=\sum_{k=1}^\infty \sum_{n=k}^\infty \frac{k}{2^n}=\sum_{k=1}^\infty k \frac{1/2^k}{1-1/2}=2 \sum_{k=1}^\infty \frac{k}{2^k}=2S_1=4.$$ Finally the desired sum is $S=2S_2-S_1=6$.

-

Let me show you a slightly different approach; this approach is very powerful, and can be used to compute values for a large number of series.

Let's think of this in terms of power series. You noticed that you can write $$\sum_{n=0}^{\infty}\frac{n^2}{2^n}=\sum_{n=0}^{\infty}n^2\left(\frac{1}{2}\right)^n;$$ so, let's consider the power series $$f(x)=\sum_{n=0}^{\infty}n^2x^n.$$ If we can find a simpler expression for the function $f(x)$, and if $\frac{1}{2}$ lies within its interval of convergence, then your series is exactly $f(\frac{1}{2})$.

Now, we note that $$f(x)=\underbrace{0}_{n=0}+\sum_{n=1}^{\infty}n^2x^n=x\sum_{n=1}^{\infty}n^2x^{n-1}.$$ But, notice that $\int n^2x^{n-1}\,dx=nx^n$; so, $$\tag{1} \sum_{n=1}^{\infty}n^2 x^{n-1}=\frac{d}{dx}\left[\sum_{n=0}^{\infty}nx^n\right].$$ Now, we write $$\tag{2} \sum_{n=0}^{\infty}nx^n=\underbrace{0}_{n=0}+x\sum_{n=1}^{\infty}nx^{n-1}=x\frac{d}{dx}\left[\sum_{n=0}^{\infty}x^n\right].$$ But, this last is a geometric series; so, as long as $\lvert x\rvert<1$, $$\sum_{n=0}^{\infty}x^n=\frac{1}{1-x}.$$ Plugging this back in to (2), we find that for $\lvert x\rvert<1$, $$\sum_{n=0}^{\infty}nx^n=x\frac{d}{dx}\left[\frac{1}{1-x}\right]=x\cdot\frac{1}{(1-x)^2}=\frac{x}{(1-x)^2}.$$ But, plugging this back in to (1), we find that $$\sum_{n=1}^{\infty}n^2x^{n-1}=\frac{d}{dx}\left[\frac{x}{(1-x)^2}\right]=\frac{x+1}{(1-x)^3}$$ So, finally, $$f(x)=x\cdot\frac{x+1}{(1-x)^3}=\frac{x(x+1)}{(1-x)^3}.$$ Plugging in $x=\frac{1}{2}$, we find $$\sum_{n=0}^{\infty}\frac{n^2}{2^n}=f\left(\frac{1}{2}\right)=6.$$

-

Consider $$\frac{1}{1-z} = \sum_{n=0}^{\infty} z^n$$ Differentiating and multiplying by $z$, one has $$\frac{z}{(1-z)^2} = z\sum_{n=1}^{\infty} nz^{n-1} = \sum_{n=1}^{\infty} nz^n$$ Repeating the above process, $$\sum_{n=1}^{\infty} n^2z^n = \frac{z(1+z)}{(1-z)^3}$$ Now plug in $z=1/2$

-