IMO 1985 · Problem 6

For every real number \(x_1\), construct the sequence \(x_1,x_2,\ldots\) by setting \[ x_{n+1}=x_n\left(x_n+\frac1n\right) \quad\text{for each }n\ge1. \] Prove that there exists exactly one value of \(x_1\) for which \[ 0<x_n<x_{n+1}<1 \] for every \(n\).

Official text of the problem. Official problem paper (PDF)

Solution

Put \[ \ell_n=1-\frac1n,\qquad f_n(t)=t\left(t+\frac1n\right). \] For \(t>0\), we have \[ f_n(t)>t\quad\Longleftrightarrow\quad t>\ell_n. \] Thus the required inequalities are equivalent to \[ \ell_n<x_n<1\qquad\text{for every }n\ge1. \tag{1} \]

Existence. Each \(f_n\) is continuous and strictly increasing on \([0,\infty)\): if \(0\le u<v\), then \[ f_n(v)-f_n(u)=(v-u)\left(u+v+\frac1n\right)>0. \] Moreover, \[ f_n(\ell_n)=\ell_n<\ell_{n+1}, \qquad f_n(1)=1+\frac1n>1. \tag{2} \] Consequently, for every \(y\in[\ell_{n+1},1]\), there is a unique \(t\in(\ell_n,1)\) such that \(f_n(t)=y\).

For each positive integer \(N\), construct a finite sequence backwards by setting \[ z_N^{(N)}=1,\qquad f_n\bigl(z_n^{(N)}\bigr)=z_{n+1}^{(N)} \quad(n=N-1,\ldots,1), \] always taking the positive solution. By (2), this construction is possible and satisfies \[ \ell_n<z_n^{(N)}<1\qquad(1\le n<N). \tag{3} \] Write \(a_N=z_1^{(N)}\). Since \[ z_N^{(N+1)}<1=z_N^{(N)}, \] strict monotonicity of the functions \(f_n\), applied successively backwards, gives \[ a_{N+1}<a_N. \] The sequence \((a_N)\) is positive and decreasing, so it has a limit \(a\ge0\).

Let \((x_n)\) be the sequence in the problem with \(x_1=a\). For every fixed \(n\), the \(n\)-th term is a polynomial, hence a continuous function, of the first term. Therefore \[ x_n=\lim_{N\to\infty}z_n^{(N)}. \] Taking limits in (3) gives \[ \ell_n\le x_n\le1\qquad(n\ge1). \tag{4} \]

Both bounds are strict. Indeed, if \(x_n=\ell_n\), then \[ x_{n+1}=f_n(\ell_n)=\ell_n<\ell_{n+1}, \] contradicting (4). If \(x_n=1\), then \[ x_{n+1}=1+\frac1n>1, \] again contradicting (4). Thus (1) holds, proving existence.

Uniqueness. Suppose two distinct initial values produce sequences \((u_n)\) and \((v_n)\) satisfying the required inequalities. Interchanging them if necessary, assume \(u_1<v_1\). Strict monotonicity of \(f_n\) gives \(u_n<v_n\) for every \(n\).

Set \(d_n=v_n-u_n>0\). By (1), \[ d_{n+1} =\left(u_n+v_n+\frac1n\right)d_n >d_n, \] because \(u_n+\frac1n>1\) and \(v_n>0\). Hence \(d_n\ge d_1>0\) for every \(n\). But (1) also yields \[ 0<d_n=v_n-u_n<1-\ell_n=\frac1n, \] which is impossible for sufficiently large \(n\). Therefore the initial value is unique.

The solution was checked against John Scholes' IMO solution archive (Kalva).