# Proof of the equality $\sum\limits_{k=1}^{\infty} \frac{k^2}{2^k} = 6$

Show that for $k$ running over positive integers $$\sum_{k=1}^\infty \frac{k^2}{2^k}=6 .$$ We can use finite calculus.

-
What do you mean by 'finite calculus'? Also, I presume you mean 'sum over all the integers $k$', not 'where $k$ is any integer' - these are two very different concepts! – Steven Stadnicki Sep 6 '11 at 22:57
@Steven Stadnicki . I have edited the question now. Finite calculus is analogous to simple calculus just applied on discrete sets. Here we are working with integers. We might be able to derive the equation using it. – Eowyn Sep 6 '11 at 23:16
Applying summation by parts twice should work. – Mike Spivey Sep 6 '11 at 23:17
@Sanch : Does the editing correspond to what you wanted to ask? – user13838 Sep 6 '11 at 23:18
@Peter: The word "identity" is reasonable in this context and there was no real need for editing. Much like $\sin(a+b)=\sin a\cos b+\cos a\sin b$ is an identity. – Asaf Karagila May 27 '12 at 17:46

Different people describe the techniques of finite calculus differently. I like the version presented in Section 2.6 of Graham, Knuth, & Patashnik, Concrete Mathematics, because it shows very clearly the similarity to ordinary calculus. In their notation what you want is $\sum_1^\infty k^2 2^{-k} \delta k$. This is analogous to the ordinary calculus integral $\int_1^\infty x^2 e^{-x} dx$, which you’d do by integrating by parts twice to reduce the $x^2$ factor to a constant. You can do the same thing here using summation by parts. Since this is homework, I’ll do a similar but slightly simpler problem, $\sum_1^\infty k 2^{-k} \delta k$.

First replace the infinite sum by a finite one; we’ll take the limit later. Then you have $\sum_1^n k 2^{-k} \delta k$, or in ordinary summation notation $\sum\limits_{k=1}^{n-1} k 2^{-k}$. Let $u = k$ and $\Delta v = 2^{-k} = (1/2)^k$; then $\Delta u = 1$, and $v = \left(\frac12\right)^k / \left(\frac12 - 1\right)= -\left(\frac12\right)^{k-1}$, so $E(v) = -\left(\frac12\right)^k$, and

\begin{align*} \textstyle\large\sum_1^n k 2^{-k} \delta k &= \left[-k\left(\frac12\right)^{k-1}\right]_1^n + \textstyle\large\sum_1^n \left(\frac12\right)^k \delta k\\ &= 1 - \frac{n}{2^{n-1}} + \textstyle\large\sum_1^n \left(\frac12\right)^k \delta k\\ &= 1 - \frac{n}{2^{n-1}} + \left[-\left(\frac12\right)^{k-1} \right]_1^n\\ &= 1 - \frac{n}{2^{n-1}} - \left(\frac{1}{2^{n-1}} - 1\right)\\ &= 2 - \frac{n+1}{2^{n-1}}. \end{align*}

Now just take the limit: $$\sum_{k=1}^\infty \frac{k}{2^k} = \lim_{n\to\infty}\left(2 - \frac{n+1}{2^{n-1}}\right) = 2.$$

This of course had only one summation by parts, and you’ll need two, but the principle is exactly the same.

-
+1 for using finite calculus (at least the way I understand it) – Mike Spivey Sep 7 '11 at 0:22
+1 Very nice. By the way, you seem to have used $\delta x$ in place of $\delta k$ in some places. – Srivatsan Sep 7 '11 at 0:26
@Srivatsan: Thanks. Habit’s a horrible thing sometimes, but I think that I caught them all this time. – Brian M. Scott Sep 7 '11 at 0:33
Considering my fondness for Knuth's work I'm surprised I've never bought Concrete Mathematics; I'll have to keep an eye out! – Steven Stadnicki Sep 7 '11 at 0:54
@Steven: I like math books with individual character, and it has it in spades: it’s actually fun to read. (Oddly enough, the other two that come to mind are elementary: the liberal arts statistics book by Freedman, Purves, and Pisani, and an old calculus book by Ralph P. Agnew, Calculus: Analytic Geometry and Calculus, with Vectors, which is chock full of snide and sarcastic remarks.) – Brian M. Scott Sep 7 '11 at 9:19

For starters, you know that $\displaystyle \sum_{k=1}^\infty {1\over 2^k} = 1$, yes? If you don't have that much, then you likely won't be able to follow the rest of the proof.

Now, consider $\displaystyle S=\sum_{k=1}^\infty {k\over 2^k}$. Then $\displaystyle {S\over 2} = \sum_{k=1}^\infty {k\over 2*2^k} = \sum_{k=1}^\infty {k\over 2^{k+1}} = \sum_{l=2}^\infty {l-1\over 2^l} = \sum_{l=1}^\infty {l-1\over 2^l}$. (The reason why the last equality is true is because the $l=1$ term is ${1-1\over 2^1}=0$, so we can add it in without changing the sum.) This means that $\displaystyle S-{S\over 2} = \sum_{k=1}^\infty {k\over 2^k} - \sum_{k=1}^\infty {k-1\over 2^k} = \sum_{k=1}^\infty {k-(k-1)\over 2^k} = \sum_{k=1}^\infty {1\over 2^k} = 1$, or in other words $S=2$. Now, can you see how to use a similar technique on your sum? The terms will be a little more complicated, but using the formula for $\sum_{k=1}^\infty {k\over 2^k}$ will help.

-
@ Steven Standnicki, I am sorry , I had tried this but this is not working. – Eowyn Sep 6 '11 at 23:25
@Sanch: what part of it isn't working? It's hard to help without knowing more specific details... – Steven Stadnicki Sep 6 '11 at 23:28

Alternative way of solving this problem. Using some basic calculus of the power series. Starting from $\sum \limits_{k \geq 1} k^2\left(\frac12\right)^k$, consider a power series $\sum \limits_{k \geq 1} k^2x^k= x\sum \limits_{k \geq 1} k^2x^{k-1}$ which converges uniformly whenever $|x| <1$. We get our sum by standard differentiation and integration of the power series. You can integrate $\sum \limits_{k \geq 1} k^2x^{k-1}$ term by term so $\sum \limits_{k \geq 1} \int_0^x k^2t^{k-1}\mathrm dt=\sum \limits_{k \geq 0}kx^k$. Again, $\sum \limits_{k \geq 0}kx^k= 1+x \sum \limits_{k \geq 1}kx^{k-1}$, by integrating term by term $\sum \limits_{k \geq 1}\int_0^x kt^{k-1}\mathrm dt= \sum\limits_{k \geq 0}x^k=\frac{1}{1-x}$. Now, we must take the derivative so $\left(\frac1{1-x}\right)^{\prime}=\frac1{(1-x)^2}$ so $$1+x \sum \limits_{k \geq 1}kx^{k-1}= 1+\frac{x}{(1-x)^2}.$$ Taking again the derivative $\left( 1+\frac{x}{(1-x)^2}\right)^{\prime}=\frac{1+x}{(1-x)^3}$ so $$\sum \limits_{k \geq 1} k^2x^k = \frac{x(1+x)}{(1-x)^3}.$$ Finally, by putting $x=\frac12$ we get that $\sum \limits_{k \geq 1} k^2\left(\frac12\right)^k=6$.

-
This "trick" is incredibly useful, while so many don't seem to know it. – TMM Sep 7 '11 at 0:17
@Thijs: I thought that it was pretty standard: I used to demonstrate it with $\sum_{k=1}^\infty k/2^k$ in my 2nd semester calculus classes, though I’d not care to guess how many really caught on. It is nice, but it’s not finite calculus, so it doesn’t really answer the question. – Brian M. Scott Sep 7 '11 at 0:29
@Steven Stadnicki gave a proper answer. I was thinking that this method is worth mentioning, cos usually I'm using it during my calculus classes. – Edvin Goey Sep 7 '11 at 0:51
@Brian: I agree, but I've seen others (both online and in my studies) struggle with this, when it can be done easily with this trick. And it may not be a proper answer here, but I just think the trick itself is neat. (When seeing discrete sums over discrete objects, I normally would not think of doing "continuous stuff" like taking derivatives and integrals to solve it.) – TMM Sep 7 '11 at 1:17
@Arjang, you should be able to undo your downvote now. – J. M. Sep 7 '11 at 3:55

I find it more instructive to outline the process than solve the problem. You may therefore view this answer as a hint.

For any $x \in \mathbb{R}$, we have

$$f_N(x) := \sum_{k=1}^N x^k$$ Multiplying the function $f_N(x)$, we get $$x f_N(x) = \sum_{k=1}^N x^{k+1}.$$ Subtracting term by term, we see that $$xf_N(X) - f_N(x) = x^{N+1} - x$$ or $$f_N(x) = \frac{x^{N+1}-x}{x-1}.$$ If $|x| < 1$, then we have $$f(x) := \sum_{k \geq 1}x^k = \lim_{N \to \infty} f_N(x) = \frac{x}{1-x}.$$ Suppose we are allowed to differentiate and integrate $f(x)$ (we will worry about exactly when we can do this later). Then: \begin{align} \left(\frac{x}{1-x}\right)' = f'(x) = \sum_{k \geq 1} (k+1)x^k = \sum_{k \geq 1}kx^k + \sum_{k \geq 1} x^k = \sum_{k \geq 1} kx^k + f(x). \end{align} This gives a formula for $\sum_{k \geq 1} k x^k$. Can you see how to extend this to find the sum you're looking for?

-

You might look at $\sum_{k=1}^n {k^2\over 2^k}$, but this is a fraction, so look at $f(n)=2^n \sum_{k=1}^n {k^2 \over 2^k}$ instead. This satisfies the recurrence $f(n) = 2f(n-1)+n^2$ starting at $f(0)=0$.

It is not difficult to find the values of this for small $n$, namely 0, 1, 6, 21, 58, 141, 318, 685, 1434, 2949, 5998,... and it becomes clear that this is a little less than $6\times 2^n$ much as you might expect from the question. It is not difficult then to take differences (or looking up OEIS A047520, which I considered 11 years ago) and suspect it is likely to satisfy $f(n) = 6\times 2^n -n^2-4n-6$, and this can easily be proved by induction.

Then all you have to do is divide by $2^n$ and take the limit.

-

Consider the series $$\sum_{k=0}^\infty\;\frac{x^k}{2^k}=\frac{1}{1-x/2}$$ Take a derivative $$\sum_{k=0}^\infty\;k\frac{x^{k-1}}{2^k}=\frac{1/2}{(1-x/2)^2}\tag{1}$$ Take another derivative $$\sum_{k=0}^\infty\;k(k-1)\frac{x^{k-2}}{2^k}=\frac{1/2}{(1-x/2)^3}\tag{2}$$ Adding $(1)$ and $(2)$ at $x=1$, we get $$\sum_{k=0}^\infty\;\frac{k^2}{2^k}=6$$

-
I just noticed the pre-calculus tag. Derivatives may not be a good way to go, then. – robjohn Sep 7 '11 at 0:18