How do I evaluate this infinite summation?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Kurushimi
Posts: 841
Joined: Thu Oct 02, 2008 12:06 am UTC

How do I evaluate this infinite summation?

Postby Kurushimi » Sun Mar 27, 2011 6:15 pm UTC

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

greengiant
Posts: 272
Joined: Thu Jul 09, 2009 9:26 am UTC

Re: How do I evaluate this infinite summation?

Postby greengiant » Sun Mar 27, 2011 6:55 pm UTC

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 epsilon-delta 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)}{(1-x)^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).

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: How do I evaluate this infinite summation?

Postby antonfire » Sun Mar 27, 2011 7:05 pm UTC

Hint: how would you evaluate the integral x2/2x 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?

demon
Posts: 170
Joined: Tue Feb 06, 2007 8:13 pm UTC

Re: How do I evaluate this infinite summation?

Postby demon » Sun Mar 27, 2011 7:08 pm UTC

I don't know what level this is either, but I feel like it makes sense to point you to generating functions.
Spoiler:
Essentially the idea is to think of a function that can be represented as a series and that can be evaluated at a certain point to yield the actual series you're concerned with.

Example:
You must be familiar with the identity [imath]1 + x + x^2 + ... + x^n = \frac{1 - x^{n+1}}{1 - x}[/imath]. Through simple limit arguments you get that [imath]\Sigma_{n = 0}^{\infty}x^n = \frac{1}{1 - x}[/imath] where both expressions are well defined. Hence to evaluate the sum of a geometric series you can just plug the ratio into [imath]\frac{1}{1 - x}[/imath]

Now if you differentiate both sides of the first identity, you will obtain a closed form for [imath]\Sigma_{k = 0}^{k = n} (x^k)' = \Sigma_{k = 0}^{k = n} k x^{k - 1}[/imath].

It takes some care to prove that you can legally differentiate the infinite sum as well. Or that you can, in fact, do that twice and get basically the generating function of what you are looking for. But yeah, you absolutely can in this case. Try the free e-book generatingfunctionology by Herbert S. Wilf if you want to learn how to work with g.f.'s, it's a pretty pleasant read and gives some theory for differentiating power series (and also why you might not even care for differentiability in the analytic sense, since sometimes all you want can be determined from formal power series alone).

Anyway, generating functions are one of your best friends for infinite series.

User avatar
Kurushimi
Posts: 841
Joined: Thu Oct 02, 2008 12:06 am UTC

Re: How do I evaluate this infinite summation?

Postby Kurushimi » Sun Mar 27, 2011 7:23 pm UTC

This is just a highschool level maths competition. Nothing like epsilon-delta 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.

greengiant
Posts: 272
Joined: Thu Jul 09, 2009 9:26 am UTC

Re: How do I evaluate this infinite summation?

Postby greengiant » Sun Mar 27, 2011 7:26 pm UTC

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.
Spoiler:
Spoiler'd to match demon. demon didn't go into it, but [imath]\Sigma_{n = 0}^{\infty}x^n = \frac{1}{1 - x}[/imath] isn't valid for all values of x. In this example it's pretty straightforward to see where it holds, but in general I find it's a good idea to keep track of where your identity holds as you go along.


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.

User avatar
Eastwinn
Posts: 303
Joined: Thu Jun 19, 2008 12:36 am UTC
Location: Maryland

Re: How do I evaluate this infinite summation?

Postby Eastwinn » Sun Mar 27, 2011 8:03 pm UTC

greengiant wrote:Try the free e-book generatingfunctionology by Herbert S. Wilf if you want to learn how to work with g.f.'s


Wow, thanks for posting this :D
http://aselliedraws.tumblr.com/ - surreal sketches and characters.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: How do I evaluate this infinite summation?

Postby antonfire » Sun Mar 27, 2011 8:54 pm UTC

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.
The analogue of integration by parts for summations is called, as you might expect, summation by parts.

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?

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: How do I evaluate this infinite summation?

Postby Qaanol » Sun Mar 27, 2011 9:42 pm UTC

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:
[math]\begin{align}\sum_{k = 0}^{\infty}{\frac{k^2}{2^k}} &= \frac{1}{2} + \frac{4}{4} + \frac{9}{8} + \frac{16}{16} + \frac{25}{32} + \frac{49}{128} + \cdots \\
& \\
&= \left(\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots \right) + \left(\frac{3}{4} + \frac{3}{8} + \frac{3}{16} + \cdots \right) + \left(\frac{5}{8} + \frac{5}{16} + \frac{5}{32} + \cdots \right) + \cdots \\
& \\
&= \sum_{k = 0}^{\infty}{\left[(2k + 1)\sum_{n = k + 1}^{\infty}{\frac{1}{2^n}}\right]} \\
& \\
&= \sum_{k = 0}^{\infty}{\frac{2k + 1}{2^k}} \\
& \\
&= \frac{1}{1} + \frac{3}{2} + \frac{5}{4} + \frac{7}{8} + \cdots \\
& \\
&= \left(\frac{1}{1} + \frac{1}{2} + \frac{1}{4} + \cdots \right) + \left[\left(\frac{2}{2} + \frac{2}{4} + \frac{2}{8} + \cdots \right) + \left(\frac{2}{4} + \frac{2}{8} + \frac{2}{16} + \cdots \right) + \left(\frac{2}{8} + \frac{2}{16} + \frac{2}{32} + \cdots \right) \cdots \right] \\
& \\
&= \left(\sum_{k = 0}^{\infty}{\frac{1}{2^k}}\right) + \sum_{k = 0}^{\infty}{\left(2 \sum_{n = k+1}^{\infty}{\frac{1}{2^n}}\right)} \\
& \\
&= 2 + \sum_{k = 0}^{\infty}{2\frac{1}{2^k}}\\
\end{align}[/math]
wee free kings

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: How do I evaluate this infinite summation?

Postby antonfire » Mon Mar 28, 2011 5:07 am UTC

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?

Ankit1010
Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

Re: How do I evaluate this infinite summation?

Postby Ankit1010 » Mon Mar 28, 2011 7:56 am UTC

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]
Last edited by Ankit1010 on Mon Mar 28, 2011 7:58 am UTC, edited 1 time in total.

Ankit1010
Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

Re: How do I evaluate this infinite summation?

Postby Ankit1010 » Mon Mar 28, 2011 7:57 am UTC

[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}{1-r}[/math]
[math]K = \frac{1}{2}[/math]
where a is the first term, and r is the common ratio.

Which gives you S=6.

greengiant
Posts: 272
Joined: Thu Jul 09, 2009 9:26 am UTC

Re: How do I evaluate this infinite summation?

Postby greengiant » Mon Mar 28, 2011 9:19 am UTC

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}{1-x}[/math]
[math]\sum_{k=0}^{\infty} kx^{k-1}=\frac{1}{(1-x)^2} \text{ (by differentiating) (*)}[/math]
[math]\sum_{k=0}^{\infty} k(k-1)x^{k-2}=\frac{2}{(1-x)^3} \text{ (by differentiating)}[/math]
[math]\sum_{k=0}^{\infty} (k^2-k)x^{k-2}=\frac{2}{(1-x)^3}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k-2}-\sum_{k=0}^{\infty} kx^{k-2}=\frac{2}{(1-x)^3}[/math]
[math]x(\sum_{k=0}^{\infty} k^{2}x^{k-2}-\sum_{k=0}^{\infty} kx^{k-2})=\frac{2x}{(1-x)^3} \text{ (multiplying both sides by x)}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k-1}-\sum_{k=0}^{\infty} kx^{k-1}=\frac{2x}{(1-x)^3}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k-1}-\frac{1}{(1-x)^2}=\frac{2x}{(1-x)^3} \text{using (*)}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k-1}=\frac{2x}{(1-x)^3}+\frac{1-x}{(1-x)^3}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k-1}=\frac{1+x}{(1-x)^3}[/math]
[math]x(\sum_{k=0}^{\infty} k^{2}x^{k-1})=\frac{x(1+x)}{(1-x)^3} \text{ (multiplying both sides by x)}[/math]
[math]\sum_{k=0}^{\infty} k^{2}x^{k}=\frac{x(1+x)}{(1-x)^3}[/math]

Apologies if there are TeX mistakes, I'm not very good at it.

User avatar
Kurushimi
Posts: 841
Joined: Thu Oct 02, 2008 12:06 am UTC

Re: How do I evaluate this infinite summation?

Postby Kurushimi » Mon Mar 28, 2011 2:16 pm UTC

Wow, these are all really cool methods. It's cool how they apply to so many different functions.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 11 guests