uniolympiads Ελληνικά

IMC 1996, Day 2, Problem 1

Prove that if f ⁣:[0,1]→[0,1]f\colon [0, 1] \to [0, 1] is a continuous function, then the sequence of iterates xn+1=f(xn)x_{n+1} = f(x_n) converges if and only if

lim⁡n→∞(xn+1−xn)=0.\lim_{n \to \infty} (x_{n+1} - x_n) = 0.
Original from the official PDFProve that if f : [0, 1] → [0, 1] is a continuous function, then the sequence of iterates x n+1 = f (x n ) converges if and only if lim (x n+1 − x n ) = 0. n→∞

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. The “only if” part is obvious. Now suppose that lim⁡n→∞(xn+1−xn)=0\lim\limits_{n\to\infty} (x_{n+1} - x_n) = 0 and the sequence {xn}\{x_n\} does not converge. Then there are two cluster points K<LK < L. There must be points from the interval (K,L)(K, L) in the sequence. There is an x∈(K,L)x \in (K, L) such that f(x)≠xf(x) \neq x. Put ε=∣f(x)−x∣2>0\varepsilon = \dfrac{|f(x) - x|}{2} > 0. Then from the continuity of the function ff we get that for some δ>0\delta > 0 for all y∈(x−δ,x+δ)y \in (x - \delta, x + \delta) it is ∣f(y)−y∣>ε|f(y) - y| > \varepsilon. On the other hand for nn large enough it is ∣xn+1−xn∣<2δ|x_{n+1} - x_n| < 2\delta and ∣f(xn)−xn∣=∣xn+1−xn∣<ε|f(x_n) - x_n| = |x_{n+1} - x_n| < \varepsilon. So the sequence cannot come into the interval (x−δ,x+δ)(x - \delta, x + \delta), but also cannot jump over this interval. Then all cluster points have to be at most x−δx - \delta (a contradiction with LL being a cluster point), or at least x+δx + \delta (a contradiction with KK being a cluster point).

Transcribed from the official solutions, pages 9–10. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?