## How do I evaluate this infinite summation?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

### How do I evaluate this infinite summation?

$\sum_{k=0}^{\infty}\frac{k^2}{2^k}$

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?

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

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

### Re: How do I evaluate this infinite summation?

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?

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.

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

### Re: How do I evaluate this infinite summation?

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?

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.

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

### Re: How do I evaluate this infinite summation?

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
http://aselliedraws.tumblr.com/ - surreal sketches and characters.

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

### Re: How do I evaluate this infinite summation?

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?

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

### 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:
\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}
wee free kings

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

### 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?

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

### Re: How do I evaluate this infinite summation?

This is the generating functions approach to the problem. Very useful for any summation.

$\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*}$
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?

$\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*}$

K is just an infinite geometric series, so:
$K = \frac{a}{1-r}$
$K = \frac{1}{2}$
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?

A different way to get the more general result, starting from the sum to infinity of a geometric series (valid for |x|<1)
$\sum_{k=0}^{\infty} x^k=\frac{1}{1-x}$
$\sum_{k=0}^{\infty} kx^{k-1}=\frac{1}{(1-x)^2} \text{ (by differentiating) (*)}$
$\sum_{k=0}^{\infty} k(k-1)x^{k-2}=\frac{2}{(1-x)^3} \text{ (by differentiating)}$
$\sum_{k=0}^{\infty} (k^2-k)x^{k-2}=\frac{2}{(1-x)^3}$
$\sum_{k=0}^{\infty} k^{2}x^{k-2}-\sum_{k=0}^{\infty} kx^{k-2}=\frac{2}{(1-x)^3}$
$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)}$
$\sum_{k=0}^{\infty} k^{2}x^{k-1}-\sum_{k=0}^{\infty} kx^{k-1}=\frac{2x}{(1-x)^3}$
$\sum_{k=0}^{\infty} k^{2}x^{k-1}-\frac{1}{(1-x)^2}=\frac{2x}{(1-x)^3} \text{using (*)}$
$\sum_{k=0}^{\infty} k^{2}x^{k-1}=\frac{2x}{(1-x)^3}+\frac{1-x}{(1-x)^3}$
$\sum_{k=0}^{\infty} k^{2}x^{k-1}=\frac{1+x}{(1-x)^3}$
$x(\sum_{k=0}^{\infty} k^{2}x^{k-1})=\frac{x(1+x)}{(1-x)^3} \text{ (multiplying both sides by x)}$
$\sum_{k=0}^{\infty} k^{2}x^{k}=\frac{x(1+x)}{(1-x)^3}$

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

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

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