Maths Olympiad Prep

Library / /59 of 155

Algebra Difficulty 5.7 AIME, harder Prove it Saudi Arabia

Let sequences of real numbers (xn)\left(x_{n}\right) and (yn)\left(y_{n}\right) satisfy x1=y1=1x_{1}=y_{1}=1 and
xn+1=xn+2xn+1 and yn+1=yn2+22yn for n=1,2,…. x_{n+1}=\frac{x_{n}+2}{x_{n}+1} \quad \text{ and } \quad y_{n+1}=\frac{y_{n}^{2}+2}{2 y_{n}} \text{ for } n=1,2, \ldots .
Prove that yn+1=x2ny_{n+1}=x_{2^{n}} holds for n=0,1,2,…n=0,1,2, \ldots

Solution

Note that, since x1=1x_{1}=1, xn+1=xn+2xn+1x_{n+1}=\frac{x_{n}+2}{x_{n}+1} we can write
xn+1=xn⋅x1+2xn+x1=xn−1+2xn−1+1⋅x1+2xn−1+2xn−1+1+x1=xn−1(x1+2)+2(x1+1)xn−1(x1+1)+(x1+2)=xn−1⋅x1+2x1+1+2xn−1+x1+2x1+1=xn−1⋅x2+2xn−1+x2 \begin{aligned} x_{n+1} & =\frac{x_{n} \cdot x_{1}+2}{x_{n}+x_{1}}=\frac{\frac{x_{n-1}+2}{x_{n-1}+1} \cdot x_{1}+2}{\frac{x_{n-1}+2}{x_{n-1}+1}+x_{1}}=\frac{x_{n-1}\left(x_{1}+2\right)+2\left(x_{1}+1\right)}{x_{n-1}\left(x_{1}+1\right)+\left(x_{1}+2\right)} \\ & =\frac{x_{n-1} \cdot \frac{x_{1}+2}{x_{1}+1}+2}{x_{n-1}+\frac{x_{1}+2}{x_{1}+1}}=\frac{x_{n-1} \cdot x_{2}+2}{x_{n-1}+x_{2}} \end{aligned}
So by the same way, we can prove that
xn=xkxn−k+2xk+xn−k for any 1≤k≤n−1.  x_{n}=\frac{x_{k} x_{n-k}+2}{x_{k}+x_{n-k}} \text{ for any } 1 \leq k \leq n-1 \text{. }
Let an+1=x2na_{n+1}=x_{2^{n}} for n≥0n \geq 0 then a1=x1=1a_{1}=x_{1}=1, a2=x2a_{2}=x_{2}, a3=x4a_{3}=x_{4}, …\ldots Take k=2n−1k=2^{n-1} in above formula, we get
x2n=x2n−12+22x2n−1 so an+1=an2+22an. x_{2^{n}}=\frac{x_{2^{n-1}}^{2}+2}{2 x_{2^{n-1}}} \text{ so } a_{n+1}=\frac{a_{n}^{2}+2}{2 a_{n}} .
Thus by induction, one can get an=yna_{n}=y_{n} for all n≥1n \geq 1. Therefore, yn+1=an+1=x2ny_{n+1}=a_{n+1}=x_{2^{n}} for any n≥0n \geq 0. □\square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.