Maths Olympiad Prep

Library / /148 of 520

Algebra Difficulty 6.0 National olympiad Prove it

1. A1 (USA) Let a0=1994 a_{0} = 1994 and an+1=an2an+1 a_{n+1} = \frac{a_{n}^{2}}{a_{n} + 1} for each nonnegative integer n n . Prove that 1994n 1994 - n is the greatest integer less than or equal to an a_{n} , 0n998 0 \leq n \leq 998 .

Solution

1. Obviously a0>a1>a2>a_{0}>a_{1}>a_{2}>\cdots. Since akak+1=11ak+1a_{k}-a_{k+1}=1-\frac{1}{a_{k}+1}, we have an=a0+(a1a0)++(anan1)=1994n+1a0+1++1an1+1>a_{n}=a_{0}+\left(a_{1}-a_{0}\right)+\cdots+\left(a_{n}-a_{n-1}\right)=1994-n+\frac{1}{a_{0}+1}+\cdots+\frac{1}{a_{n-1}+1}> 1994n1994-n. Also, for 1n9981 \leq n \leq 998,
1a0+1++1an1+1<1. \frac{1}{a_{0}+1}+\cdots+\frac{1}{a_{n-1}+1} < 1.
Hence,
an<1995n. a_{n} < 1995 - n.
For 999n1993999 \leq n \leq 1993,
1a0+1++1an1+1>1. \frac{1}{a_{0}+1}+\cdots+\frac{1}{a_{n-1}+1} > 1.
Thus,
an<1994n. a_{n} < 1994 - n.
For n=1994n = 1994,
1a0+1++1a1993+1=1. \frac{1}{a_{0}+1}+\cdots+\frac{1}{a_{1993}+1} = 1.
Therefore,
a1994=0. a_{1994} = 0.
For n1995n \geq 1995,
1a0+1++1an1+1>1. \frac{1}{a_{0}+1}+\cdots+\frac{1}{a_{n-1}+1} > 1.
Hence,
an<1994n. a_{n} < 1994 - n.
In summary, for 1n9981 \leq n \leq 998,
an=1994n. \left\lfloor a_{n} \right\rfloor = 1994 - n.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.