Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1989 USAMO Problems/Problem 1"

(add solution)
(cleanup)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
For each positive integer <math>n</math>, let
+
For each positive [[integer]] <math>n</math>, let
 
<div style="text-align:center;">
 
<div style="text-align:center;">
 
<math>S_n = 1 + \frac 12 + \frac 13 + \cdots + \frac 1n</math>
 
<math>S_n = 1 + \frac 12 + \frac 13 + \cdots + \frac 1n</math>
Line 8: Line 8:
 
<math>U_n = \frac{T_1}{2} + \frac{T_2}{3} + \frac{T_3}{4} + \cdots + \frac{T_n}{n+1}</math>.
 
<math>U_n = \frac{T_1}{2} + \frac{T_2}{3} + \frac{T_3}{4} + \cdots + \frac{T_n}{n+1}</math>.
 
</div>
 
</div>
−
Find, with proof, integers <math>0 < a,\ b,\ c,\ d < 1000000</math> such that <math>\displaystyle T_{1988} = a S_{1989} - b</math> and <math>\displaystyle U_{1988} = c S_{1989} - d</math>.
+
Find, with proof, integers <math>0 < a,\ b,\ c,\ d < 1000000</math> such that <math>T_{1988} = a S_{1989} - b</math> and <math>U_{1988} = c S_{1989} - d</math>.
  
 
== Solution ==
 
== Solution ==
−
Let us prove that <math>\displaystyle T_{n-1} = nS_n - n</math>. Expanding:
+
If we re-group the terms of <math>T_{n-1}</math>,
  
−
:<math>\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</math>
+
<cmath>\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*}</cmath>
  
−
Grouping like terms, there are <math>n-1</math> <math>\displaystyle 1</math>s, <math>n-2</math> <math>\frac 12</math>s, and so on:
+
Thus, for <math>n = 1989</math>, <math>T_{1988} = 1989 S_{1989} - 1989 \Longrightarrow \boxed{a = b = 1989}</math>.
  
−
:<math>\left(\sum_{i=1}^{n-1} \frac 1i \cdot (n - i)\right) = n\left(\sum_{i=1}^n \frac 1i\right) - n</math>
+
For the second part, applying this result gives
−
:<math>\left(\sum_{I=1}^{n-1} \frac ni\right) - (n - 1)  =\left(\sum_{i=1}^n \frac ni\right) - n</math>
 
−
:<math>-(n-1) = n \cdot \frac 1n - n \Longrightarrow 1 - n = 1 - n</math>
 
  
−
which completes our proof. Thus, for <math>\displaystyle n = 1989</math>, we have that <math>\displaystyle T_{1988} = 1989 S_{1989} - 1989</math>, and so <math>a = b = 1989 \displaystyle</math>.
+
<cmath>\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*}</cmath>
  
−
For the second part, use our previously derived identity to determine <math>\displaystyle U_{n-1}</math> in terms of <math>\displaystyle S_n</math>. The problem simplifies to:
+
For <math>n = 1989</math>, we get that <math>\boxed{c = 1990, d = 2 \cdot 1989 = 3978}</math>.
−
 
 
−
:<math>U_{n-1} = \frac{2 S_2 - 2}{2} +  \frac{3 S_3 - 3}{3}  + \ldots + \frac{nS_{n} - n}{n}</math>
 
−
:<math>=S_2 + S_3 + \ldots S_{n} - (n - 1) + \left(S_1 - S_1\right)</math>
 
−
:<math>\displaystyle = T_{n-1} + S_n - (n-1)</math>
 
−
:<math>\displaystyle = \left(nS_n - n\right) + S_n - n + 1 - S_1</math>
 
−
:<math>\displaystyle = (n + 1)S_n - 2n</math>
 
−
 
 
−
Thus, we have <math>\displaystyle U_{n-1} = (n+1)S_n - 2n</math>. For <math>\displaystyle n = 1989</math>, we get that <math>\displaystyle c = 1990</math> and <math>d = 2 \cdot 1989 = 3978</math>
 
  
 
== See also ==
 
== See also ==

Revision as of 21:58, 10 January 2008

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 (Problems • Resources)
Preceded by
First question 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1989_USAMO_Problems/Problem_1&oldid=22303"