How do I evaluate this infinite summation?
Moderators: gmalivuk, Moderators General, Prelates
How do I evaluate this infinite summation?
[math]\sum_{k=0}^{\infty}\frac{k^2}{2^k}[/math]
No idea where to even start. It's not for homework, but it was on a math team practice test and I'm not really sure how to do it.
No idea where to even start. It's not for homework, but it was on a math team practice test and I'm not really sure how to do it.

 Posts: 272
 Joined: Thu Jul 09, 2009 9:26 am UTC
Re: How do I evaluate this infinite summation?
Depends what level you're working at, what you're allowed to take as given and whether you're asked to prove your result or just find the number.
For example, they might expect you to just punch numbers into a computer/calculator and identify the limit by eye or maybe they want you to prove a limit exists with a convergence test then work out what it is and prove that you've got the right limit with an epsilondelta proof or alternatively, they might even expect you to just quote the general rule
[imath]\sum_{k=1}^{\infty} k^2 x^k =\frac{x(1+x)}{(1x)^3}[/imath] for [imath]x < 1[/imath]
and pop in x=1/2. I wouldn't like to guess what's wanted without a bit more context (maybe I should know what math team is, but I don't even have an idea whether it's a uni thing or a school thing).
For example, they might expect you to just punch numbers into a computer/calculator and identify the limit by eye or maybe they want you to prove a limit exists with a convergence test then work out what it is and prove that you've got the right limit with an epsilondelta proof or alternatively, they might even expect you to just quote the general rule
[imath]\sum_{k=1}^{\infty} k^2 x^k =\frac{x(1+x)}{(1x)^3}[/imath] for [imath]x < 1[/imath]
and pop in x=1/2. I wouldn't like to guess what's wanted without a bit more context (maybe I should know what math team is, but I don't even have an idea whether it's a uni thing or a school thing).
Re: How do I evaluate this infinite summation?
Hint: how would you evaluate the integral x^{2}/2^{x} dx from 0 to infinity? Is there a corresponding technique for summations?
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
Re: How do I evaluate this infinite summation?
I don't know what level this is either, but I feel like it makes sense to point you to generating functions.
Anyway, generating functions are one of your best friends for infinite series.
Spoiler:
Anyway, generating functions are one of your best friends for infinite series.
Re: How do I evaluate this infinite summation?
This is just a highschool level maths competition. Nothing like epsilondelta would be required. I'm not familiar with the term "generating function" but I've seen other problems where you were supposed to find the sum by first taking a series you know how to evaluate and then differentiating/multiplying by x, so I think that's probably the method they wanted us to use.
@antonfire: I would integrate by parts then evaluate the limit of the value as the upper limit of the integral approached infinity. But I do not know an analogue of this procedure that would aid in evaluating this sum.
@antonfire: I would integrate by parts then evaluate the limit of the value as the upper limit of the integral approached infinity. But I do not know an analogue of this procedure that would aid in evaluating this sum.

 Posts: 272
 Joined: Thu Jul 09, 2009 9:26 am UTC
Re: How do I evaluate this infinite summation?
The differentiating method's probably what they're looking for then. Just thought I'd add the advice to be careful and think about where your identities are valid.
Edit: I've just worked through the solution by differentiating. There's a bit of messing around to be done after you've differentiated, but it's fairly doable.
Spoiler:
Edit: I've just worked through the solution by differentiating. There's a bit of messing around to be done after you've differentiated, but it's fairly doable.
Re: How do I evaluate this infinite summation?
greengiant wrote:Try the free ebook generatingfunctionology by Herbert S. Wilf if you want to learn how to work with g.f.'s
Wow, thanks for posting this
http://aselliedraws.tumblr.com/  surreal sketches and characters.
Re: How do I evaluate this infinite summation?
The analogue of integration by parts for summations is called, as you might expect, summation by parts.Kurushimi wrote:@antonfire: I would integrate by parts then evaluate the limit of the value as the upper limit of the integral approached infinity. But I do not know an analogue of this procedure that would aid in evaluating this sum.
Anyway, the generating functions approach is an easier computation, but I'd say you should know both ways. (And thinking about the relationship between them would probably be pretty useful too.)
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
Re: How do I evaluate this infinite summation?
If I were a bright high schooler who knows how to show this sum is absolutely convergent, and knows that the terms of an absolutely convergent series can be rearranged and the new series will still be absolutely convergent with the same sum as long as all the terms are included, and knows how to sum a geometric series, and knows the difference of squares of consecutive integers, this is the approach I would take:
Spoiler:
wee free kings
Re: How do I evaluate this infinite summation?
For what it's worth, Qaanol's method is essentially the summation by parts method. This might give you some insight on why summation by parts works, and maybe if you think about it hard enough even why integration by parts works. Unless you knew all that already.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
Re: How do I evaluate this infinite summation?
This is the generating functions approach to the problem. Very useful for any summation.
[math]\begin{eqnarray*}
S &=& \sum_{k=1}^{\infty} \frac{k^2}{2^k}\\
&=& \frac{1}{2} + \sum_{k=2}^{\infty} \frac{k^2}{2^k}\\
&=& \frac{1}{2} + \sum_{k=1}^{\infty} \frac{(k+1)^2}{2^{k+1}}\\
&=& \frac{1}{2} + \frac{1}{2} \sum_{k=1}^{\infty} \frac{k^2}{2^k} + \sum_{k=1}^{\infty} \frac{2k}{2^{k+1}} + \sum_{k=1}^{\infty} \frac{1}{2^{k+1}} \\
&=& \frac{1}{2} +\frac{1}{2}S + \sum_{k=1}^{\infty} \frac{k}{2^k} + K
&=& \frac{1}{2} +\frac{1}{2}S + T + K
\end{eqnarray*}[/math]
[math]\begin{eqnarray*}
S &=& \sum_{k=1}^{\infty} \frac{k^2}{2^k}\\
&=& \frac{1}{2} + \sum_{k=2}^{\infty} \frac{k^2}{2^k}\\
&=& \frac{1}{2} + \sum_{k=1}^{\infty} \frac{(k+1)^2}{2^{k+1}}\\
&=& \frac{1}{2} + \frac{1}{2} \sum_{k=1}^{\infty} \frac{k^2}{2^k} + \sum_{k=1}^{\infty} \frac{2k}{2^{k+1}} + \sum_{k=1}^{\infty} \frac{1}{2^{k+1}} \\
&=& \frac{1}{2} +\frac{1}{2}S + \sum_{k=1}^{\infty} \frac{k}{2^k} + K
&=& \frac{1}{2} +\frac{1}{2}S + T + K
\end{eqnarray*}[/math]
Last edited by Ankit1010 on Mon Mar 28, 2011 7:58 am UTC, edited 1 time in total.
Re: How do I evaluate this infinite summation?
[math]\begin{eqnarray*}
T &=& \sum_{k=1}^{\infty} \frac{k}{2^k} \\
&=& \frac{1}{2} + \sum_{k=2}^{\infty} \frac{k}{2^k} \\
&=& \frac{1}{2} + \sum_{k=2}^{\infty} \frac{k+1}{2^{k+1}} \\
&=& \frac{1}{2} + \frac{1}{2} \sum_{k=2}^{\infty} \frac{k}{2^k} + \sum_{k=2}^{\infty} \frac{1}{2^{k+1}}\\
&=& \frac{1}{2} + \frac{1}{2}T + K\\
T &=& 2
\end{eqnarray*}[/math]
K is just an infinite geometric series, so:
[math]K = \frac{a}{1r}[/math]
[math]K = \frac{1}{2}[/math]
where a is the first term, and r is the common ratio.
Which gives you S=6.
T &=& \sum_{k=1}^{\infty} \frac{k}{2^k} \\
&=& \frac{1}{2} + \sum_{k=2}^{\infty} \frac{k}{2^k} \\
&=& \frac{1}{2} + \sum_{k=2}^{\infty} \frac{k+1}{2^{k+1}} \\
&=& \frac{1}{2} + \frac{1}{2} \sum_{k=2}^{\infty} \frac{k}{2^k} + \sum_{k=2}^{\infty} \frac{1}{2^{k+1}}\\
&=& \frac{1}{2} + \frac{1}{2}T + K\\
T &=& 2
\end{eqnarray*}[/math]
K is just an infinite geometric series, so:
[math]K = \frac{a}{1r}[/math]
[math]K = \frac{1}{2}[/math]
where a is the first term, and r is the common ratio.
Which gives you S=6.

 Posts: 272
 Joined: Thu Jul 09, 2009 9:26 am UTC
Re: How do I evaluate this infinite summation?
A different way to get the more general result, starting from the sum to infinity of a geometric series (valid for x<1)
[math]\sum_{k=0}^{\infty} x^k=\frac{1}{1x}[/math]
[math]\sum_{k=0}^{\infty} kx^{k1}=\frac{1}{(1x)^2} \text{ (by differentiating) (*)}[/math]
[math]\sum_{k=0}^{\infty} k(k1)x^{k2}=\frac{2}{(1x)^3} \text{ (by differentiating)}[/math]
[math]\sum_{k=0}^{\infty} (k^2k)x^{k2}=\frac{2}{(1x)^3}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k2}\sum_{k=0}^{\infty} kx^{k2}=\frac{2}{(1x)^3}[/math]
[math]x(\sum_{k=0}^{\infty} k^{2}x^{k2}\sum_{k=0}^{\infty} kx^{k2})=\frac{2x}{(1x)^3} \text{ (multiplying both sides by x)}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k1}\sum_{k=0}^{\infty} kx^{k1}=\frac{2x}{(1x)^3}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k1}\frac{1}{(1x)^2}=\frac{2x}{(1x)^3} \text{using (*)}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k1}=\frac{2x}{(1x)^3}+\frac{1x}{(1x)^3}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k1}=\frac{1+x}{(1x)^3}[/math]
[math]x(\sum_{k=0}^{\infty} k^{2}x^{k1})=\frac{x(1+x)}{(1x)^3} \text{ (multiplying both sides by x)}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k}=\frac{x(1+x)}{(1x)^3}[/math]
Apologies if there are TeX mistakes, I'm not very good at it.
[math]\sum_{k=0}^{\infty} x^k=\frac{1}{1x}[/math]
[math]\sum_{k=0}^{\infty} kx^{k1}=\frac{1}{(1x)^2} \text{ (by differentiating) (*)}[/math]
[math]\sum_{k=0}^{\infty} k(k1)x^{k2}=\frac{2}{(1x)^3} \text{ (by differentiating)}[/math]
[math]\sum_{k=0}^{\infty} (k^2k)x^{k2}=\frac{2}{(1x)^3}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k2}\sum_{k=0}^{\infty} kx^{k2}=\frac{2}{(1x)^3}[/math]
[math]x(\sum_{k=0}^{\infty} k^{2}x^{k2}\sum_{k=0}^{\infty} kx^{k2})=\frac{2x}{(1x)^3} \text{ (multiplying both sides by x)}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k1}\sum_{k=0}^{\infty} kx^{k1}=\frac{2x}{(1x)^3}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k1}\frac{1}{(1x)^2}=\frac{2x}{(1x)^3} \text{using (*)}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k1}=\frac{2x}{(1x)^3}+\frac{1x}{(1x)^3}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k1}=\frac{1+x}{(1x)^3}[/math]
[math]x(\sum_{k=0}^{\infty} k^{2}x^{k1})=\frac{x(1+x)}{(1x)^3} \text{ (multiplying both sides by x)}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k}=\frac{x(1+x)}{(1x)^3}[/math]
Apologies if there are TeX mistakes, I'm not very good at it.
Re: How do I evaluate this infinite summation?
Wow, these are all really cool methods. It's cool how they apply to so many different functions.
Who is online
Users browsing this forum: No registered users and 11 guests