Maths Olympiad Prep

Track / Stage 7 / 152 of 300 #1552 of 1964

Problem 1552

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

Example 3 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.

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\left(1-x^{n}\right) \\
& =\left(1-x^{n}\right)(1-x)>0
\end{aligned} This is a contradiction, so $x \geqslant 1$. Next, $x \geqslant 2-\frac{2}{n+1}$. In fact, if $x\frac{1}{n}\left(2-x+\frac{x-1}{n}\right)$ (this is because when the sum of two numbers is a constant $2-x+\frac{x}{n}$, the smaller the smaller number, the smaller the product), i.e., x(2-x)>2-x+\frac{x-1}{n}Repeatingthisprocess,weget Repeating this process, we get x^{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 $x \geqslant 2-\frac{2}{n+1}$. For $y>x \geqslant 2-\frac{2}{n+1}$, we have $\frac{y}{n}>\frac{x}{n} \geqslant 2-x$, so \frac{x}{n}(2-x)>\frac{y}{n}\left(2-x+\frac{y-x}{n}\right)Therefore, Therefore, 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\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 and solution reproduced as published; topic, difficulty and ordering added by this site.