Mathematical Food for Thought

  
 
 

  • About

    Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
  
Square Sum Stuff. Topic: Polynomials/S&S. Level: AMC/AIME. October 27th, 2006

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 .

Posted in AIME, AMC, Polynomials, Sequences & Series || 2 Comments »

2 Responses to “Square Sum Stuff. Topic: Polynomials/S&S. Level: AMC/AIME.”

  1. t0rajir0u Says:
    October 28th, 2006 at 10:07 pm

    The coefficients don’t have to be integer…

  2. paladin8 Says:
    October 28th, 2006 at 10:46 pm

    I suppose.

Leave a Reply

You must be logged in to post a comment.
Google

 

  
 
free web counters
Etronics