For each positive integer $n$, let \begin{eqnarray*} 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}. \end{eqnarray*} 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$.
Problem
Source: USAMO1989
Tags: number theory solved, number theory
bubala
08.11.2005 00:53
a=1989, b=1989, c=1990, d=3978.
Proof. First we show that $T_{n-1}=nS_n-n$ by induction.
The base case, n=2, is trivial.
We must show that if $T_{n-1}=nS_n-n$, then $T_n=(n+1)S_{n+1}-(n+1)$
$T_n=S_1+...+S_{n-1}+S_n=T_{n-1}+S_n=nS_n-n+S_n=(n+1)S_n-n$.
$S_n=S_{n+1}-\frac{1}{n+1}$, so
$T_n=(n+1)(S_{n+1}-\frac{1}{n+1})-n=(n+1)S_{n+1}-(n+1)$
Therefore, a=b=1989.
$U_n=\frac{T_1}{2}+...+\frac{T_n}{n+1}=\frac{2S_2-2}{2}+\frac{(n+1)S_{n+1}-(n+1)}{n+1}=S_2-1+...+S_{n+1}-1=S_2+ S_{n+1}-n=S_1+...+S_{n+1}-(n+1)=T_{n+1}-(n+1)=(n+2)S_{n+2}-(n+2)-(n+1)=(n+2)(S_{n+1}+\frac{1}{n+2})-2n-3=(n+2)S_{n+1}+1-2n-3=(n+2)S_{n+1}-(2n+2)$
Therefore, c=1990 and d=3978.
chess64
13.11.2005 17:19
We know that
\begin{eqnarray*} T_{1988} &=& 1 + \left(1 + \frac{1}{2}\right) + \left(1+\frac{1}{2}+\frac{1}{3}\right) + \cdots + \left(1+\frac{1}{2}+ \cdots + \frac{1}{1988}\right) \\ &=& 1(1988) + \frac{1}{2} (1987) + \frac{1}{3}(1986) + \cdots + \frac{1}{1987}(2) +\frac{1}{1988}(1)\\ &=& \sum_{k=1}^{1988} \frac{1989-k}{k}\\ &=& \sum_{k=1}^{1988} \left( \frac{1989}{k}-1 \right)\\ &=& -1988 + 1989 \cdot \sum_{k=1}^{1988} \frac{1}{k}\\ &=& -1988 + 1989 \cdot S_{1988}\\ \end{eqnarray*}
Since $S_{1989} = S_{1988} + \frac{1}{1989}$, we have
\begin{eqnarray*} T_{1988} &=& -1988 + 1989 \cdot \left( S_{1989} - \frac{1}{1989} \right) \\ &=& -1989 + 1989S_{1989}\\ \end{eqnarray*}
Thus $a=b=1989$.
Generalizing for any positive integer $n$, we can say that \[ T_n = S_{n+1}(n+1)-(n+1) = (S_{n+1}-1)(n+1) . \] We can prove this by induction. For $n=1$, we have \[ T_1 = 2(S_{2}-1) = 2\left( 1 + \frac{1}{2} - 1 \right) = 1, \] as desired. Now assume $T_k = (k+1)(S_{k+1}-1)$ for all $k$; thus it must be true for $k+1$ as well:
\begin{eqnarray*} T_{k+1} &=& (k+2)(S_{k+2}-1)\\ T_{k} + S_{k+1} &=& (k+2)(S_{k+1} + \frac{1}{k+2}-1)\\ (k+1)(S_{k+1}-1) + S_{k+1} &=& (k+2)(S_{k+1} - \frac{k+1}{k+2})\\ k \cdot S_{k+1} - k + S_{k+1} - 1 + S_{k+1} &=& (k+2)(S_{k+1} - \frac{k+1}{k+2})\\ S_{k+1}(k+2) - k - 1 &=& (k+2)S_{k+1} - (k+1)\\ S_{k+1}(k+2) &=& (k+2)S_{k+1}\\ \end{eqnarray*}
And thus our assertion that $T_n = (n+1)(S_{n+1}-1)$ holds for all positive integers $n$. Hence,
\begin{eqnarray*} U_{1988} &=& \sum_{k=1}^{1988} \frac{T_k}{k+1} \\ &=& \sum_{k=1}^{1988} \frac{(S_{k+1}-1)(k+1)}{k+1} \\ &=& \sum_{k=1}^{1988} (S_{k+1}-1) \\ &=& -1988+\sum_{k=1}^{1988} S_{k+1} \\ &=& -1988+\left( \sum_{k=1}^{1988} S_{k} \right) + S_{1989}-S_1 \\ &=& -1989+T_{1988} + S_{1989} \\ &=& -1989+ 1989(S_{1989}-1) + S_{1989} \\ &=& 1990S_{1989}-3978\\ \end{eqnarray*}
So $c=1990$, $d=3978$.