1989 USAMO Problems/Problem 1

Revision as of 18:39, 11 April 2007 by Azjps (talk | contribs) (add solution)

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 $\displaystyle T_{1988} = a S_{1989} - b$ and $\displaystyle U_{1988} = c S_{1989} - d$.

Solution

Let us prove that $\displaystyle T_{n-1} = nS_n - n$. Expanding:

$\left(1\right) + \left(1 + \frac 12\right) + \ldots + \left(1 + \frac 12 + \frac 13 + \ldots + \frac 1n\right) = n\left(\sum_{i=1}^n \frac 1i\right) - n \displaystyle$

Grouping like terms, there are $n-1$ $\displaystyle 1$s, $n-2$ $\frac 12$s, and so on:

$\left(\sum_{i=1}^{n-1} \frac 1i \cdot (n - i)\right) = n\left(\sum_{i=1}^n \frac 1i\right) - n$
$\left(\sum_{I=1}^{n-1} \frac ni\right) - (n - 1)  =\left(\sum_{i=1}^n \frac ni\right) - n$
$-(n-1) = n \cdot \frac 1n - n \Longrightarrow 1 - n = 1 - n$

which completes our proof. Thus, for $\displaystyle n = 1989$, we have that $\displaystyle T_{1988} = 1989 S_{1989} - 1989$, and so $a = b = 1989 \displaystyle$.

For the second part, use our previously derived identity to determine $\displaystyle U_{n-1}$ in terms of $\displaystyle S_n$. The problem simplifies to:

$U_{n-1} = \frac{2 S_2 - 2}{2} +  \frac{3 S_3 - 3}{3}  + \ldots + \frac{nS_{n} - n}{n}$
$=S_2 + S_3 + \ldots S_{n} - (n - 1) + \left(S_1 - S_1\right)$
$\displaystyle = T_{n-1} + S_n - (n-1)$
$\displaystyle = \left(nS_n - n\right) + S_n - n + 1 - S_1$
$\displaystyle = (n + 1)S_n - 2n$

Thus, we have $\displaystyle U_{n-1} = (n+1)S_n - 2n$. For $\displaystyle n = 1989$, we get that $\displaystyle c = 1990$ and $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