## Friday, October 27, 2006

### Square Sum Stuff. Topic: Polynomials/S&S. Level: AMC/AIME.

Problem: Evaluate the summation

$\displaystyle \sum_{k=1}^{\infty} \frac{k^2}{2^k} = \frac{1^2}{2^1}+\frac{2^2}{2^2}+\frac{3^2}{2^3}+\frac{4^2}{2^4}+\cdots$.

Solution: Here's a technique that will help you evaluate infinite series that are of the form polynomial over exponential. It's based on the idea of finite differences:

If $P$ is a polynomial with integer coefficients of degree $n$ then

$P(x+1)-P(x)$

is a polynomial of degree $n-1$ (not hard to show; just think about it).

So let

$S = \frac{1^2}{2^1}+\frac{2^2}{2^2}+\frac{3^2}{2^3}+\frac{4^2}{2^4}+\cdots$.

Then consider $2S$ by simply multiplying each term by $2$:

$2S = 1^2+\frac{2^2}{2^1}+\frac{3^2}{2^2}+\frac{4^2}{2^3}+\cdots$.

And now find the difference $2S-S = S$ by subtracting the terms with equal denominators. We get

$S = 2S-S = 1+\frac{2^2-1^2}{2^1}+\frac{3^2-2^2}{2^2}+\frac{4^2-3^2}{2^3}+\cdots$

$S = 1+\frac{3}{2^1}+\frac{5}{2^2}+\frac{7}{2^3}+\cdots$.

Notice that the numerator is now a polynomial of degree $1$ instead of $2$. Repeating this, we have

$2S = 2+3+\frac{5}{2^1}+\frac{7}{2^2}+\cdots$

and

$S = 2S-S = 2 + 2 + \frac{5-3}{2^1}+\frac{7-5}{2^2}+\cdots$

$S = 2 + (2 + 1+\frac{1}{2}+\cdots)$.

Notice that the latter part is just a geometric series which sums to

$2 + 1 + \frac{1}{2} + \cdots = 4$

so $S = 2+4 = 6$. QED.

--------------------

Comment: The method of finite differences is extremely useful and is basically a simplified version of calculus - $P(x+1)-P(x) \approx P^{\prime}(x)$ in a very approximating sense. It's a good thing to know, though, because then you have a better understanding of how polynomials work.

--------------------

Practice Problem: Let $P$ be a polynomial with integer coefficients. Using the method of finite differences, predict the degree of $P$.

$P(1) = 1 \mbox{ } P(2) = 9 \mbox{ } P(3) = 20 \mbox{ } P(4) = 36 \mbox{ } P(5) = 59 \mbox{ } P(6) = 91$.