Maths Olympiad Prep

Library / /24 of 45

Algebra Difficulty 5.7 AIME, harder Prove it Romania

xn+1=∣xn−1n∣,for n≥1. x_{n+1} = \left| x_n - \frac{1}{n} \right|, \quad \text{for } n \ge 1.
Prove that it has a finite limit, and calculate it.

Solution

Let NN be an arbitrary positive integer. There exists a least k∈Nk \in \mathbb{N} such that xN<1N+1N+1+⋯+1N+kx_N < \frac{1}{N} + \frac{1}{N+1} + \dots + \frac{1}{N+k}, since the harmonic series is divergent. Then xN+k=xN−(1N+⋯+1N+k−1)<1N+k≤1Nx_{N+k} = x_N - \left(\frac{1}{N} + \dots + \frac{1}{N+k-1}\right) < \frac{1}{N+k} \le \frac{1}{N}. Also xn<1Nx_n < \frac{1}{N} for n≥N+kn \ge N+k. The proof is by simple induction, since xn+1=∣xn−1n∣x_{n+1} = \left|x_n - \frac{1}{n}\right|, and if xn>1nx_n > \frac{1}{n}, then xn+1=xn−1n<xn<1Nx_{n+1} = x_n - \frac{1}{n} < x_n < \frac{1}{N}, while if xn≤1nx_n \le \frac{1}{n}, then xn+1=1n−xn≤1n<1Nx_{n+1} = \frac{1}{n} - x_n \le \frac{1}{n} < \frac{1}{N}.

Therefore for any NN there exists N1N_1 such that 0≤xn<1N0 \le x_n < \frac{1}{N} for n≥N1n \ge N_1, which means the sequence converges to 00.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.