Saudi Arabian Mathematical Competitions

Note that, since $x_{1}=1$, $x_{n+1}=\frac{x_{n}+2}{x_{n}+1}$ we can write
$$\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
$$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 $a_{n+1}=x_{2^{n}}$ for $n \geq 0$ then $a_{1}=x_{1}=1$, $a_{2}=x_{2}$, $a_{3}=x_{4}$, $\ldots$ Take $k=2^{n-1}$ in above formula, we get
$$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 $a_{n}=y_{n}$ for all $n \geq 1$. Therefore, $y_{n+1}=a_{n+1}=x_{2^{n}}$ for any $n \geq 0$. $\square$