Maths Olympiad Prep

Track / Stage 7 / 168 of 300 #1568 of 1964

Problem 1568

National Olympiad second round; IMO P1/P4
Algebra Difficulty 7.3 Prove it

Let x1,x2,,xnx_{1}, x_{2}, \cdots, x_{n} be positive numbers, and xn=i=0n1xni,n=1,2,3,x_{n}^{*}=\sum_{i=0}^{n-1} x_{n}^{i}, n=1,2,3, \cdots, prove: for all nNn \in \mathbf{N}^{\cdot}, we have 212n1xn<212n2-\frac{1}{2^{n-1}} \leqslant x_{n}<2-\frac{1}{2^{n}}. (36th IMO Shortlist Problem)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Prove that when n=1n=1, xn=1x_{n}=1, the proposition holds. Now assume n>1n>1, and let xn=xx_{n}=x. Clearly, x1x \neq 1, and we have xn=xn1x1x^{n}=\frac{x^{n}-1}{x-1}, which means
xn+12xn+1=0x^{n+1}-2 x^{n}+1=0

From (1), we get xn(2x)=1x^{n}(2-x)=1, so x1-x n -x (1-x n ) = (1-x n )(1-x)>0\text{x1-x n -x (1-x n ) = (1-x n )(1-x)>0}

This is a contradiction, so x1x \geqslant 1.
Next, x22n+1x \geqslant 2-\frac{2}{n+1}. In fact, if x1n(2x+x1n)x\frac{1}{n}\left(2-x+\frac{x-1}{n}\right) (this is because when the sum of two numbers is a constant 2x+xn2-x+\frac{x}{n}, the smaller the smaller number, the smaller the product), i.e.,
x(2x)>2x+x1nx(2-x)>2-x+\frac{x-1}{n}

Repeating this process, we get
xn(2x)>xn1(2x+x1n)>>2x+x1nn=1x^{n}(2-x)>x^{n-1}\left(2-x+\frac{x-1}{n}\right)>\cdots>2-x+\frac{x-1}{n} \cdot n=1

This contradicts (1), which proves that x22n+1x \geqslant 2-\frac{2}{n+1}.
For y>x22n+1y>x \geqslant 2-\frac{2}{n+1}, we have yn>xn2x\frac{y}{n}>\frac{x}{n} \geqslant 2-x, so
xn(2x)>yn(2x+yxn)\frac{x}{n}(2-x)>\frac{y}{n}\left(2-x+\frac{y-x}{n}\right)

Therefore,
xn(2x)>xn1y(2x+yxn)>>yn(2x+yxnn)=yn(2y)x^{n}(2-x)>x^{n-1} y\left(2-x+\frac{y-x}{n}\right)>\cdots>y^{n}\left(2-x+\frac{y-x}{n} \cdot n\right)=y^{n}(2-y)

Thus, if x(212n1)n12n1=2(112n)n>1x\left(2-\frac{1}{2 n-1}\right)^{n} \cdot \frac{1}{2^{n-1}}=2\left(1-\frac{1}{2^{n}}\right)^{n}>1$

This contradicts (1), so x212nx \geqslant 2-\frac{1}{2^{n}}.
This proves the required inequality.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.