olymmath

IMO 1985 Problem 6

For every real number x1x_1 , construct the sequence x1,x2,…x_1,x_2,\ldots by setting: xn+1=xn(xn+1n).x_{n+1}=x_n(x_n+{1\over n}). Prove that there exists exactly one value of x1x_1 which gives 0<xn<xn+1<10<x_n<x_{n+1}<1 for all nn .

Dataset text AI-MO AoPS. Quoted with source.

Official text: IMO 1985 official English paper, page 1.

Solutions

Human solution Solution 1 by hrkrshnn

Assume that there is some x1x_1 such that 0<xn<xn+1<10<x_n<x_{n+1}<1 then {xn}\{x_n\} is monotonically increasing and bounded. Hence converges by monotone convergence theorem.

Let lim⁡n→∞xn=l\lim\limits_{n\rightarrow \infty}{x_n}=l, then obtain l2=l⇒l=0,1l^2=l \Rightarrow l=0,1, we can readily omit 00 and hence xn→1x_n\rightarrow 1.


Proof for uniqueness of x1x_1.

Assume for the first term x1x_1 and a1a_1, the sequence {xn}\{x_n\} and {an}\{a_n\} converges. Without loss of generality assume x1>a1x_1>a_1(Recall that the definition states that all terms of the sequence are positive). Using induction we can prove that xn>an∀n∈Nx_n>a_n \quad\forall n\in \mathbb{N}.

As xnx_n and ana_n both converges to 11, there exits an NN such that for all n≥N  ⟹  34<an<xn<1n\ge N\implies \frac{3}{4}<a_n<x_n<1 (Take ε=14\varepsilon=\frac{1}{4})

Observe that xn+1−an+1=(xn−an)(xn+an)+1n(xn−an)>32(xn−an)x_{n+1}-a_{n+1}=\left(x_n-a_n\right)\left(x_n+a_n\right)+\frac{1}{n}\left(x_n-a_n\right)>\frac{3}{2}(x_n-a_n)

Hence xn+1−an+1xn−an>32  ⟹  xn+1−an+1>(32)n+1−N⋅(xN−aN)\begin{array}{rcl}\frac{x_{n+1}-a_{n+1}}{x_n-a_n}&>&\frac{3}{2}\implies\\ x_{n+1}-a_{n+1}&>&\left(\frac{3}{2}\right)^{n+1-N}\cdot(x_N-a_N) \\ \end{array}

The divergence of xn−anx_n-a_n is clear. A contradiction.


To prove the existence, denote f1(x)=xf_{1}(x)=x and fn+1(x)=fn(x)(fn(x)+1n)f_{n+1}(x)=f_{n}(x)\left(f_{n}(x)+\frac{1}{n}\right). Using induction prove that fn(x)f_{n}(x) is a strictly increasing function in xx.

Let bnb_n, cnc_n be such that fn(bn)=1−1nf_{n}(b_n)=1-\frac{1}{n} and fn(cn)=1f_{n}(c_n)=1, the existence and uniqueness of bnb_n, cnc_n follows from monotonicity of fnf_n, the observations fn(0)=0f_{n}(0)=0, fn(1)>1f_{n}(1)>1 and the continuity of fnf_{n}. Also observe that bn<cnb_n<c_n and using induction that bnb_n is strictly increasing and cnc_n is strictly decreasing sequences.

The set A={bn}A=\{b_n\} is bounded above. Hence by least upper bound property of R\mathbb{R} there exists a γ=sup⁡{bn}\gamma =\sup \{b_n\}. We shall show that γ\gamma is indeed our x1x_1!

fn+1(γ)=fn(γ)(fn(γ)+1n)>fn(γ)(fn(bn)+1n)=fn(γ)>0\color{blue}{f_{n+1}{(\gamma)}}=f_{n}(\gamma)\left(f_n{(\gamma)}+\frac{1}{n}\right)\color{blue}{>}f_{n}(\gamma)\left(f_{n}(b_n)+\frac{1}{n}\right)=\color{blue}{f_{n}(\gamma)>0} 1=fn(cn)>fn(γ)∀n\color{blue}{1}=f_{n}(c_{n})\color{blue}{>f_{n}(\gamma)} \quad \forall n   ⟹  1>fn+1(γ)>fn(γ)>0□\implies 1>f_{n+1}{(\gamma)}>f_{n}(\gamma)>0 \qquad \square


Proofs of interest

fn(x)f_n(x) has non negative integer coefficients hence fn(x)f_n(x) is strictly increasing on [0,1][0,1].

Notice that fn+1(bn)=fn(bn)(fn(bn)+1n)=1−1n<1−1n+1=fn+1(bn+1)  ⟹  bn<bn+1\color{blue}{f_{n+1}(b_n)}=f_{n}(b_n)\left(f_{n}(b_n)+\frac{1}{n}\right)=1-\frac{1}{n}\color{blue}{<}1-\frac{1}{n+1}=\color{blue}{f_{n+1}(b_{n+1})} \implies b_n< b_{n+1} or bnb_n is a strictly increasing sequence.

Notice that fn+1(cn)=fn(cn)(fn(cn)+1n)=1+1n>1=fn+1(cn+1)  ⟹  cn+1<cn\color{blue}{f_{n+1}(c_n)}=f_{n}(c_n)\left(f_{n}(c_n)+\frac{1}{n}\right)=1+\frac{1}{n}\color{blue}{>}1=\color{blue}{f_{n+1}(c_{n+1})} \implies c_{n+1}<c_n or cnc_n is a strictly decreasing sequence.

The fact that bnb_n is bounded is clear as bn<c1∀nb_n<c_1 \quad \forall n.

Mathematics Stack Exchange. Open licence.

Similar problems

These problems have the most words in common with this statement.

Locator imo/1985/p6 · Tag SM54M73ECF · Edit this page on GitHub · Keys: j next, k previous