Saturday, October 14, 2006

Sumthing's Up. Topic: Algebra/S&S. Level: AIME.

Problem: (1994 Putnam - A1) Suppose that a sequence $ a_1, a_2, a_3, \ldots $ satisfies $ 0 < a_n \le a_{2n}+a_{2n+1} $ for all $ n \ge 1 $. Prove that the series $ \displaystyle \sum_{n=1}^{\infty} a_n $ diverges.

Solution: Well, let's see. $ a_1 $ is an arbitrary constant. Then

$ a_2+a_3 \ge a_1 $

$ (a_4+a_5)+(a_6+a_7) \ge a_2+a_3 \ge a_1 $.

Whoa, that looks like a pattern... Indeed, by induction we can show that

$ S_k = (a_{2^k}+a_{2^k+1})+(a_{2^k+2}+a_{2^k+3})+\cdots+(a_{2^{k+1}-2}+a_{2^{k+1}-1}) \ge S_{k-1} $

for $ k \ge 1 $ and $ S_0 = a_1 $, so

$ \displaystyle \sum_{n=1}^{\infty} a_n = \sum_{k=1}^{\infty} S_k \ge \sum_{k=1}^{\infty} a_1 $,

which clearly diverges. QED.


Comment: Pretty interesting and easy problem, though from the scores evidently a lot of people missed some minor error in rigor (59 people got 9/10, and also 59 people got a full score). In any case, this is a good concept for infinite series, and should be familiar to most people who do math a lot (a.k.a. if you are familiar with the following practice problem).


Practice Problem: Without calculus, show that $ \displaystyle \sum_{n=1}^{\infty} \frac{1}{n} $ diverges.


  1. We make the opposite assumption, that it converges. Let O be the sum of the reciprocal of the odds, and let E be the sum of the reciprocal of the evens. (These are both guaranteed to be finite since they are both less than the sum of the reciprocal of the positive integers, given our assumption.)

    Obvoiusly O > E. However, E = 1/2 (O + E), which implies O = E. Contradiction.

  2. Now that's an unconvential proof...

  3. Not really. I've seen it used in some books.