Monday, November 28, 2005

Problem: (1989 USAMO - #1) For each positive integer $n$, let

$S_n = 1+\frac{1}{2}+ \cdots + \frac{1}{n}$

$T_n = S_1+S_2+ \cdots + S_n$

$U_n = \frac{T_1}{2}+\frac{T_2}{3} +\cdots + \frac{T_n}{n+1}$

Find, with proof, integers $0 < a,b,c,d < 1000000$ such that $T_{1988} = aS_{1989}-b$ and $U_{1988} = cS_{1989}-d$.

Solution: Well let's start with the first condition - $T_{1988} = aS_{1989}-b$. We claim that

$T_n = (n+1)(S_{n+1}-1)$.

Consider writing $T_n$ as sum of the following sequences:

$S_1 = 1$
$S_2 = 1+\frac{1}{2}$
...
$S_n = 1+\frac{1}{2}+ \cdots +\frac{1}{n}$.

Notice that $1$ appears $n$ times, $\frac{1}{2}$ appears $n-1$ times, and more generally $\frac{1}{i}$ appears $n+1-i$ times. Then we can say

$\displaystyle T_n = \sum_{i=1}^n \frac{n+1-i}{i} = (n+1)\sum_{i=1}^n \frac{1}{i} - \sum_{i=1}^n 1 = (n+1)S_n-n = (n+1)\left(S_{n+1}-\frac{1}{n+1}\right)-n = (n+1)(S_{n+1}-1)$

as claimed. Also, save the fact that $T_n = (n+1)S_n - n$.

So then $T_{1988} = 1989(S_{1989}-1) = 1989S_{1989}-1989 \Rightarrow a = b = 1989$.

Now, using $T_n = (n+1)(S_{n+1}-1)$, we substitute into the $U_n$ equation to get

$\displaystyle U_n = \sum_{i=1}^n \frac{T_n}{n+1} = \sum_{i=1}^n \frac{(n+1)(S_{n+1}-1)}{n+1} = \sum_{i=1}^n S_{n+1} - \sum_{i=1}^n 1 = \sum_{i=1}^n S_{n+1} - n$.

But recall that $\displaystyle \sum_{i=1}^n S_{n+1} = T_{n+1}-1$ and remember the fact we saved back up there, so our final equation becomes

$U_n = T_{n+1}-(n+1) = (n+2)S_{n+1}-(n+1)-(n+1) = (n+2)S_{n+1}-2(n+1)$.

So $U_{1988} = 1990S_{1989}-3978 \Rightarrow c = 1990, d = 3978$.

Thus our final answer is $a = 1989, b = 1989, c = 1990, d = 3978$. QED.

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

Comment: This was back in 1989, when the USAMO was a one-day, $3 \frac{1}{2}$ hour test with five problems. Not until 1996 did it become a two-day test.

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

Practice Problem #1: Do the problem again with $T_{2005}$ and $U_{2005}$ instead, to fully understand the solution.

Practice Problem #2: Show that $T_n+\ln{(n+1)} > U_n+n$ for all positive integers $n$.