Show that for $k$ running over positive integers $ \sum_{k=1}^\infty \frac{k^2}{2^k}=6 .$ We can use finite calculus.
Proof of the equality $\sum\limits_{k=1}^{\infty} \frac{k^2}{2^k} = 6$
-
0The first one should be $\sin^2 z+\cos^2 z=1$. Euler's identity is missnamed, it is an equation. – 2012-05-27
8 Answers
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.
-
2@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.) – 2011-09-07
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$.
-
1@Arjang, you should be able to undo your downvote now. – 2011-09-07
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.
-
0@Sanch: what part of it isn't working? It's hard to help without knowing more specific details... – 2011-09-06
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 $
-
0I just noticed the pre-calculus tag. Derivatives may not be a good way to go, then. – 2011-09-07
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.
Solution
For convenience, we denote $a_k=\frac{k^2+2k+3}{2^{k-1}},~~~k=1,2,\cdots$ Then $\frac{k^2}{2^k}=a_k-a_{k+1}.$ Thus \begin{align*}\sum_{k=1}^n \frac{k^2}{2^k}&=(a_1-a_2)+(a_2-a_3)+\cdots+(a_n-a_{n+1})=a_1-a_{n+1}\\&=6-\frac{(n+1)^2+2(n+1)+3}{2^n}\\&=6-\frac{n^2+4n+6}{2^n}.\end{align*}
It follows that \begin{align*}\sum_{k=1}^\infty\frac{k^2}{2^k}&=\lim_{n \to \infty}\sum_{k=1}^n \frac{k^2}{2^k}\\&=\lim_{n \to \infty}\left(6-\frac{n^2+4n+6}{2^n}\right)\\&=6-0\\&=6.\end{align*}
Claim. For every polynomial $p(t)\in\mathbb{C}[t]$ of degree at most $m$ and for any complex number $z$ with $|z|<1$, we have $\begin{align}\sum_{k=0}^\infty\,p(k)\,z^k&=\frac{1}{1-z}\,\sum_{r=0}^m\,\left(\frac{z}{1-z}\right)^r\,\sum_{s=0}^r\,(-1)^{r-s}\,\binom{r}{s}\,p(s) \\&=\frac{1}{1-z}\,\sum_{s=0}^m\,\left(\frac{z}{1-z}\right)^s\,p(s)\,\sum_{r=0}^{m-s}\,(-1)^{r}\,\binom{r+s}{s}\,\left(\frac{z}{1-z}\right)^r\,.\end{align}$
We want to find $f(z):=\sum_{k=0}^\infty\,p(k)\,z^k\,,$ where $p(t)\in\mathbb{C}[t]$ and $x\in\mathbb{C}$ is such that $|z|<1$. The idea is to determine $q_z(t)\in\mathbb{C}[t]$ depending on $z$ such that $q_z(k+1)\,z^{k+1}-q_z(k)\,z^k=-p(k)\,z^k\,.$ This will show that $\sum_{k=0}^n\,p(k)\,z^k=q_z(0)-q_z(n+1)\,z^{n+1}\text{ for }n=0,1,2,\ldots\,,$ which then implies that $f(z)=q_z(0)$.
In this part, the condition $|z|<1$ is not necessary. For each $g(t)\in\mathbb{C}[t]$, set $\Delta\,g(t):=g(t+1)-g(t)\,.$ For each integer $r\geq 1$, we have $\Delta^r\,g:=\Delta^{r-1}\,\big(\Delta\,g\big)\,,$ where $\Delta^0\,g:=g$ (and so $\Delta^1\,g=\Delta\,g$). If $z\neq 1$, then take $q_z(t):=\frac{1}{1-z}\,\sum_{r=0}^m\,\left(\frac{z}{1-z}\right)^r\,\Delta^r\,p(t)\,,$ where $m$ is the degree of $p(t)$. Observe that $\Delta^{m+1}\,p\equiv0$. That is, $\begin{align} q_z(t)-z\,q_z(t+1)&=\small\frac{1}{1-z}\,\sum_{r=0}^m\,\left(\frac{z}{1-z}\right)^r\,\Delta^r\,p(t)-\frac{z}{1-z}\,\sum_{r=0}^m\,\left(\frac{z}{1-z}\right)^r\,\Delta^r\,p(t+1) \\ &=\small\frac{1}{1-z}\,\sum_{r=0}^m\,\left(\frac{z}{1-z}\right)^r\,\Delta^r\,p(t)-\frac{z}{1-z}\,\sum_{r=0}^m\,\left(\frac{z}{1-z}\right)^r\,\Big(\Delta^{r+1}\,p(t)+\Delta^r\,p(t)\Big) \\ &=\small\frac{1}{1-z}\,\sum_{r=0}^m\,\left(\frac{z}{1-z}\right)^r\,\Delta^r\,p(t)-\sum_{r=1}^{m}\,\left(\frac{z}{1-z}\right)^r\,\Delta^r\,p(t)-\frac{z}{1-z}\,\sum_{r=0}^m\,\left(\frac{z}{1-z}\right)^r\,\Delta^r\,p(t) \\ &=\sum_{r=0}^m\,\left(\frac{z}{1-z}\right)^r\,\Delta^r\,p(t)-\sum_{r=1}^m\,\left(\frac{z}{1-z}\right)^r\,\Delta^r\,p(t) \\ &=\left(\frac{z}{1-z}\right)^0\,\Delta^0\,p(t)=p(t)\,. \end{align}$ Now, write $p(t)=\sum_{r=0}^m\,p_r\,\binom{t}{r}\,,$ where $p_0,p_1,\ldots,p_m$ are complex numbers. For $z=1$, take $q_z(t)=q_1(t):=-\sum_{r=0}^m\,p_r\,\binom{t}{r+1}\,,$ whence $q_1(t+1)-q_1(t)=-\sum_{r=0}^m\,p_r\,\Biggl(\binom{t+1}{r+1}-\binom{t}{r+1}\Biggr)=-\sum_{r=0}^m\,p_r\,\binom{t}{r}=-p(t)\,.$ That is, $z^{k+1}\,q_z(t+1)-z^k\,q_z(t)=-z^k\,p(t)$ holds identically for all $k=0,1,2,\ldots$ and $z\in\mathbb{C}$. In fact, if $z\neq 1$, we can also write $q_z(t)=\frac{1}{1-z}\,\sum_{r=0}^m\,\left(\frac{z}{1-z}\right)^r\,\sum_{s=0}^{m-r}\,p_{s+r}\,\binom{t}{s}=\frac{1}{1-z}\,\sum_{s=0}^m\,p_s\,\sum_{r=0}^s\,\left(\frac{z}{1-z}\right)^{s-r}\,\binom{t}{r}\,.$
In the remaining work, $|z|<1$ is assumed. From the result above, $ \begin{align}f(z)&=q_z(0)=\frac{1}{1-z}\,\sum_{r=0}^m\,\left(\frac{z}{1-z}\right)^r\,\Delta^r\,p(0) \\ &=\frac{1}{1-z}\,\sum_{r=0}^m\,\left(\frac{z}{1-z}\right)^r\,\sum_{s=0}^r\,(-1)^{r-s}\,\binom{r}{s}\,p(s) \\ &=\frac{1}{1-z}\,\sum_{s=0}^m\,\left(\frac{z}{1-z}\right)^s\,p(s)\,\sum_{r=0}^{m-s}\,(-1)^{r}\,\binom{r+s}{s}\,\left(\frac{z}{1-z}\right)^r \end{align}$ for $z\in\mathbb{C}$ such that $|z|<1$. In paticular, if $p(t)=t^2$ and $z=\frac{1}{2}$, then $f\left(\frac{1}{2}\right)=f(z)=2\,\sum_{s=0}^2\,p(s)\,\sum_{r=0}^{2-s}\,(-1)^r\,\binom{r+s}{s}=2\,\big(p(0)-p(1)+p(2)\big)=6\,,$ as $m=2$. In fact, $\begin{align}q_{\frac{1}{2}}(t)&=2\,\Big(p(t)+\big(p(t+1)-p(t)\big)+\big(p(t+2)-2\,p(t+1)+p(t)\big)\Big) \\&=2\,\big(t^2+(2t+1)+2\big)=2\,\left(t^2+2t+3\right)\,,\end{align}$ so $\frac{k^2}{2^k}=\frac{k^2+2k+3}{2^{k-1}}-\frac{(k+1)^2+2(k+1)+3}{2^{(k+1)-1}}\,,$ as discovered by mengdie1982.