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