Friday, September 22, 2006

Infinite... POWER! Topic: Algebra/Inequalities/S&S. Level: AIME/Olympiad.

Problem: (2000 Putnam - A1) Let $ A $ be a positive real number. What are the possible values of $ \displaystyle \sum_{j=0}^{\infty} x_j^2 $, given that $ x_0, x_1, \ldots $ are positive numbers such that $ \displaystyle \sum_{j=0}^{\infty} x_j = A $?

Solution: First, we will try to guess what the range is using inequalities. We obviously have

$ \displaystyle \sum x_j^2 > 0 $

because all the $ x_j $ are positive. Also,

$ \displaystyle \sum x_j^2 < \left(\sum x_j\right)^2 = A^2 $

by "expansion" (infinitely, but that's ok). So for now, our guess is the interval $ (0, A^2) $. We want to show that given any $ \alpha \in (0, A^2) $ we can make a sequence such that $ \displaystyle \sum x_j = A $ and $ \displaystyle \sum x_j^2 = \alpha $. Well, we like easy sequences so consider if $ x_j $ is a geometric sequence with common ratio $ r $. Then

$ \displaystyle \sum x_j = \frac{x_0}{1-r} = A $.

We want to show that given any $ \alpha $, we can find a positive real $ r $ satisfying $ r < 1 $, the above equation, and

$ \displaystyle \sum x_j^2 = \frac{x_0^2}{1-r^2} = \alpha $.

Rewriting the two equations (and squaring the first), we have

$ x_0^2 = A^2(1-r)^2 = \alpha(1-r^2) $

so

$ (A^2+\alpha)r^2-(2A^2)r+(A^2-\alpha) $

$ (r-1)[(A^2+\alpha)r-(A^2-\alpha)] $.

Since we want $ |r| < 1 $, we must use the second factor, which gives us

$ r = \frac{A^2-\alpha}{A^2+\alpha} $.

But if $ \alpha \in (0, A^2) $, clearly $ A^2 - \alpha < A^2 + \alpha \Rightarrow \frac{A^2-\alpha}{A^2+\alpha} < 1 $, so there exists some positive ratio such that $ \displaystyle \sum x_j = A $ and $ \displaystyle \sum x_j^2 = \alpha $. Hence the possible values are $ (0, A^2) $. QED.

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

Comment: A surprisingly difficult A1 problem on a Putnam; it had less perfect scores than A2, B1, and B2 (which will probably be posted over the next week or so). It required some experience with inequalities to guess the range and then a clever assumption of a geometric series to complete the proof.

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

Practice Problem: What if the terms could be any nonzero real? What are the possible values of $ \displaystyle \sum x_j^2 $ then?

1 comment: