1985 IMO Problems/Problem 6

Problem

For every real number $x_1$ , construct the sequence $x_1,x_2,\ldots$ by setting $x_{n+1}=x_n \left(x_n + \frac{1}{n}\right)$ for each $n \geq 1$ . Prove that there exists exactly one value of $x_<x_n<x_{n+1}<1$ for every $n$ .

Solution 1

By recursive substitution, one can write $x_n=P_n(x_1)$ , where $P_n$ is a polynomial with non-negative coefficients and zero constant term. Thus, $P_n(0)=0$ , $P_n$ is strictly increasing in $[0,+\infty)$ , and $\displaystyle \lim_{x_1 \rightarrow + \infty} P_n(x_1)=+\infty$ . We can therefore define the inverse $P_n^{-1}$ of $P_n$ on $[0,+\infty)$ . It follows that $x_1=P_n^{-1}(x_n)$ , $P_n^{-1}(0)=0$ , $P_n^{-1}$ is strictly increasing in $[0,+\infty)$ , and $\displaystyle \lim_{x_1 \rightarrow + \infty} P_n^{-1}(x_1) =+\infty$ .

Denote by $\displaystyle a_n=P_n^{-1}(1-\frac{1}{n})$ and $b_n=P_n^{-1}(1)$ . By the monotonicity of $P_n^{-1}$ we have $a_n<b_n$ for each $n$ . Note that:

(a) $\displaystyle x_n<x_{n+1} \Leftrightarrow x_n>1-\frac{1}{n} \Leftrightarrow P_n^{-1}(x_n)>P_n^{-1}(1-\frac{1}{n}) \Leftrightarrow x_1>a_n$ ; (b) $\displaystyle x_n<1 \Leftrightarrow P_n^{-1}(x_n)<P_n^{-1}(1) \Leftrightarrow x_1<b_n$ .

Thus, $0<x_n<x_{n+1}<1,\forall n$ holds if and only if $a_n<x_1<b_n,\forall n$ , or $\displaystyle x_1 \in \bigcap_{n=1}^{+\infty}(a_n,b_n)$ . We need to show that $\displaystyle \bigcap_{n=1}^{+\infty}(a_n,b_n)$ is a singleton. We have:

(c) if $x_1=a_n$ , then $x_n=1-\frac{1}{n}$ , which implies that $x_{n+1}=1-\frac{1}{n}<1-\frac{1}{n+1}=P_{n+1}(a_{n+1})$ , and $x_1<a_{n+1}$ . It follows that $a_n<a_{n+1},\forall n$ ; and (d) if $x_1=b_n$ , then $x_n=1$ , which implies that $x_{n+1}=1+\frac{1}{n}>1=P_{n+1}(b_{n+1})$ , and $x_1>b_{n+1}$ . It follows that $b_n>b_{n+1},\forall n$ ; and

Thus, $a_n<a_{n+1}<b_{n+1}<b_n, \forall n$ . Therefore, the two sequences $\{a_n\}_{n=1}^{+\infty}$ and $\{b_n\}_{n=1}^{+\infty}$ converge, and their limits $a$ and $b$ satisfy $a \leq b$ . Hence, $\displaystyle \bigcap_{n=1}^{+\infty}(a_n,b_n)=[a,b]$ is non-empty, which demonstrates the existence of $x_1$ .

Now, suppose that $a \leq x_1 \leq x_1' \leq b$ . We have $x_{n+1}'-x_{n+1} = (x_n'-x_n)(x_n'+x_n+\frac{1}{n}) \geq (x_n'-x_n)(2-\frac{1}{n}) \geq (x_n'-x_n)$ for each $n$ , so that $x_n'-x_n \geq x_1'-x_1$ for each $n$ . However, $1-\frac{1}{n}<x_n \leq x_n'<1$ , so that $0 \leq x_n'-x_n<\frac{1}{n}$ , which implies that $\displaystyle \lim_{n \rightarrow +\infty}(x_n'-x_n)=0$ . Therefore, $x_1' \leq x_1$ , proving unicity.

This solution was posted and copyrighted by DAFR. The original thread for this problem can be found here: [1]

Solution 2

For each $n \ge 1$ let $I_n$ be the interval of real numbers $0 \textless x \textless 1$ such that if $x=x_1$ , we will have $x_n \textless x_{n+1} \textless 1$ . (That is, the values of $x_1$ which make $x_{n+1}$ "work"). We must prove these intervals intersect at one point.

First, I prove they intersect. Notice that as $x_1$ increases, $x_n$ and $x_{n+1}$ do too. So if $I_n=(a_n,b_n)$ it is easy to see $a_n=x_1$ will give $x_n=x_{n+1}=1-1/n$ and $b_n=x_1$ will give $x_{n+1}=1$ (the "extremal" values $x_{n+1}$ can take are given by the extremal values $x_1$ can take).

But if $a_n=x_1$ we see that $x_{n+1} \textless 1-1/(n+1)$ and so $x_{n+1} \textgreater x_{n+2}$ and similarly $x_1=b_n$ gives $x_{n+1}=1$ which gives a $x_{n+2}$ too big. So basically when $x_1$ only barely works for $x_{n+1}$ , it won't work for $x_{n+2}$ . So $I_{n+1}$ is a subset of $I_n$ .

So we have an infinite sequence of open intervals, each contained inside the previous one. Therefore their intersection must contain at least one number. This guarantees the existence of $x_1$ .

But, we must prove that $x_1$ can't take two different values. Suppose it could. Suppose $x_1=a,b$ both work. Let $x_i$ be the sequence generated by $a$ and $x_i'$ the sequence generated by $b$ , and let $l_i=x_i'-x_i$ (wlog $a \textless b$ ). Then we see $l_{n+1}=l_n(2x_n+l_n+1/n) \textgreater l_n$ for $n \ge 2$ since $2x_n \textgreater 1$ since $x_n \textgreater 1-1/n \ge 1/2$ . So there exists a constant $C$ such that $x_k' \ge x_k+C$ for $k \ge 2$ . But since $x_k, x_k' \in (1-1/k, 1)$ , this is impossible. So we're done.

This solution was posted and copyrighted by JuanOrtiz. The original thread for this problem can be found here: [2]

Solution 3

Consider, now, the following observations:

(a) If, at any point, $x_{n+1}\le x_n$ , then from here we know that $x_n\le 1-\frac{1}{n},\quad x_{n+1}\le 1-\frac{1}{n} < 1-\frac{1}{n+1}\to x_{n+2}<x_{n+1}, \cdots x_m\le 1-\frac{1}{n} < 1-\frac{1}{m}\to x_{m+1}<x_m, \forall m>n$ and therefore the sequence $\{x_n\}$ will be monotonically decreasing after one point.

(b) If some $x$ does satisfy $0<x_n<x_{n+1}<1$ for all $n$ , then $1-\frac{1}{n}<x_n<1$ for all $n$ , and therefore by Squeeze's theorem $\lim_{n\to\infty}x_n = 1$ .

(c) If $x_n\ge 1$ for some $n$ , then $x_{n+1}=x_n(x_n+\frac 1n)>x_n^2\ge 1$ and so $x_{n+m}>(x_{m+1})^{2^{m-1}}$ which then gives $\lim_{n\to\infty}x_n=+\infty$ .

(d) If $x_1=0$ , then for each $n$ , $x_n=0$ . If $x_1\to\infty$ then for each $n$ (fixed), $x_n\to\infty$ . Thus, we can denote a mapping $f_n:\mathbb{R}^{\ge 0}\to \mathbb{R}^{\ge 0}$ that maps $x_1$ to $x_n$ , which is continuous and monotonically increasing, with $\lim_{x\to +\infty} f_n(x)=+\infty$ so $f_n$ is bijective.

Let's first show uniqueness. Suppose that $\{x_n\}$ and $\{y_n\}$ are both such sequences. We have $\lim_{n\to\infty}x_n=\lim_{n\to\infty}y_n=1$ and suppose that $y_1>x_1$ . Then for all $n$ , $\frac{y_{n+1}}{x_{n+1}} = \frac{y_n(y_n+\frac 1n)}{x_n(x_n+\frac 1n)}>\frac{y_n}{x_n}$ so inductively, $\frac{y_{n+1}}{x_{n+1}}>(\frac{y_{1}}{x_{1}})^n$ with $\lim_{n\to\infty}\frac{y_{n+1}}{x_{n+1}}=+\infty$ . However, $\lim_{n\to\infty}x_n=\lim_{n\to\infty}y_n=1$ gives $\lim_{n\to\infty}\frac{y_{n+1}}{x_{n+1}}=\frac{1}{1}=1$ , contradiction. Hence, the $x_1$ that satisfies this must be unique.

Next, let's show existence. We have seen from above that, $y_1>x_1$ implies $y_n>x_n$ , and that if $x_n>1$ for some $n$ then $\{x_n\}$ is monotonically increasing after some point. Suppose no such $x_1$ exists. Let \[ A=\{x_1: \exists n: x_{n+1}<x_n\}\qquad B=\{x_1: \exists n: x_n>1\} \]then if $x\in A$ , $y\in A$ for all $y<x$ and similarly $x\in B$ , $y\in B$ for all $y>B$ . Notice also an wasy fact that $1\in B$ , so $A$ is bounded. Define, now, $c=glb(A)$ . As we assumed $A\cup B=\mathbb{R}^+$ , this $c$ implies that $x_1<c\to x_1\in A$ and $x_1>c\to x_1\in B$ . It remains to ask whether $c\in A$ or $c\in B$ .

If $c\in A$ , then for this $x_1:=c$ , $x_n\le 1-\frac{1}{n}$ and so $x_{n+1}<1-\frac{1}{n+1}$ . Let $y_{n+1}$ be such that $x_{n+1}<y_{n+1}<1$ . By above, there's exactly one $y_1$ with $f_{n+1}(y_1)<y_{n+1}$ , and notice that $y_1>x_1=c$ by the monotonicity of $f_{n+1}$ . This means that there exists $y_1>c\in A$ , contradicting the definition of glb. A similar contradiction (but opposite direction) can also be established for the case $c\in B$ .

Hence $c$ is neither in $A$ or $B$ , means that $x_1=c$ should satisfy the problem condition. Q.E.D.

This solution was posted and copyrighted by Anzoteh. The original thread for this problem can be found here: [3]

1985 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Question
All IMO Problems and Solutions

Page

Toolbox

Search

1985 IMO Problems/Problem 6

Contents

Problem

Solution 1

Solution 2

Solution 3

See Also