Difference between revisions of "1989 USAMO Problems/Problem 1"
(add solution) |
|||
Line 11: | Line 11: | ||
== Solution == | == Solution == | ||
− | {{ | + | Let us prove that <math>\displaystyle T_{n-1} = nS_n - n</math>. Expanding: |
+ | |||
+ | :<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> | ||
+ | |||
+ | 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: | ||
+ | |||
+ | :<math>\left(\sum_{i=1}^{n-1} \frac 1i \cdot (n - i)\right) = n\left(\sum_{i=1}^n \frac 1i\right) - n</math> | ||
+ | :<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>. | ||
+ | |||
+ | 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: | ||
+ | |||
+ | :<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 18:39, 11 April 2007
Problem
For each positive integer , let
.
Find, with proof, integers such that and .
Solution
Let us prove that . Expanding:
Grouping like terms, there are s, s, and so on:
which completes our proof. Thus, for , we have that , and so .
For the second part, use our previously derived identity to determine in terms of . The problem simplifies to:
Thus, we have . For , we get that and
See also
1989 USAMO (Problems • Resources) | ||
Preceded by First question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |