IMO 1975 SL 14

Origin: YUG

Problem

Let x0 = 5 and xn+1 = xn + xn (n = 0, 1, 2, . . .). Prove that 45 < x1000 < 45, 1.

Solution

We shall prove that for every n \inN, \sqrt2n + 25 \leqxn \leq\sqrt2n + 25 + 0.1. Note that for n = 1000 this gives us exactly the desired inequalities.

First, notice that the recurrent relation is equivalent to 2xk(xk+1 −xk) = 2. (1) Since x0 < x1 < \cdot \cdot \cdot < xk < \cdot \cdot \cdot , from (1) we get x2 k+1 −x2 k = (xk+1 + xk)(xk+1 −xk) > 2. Adding these up we obtain x2 n \geqx2 0 + 2n, which proves the first inequality. On the other hand, xk+1 = xk + xk \leqxk + 0.2 (for xk \geq5), and one also deduces from (1) that x2 k+1 −x2 k −0.2(xk+1 −xk) = (xk+1 + xk − 0.2)(xk+1−xk) \leq2. Again, adding these inequalities up, (k = 0, . . . , n−1) yields x2 n \leq2n + x2 0 + 0.2(xn −x0) = 2n + 24 + 0.2xn. Solving the corresponding quadratic equation, we obtain xn < 0.1 + \sqrt2n + 24.01 < 0.1+ +\sqrt2n + 25.