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