Team selection tests for GMO 2018

The sequence is increasing since $x_{n+1}-x_n=(x_n-1{)}^2\ge 0$. We also have $x_{n+1}-1=x_n(x_n-1)$ which gives us $$\frac{1}{x_{n+1}-1}=\frac{1}{x_n(x_n-1)}=\frac{1}{x_n-1}-\frac{1}{x_n}$$ This identity is valid because given $x_1=2$ we have $x_n\ge 2$ and therefore $x_n-1\ne 0$. Now given that $\frac{1}{x_n}=\frac{1}{x_n-1}-\frac{1}{x_{n+1}-1}$ we obtain the identity $$\frac{1}{x_1}+\frac{1}{x_2}+\cdots +\frac{1}{x_n}=1-\frac{1}{x_{n+1}-1}$$ So we have to prove $$1-\frac{1}{2^{2^{n-1}}}<1-\frac{1}{x_{n+1}-1}<1-\frac{1}{2^{2^n}}$$ or equivalently $$2^{2^{n-1}}<x_{n+1}-1<2^{2^n}$$ We will prove this by induction. For $n=1$ we simply get $2<x_2-1<4$ which is true since $x_2=3$. Assume the statement is true for $n=k$, i.e. $$2^{2^{k-1}}<x_{k+1}-1<2^{2^k}$$ For $n=k+1$ we have $$x_{k+2}-1=x_{k+1}(x_{k+1}-1)>2^{2^{k-1}}(2^{2^{k-1}}+1)=2^{2^k}+2^{2^{k-1}}>2^{2^k}$$ by the induction hypothesis. On the other hand we know that $x_n$'s are all integers and therefore $x_{k+1}\le 2^{2^k}$ by the induction hypothesis. We obtain $$x_{k+2}-1=x_{k+1}(x_{k+1}-1)>2^{2^k}\cdot 2^{2^k}=2^{2^{k+1}}$$ which is what we wanted to prove. $\square$