Team selection tests for GMO, 2018

The sequence is increasing since $x_{n+1}-x_{n}=(x_{n}-1)^{2} \geq 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} \geq 2$ and therefore $x_{n}-1 \neq 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} \leq 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$