1989 USAMO Problems/Problem 1

Revision as of 20:58, 10 January 2008 by Azjps (talk | contribs) (cleanup)

Problem

For each positive integer $n$, let

$S_n = 1 + \frac 12 + \frac 13 + \cdots + \frac 1n$

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

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

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

Solution

If we re-group the terms of $T_{n-1}$,

\begin{align*} T_{n-1} &= \left(1\right) + \left(1 + \frac 12\right) + \left(1 + \frac 12 + \frac 13\right) + \ldots + \left(1 + \frac 12 + \frac 13 + \ldots + \frac 1{n-1}\right) \\  &= \sum_{i=1}^{n-1} \left(\frac {n-i}i\right) = n\left(\sum_{i=1}^{n-1} \frac{1}{i}\right) - (n-1) = n\left(\sum_{i=1}^{n} \frac{1}{i}\right) - n \\ &= n \cdot S_{n} - n\end{align*}

Thus, for $n = 1989$, $T_{1988} = 1989 S_{1989} - 1989 \Longrightarrow \boxed{a = b = 1989}$.

For the second part, applying this result gives

\begin{align*}U_{n-1} &= \sum_{i=2}^{n} \frac{T_{i-1}}{i} = \sum_{i=2}^{n}\ (S_{i} - 1) = T_{n-1} + S_n - (n-1) - S_1\\ &= \left(nS_n - n\right) + S_n - n = (n + 1)S_n - 2n\end{align*}

For $n = 1989$, we get that $\boxed{c = 1990, d = 2 \cdot 1989 = 3978}$.

See also

1989 USAMO (ProblemsResources)
Preceded by
First question
Followed by
Problem 2
1 2 3 4 5
All USAMO Problems and Solutions
Invalid username
Login to AoPS