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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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 $$

Answer 5

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?

Answer 6

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.