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$.
2. U_n + n = T_{n+1} - 1 = T_n + S_{n+1} - 1, and the problem is to show that this is always
ReplyDeleteI keep getting cut off. X.x ln(n+1) > S_{n+1} - 1 by integrals. Q.E.D. =P
ReplyDelete