Add Them Up. Topic: Sequences & Series. Level: AIME/Olympiad.

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