USA IMO

It suffices to prove that $a_{n+5}\ge a_n^2$ for $n\ge 0$, for then we would have $\sqrt{a_{n+5}}\ge a_n$ and $a_n\ge a_{n-5}^2$ for all $n\ge 5$, which implies the desired result. Adding the inequalities $$\begin{array}{rl}{a}_{n+5}& \ge a_{n+4}^2+\frac{1}{5},\\ a_{n+4}& \ge a_{n+3}^2+\frac{1}{5},\\ a_{n+3}& \ge a_{n+2}^2+\frac{1}{5},\\ a_{n+2}& \ge a_{n+1}^2+\frac{1}{5},\\ a_{n+1}& \ge a_n^2+\frac{1}{5}\end{array}$$ yields $$\begin{array}{rl}{a}_{n+5}& \ge \sum _{k=1}^4(a_{n+k}^2-a_{n+k})+1+a_n^2\\ & =\sum _{k=1}^4\left(a_{n+k}^2-a_{n+k}+\frac{1}{4}\right)+a_n^2\\ & =\sum _{k=1}^4{\left(a_{n+k}-\frac{1}{2}\right)}^2+a_n^2\ge a_n^2,\end{array}$$ as desired.

---

Alternative solution.

(by Alison Miller) For any $k$, we have the following inequality: $$a_{k+1}+\frac{1}{20}\ge a_k^2+\frac{1}{5}+\frac{1}{20}=a_k^2+\frac{1}{4}\ge a_k,$$ because $(a_k-\frac{1}{2}{)}^2\ge 0$. Summing up this inequalities over $k=n+1,\dots ,n+4$, we have $$a_{n+5}+\frac{1}{5}\ge a_{n+1}\ge a_n^2+\frac{1}{5},$$ and similarly $a_n\ge a_{n-5}^2$, so $$a_{n+5}\ge a_n^2\ge a_{n-5}^4,$$ implying the desired result.

---

Alternative solution.

Define the function $f(x)=x^2+\frac{1}{5}$, which is increasing for $x\ge 0$. Also define the function $g(x)=f(x)-x=(x-r_1)(x-r_2)$, where $$r_1=\frac{5-\sqrt{5}}{10}\text{and}{r}_2=\frac{5+\sqrt{5}}{10}.$$ Observe that $0<r_1<r_2<1$. So, for nonnegative $x$, $g(x)$ is zero for $x=r_1,r_2$, negative for $x\in (r_1,r_2)$, and positive otherwise. Therefore, for nonnegative $x$, $f(x)=x$ for $x=r_1,r_2$, $f(x)<x$ for $x\in (r_1,r_2)$, and $f(x)>x$ otherwise. Fix $n\ge 5$, and write $a=|a_{n-5}|$. It suffices to prove that $a_{n+5}\ge a_{n-5}^4$. We consider the following cases. (i) $a\le r_1$. For $x\in [0,r_1]$, observe that $x\le f(x)\le f(r_1)=r_1$. An easy proof by induction on $k=0,1,\dots ,9$ then shows that $f^{(k)}(x)\le f^{(k+1)}(x)\le r_1$. Therefore, $a\le f(a)\le f^{(2)}(a)\le \cdots \le f^{(10)}(a)=a_{n+5}$. Because $a<1$, we have $a_{n+5}\ge a>a^4=a_{n-5}^4$, as desired. (ii) $a\in (r_2,1]$. For $x>r_2$, observe that $f(x)>x$ and hence $f(x)>x>r_2$. We can repeat this argument to show that $f^{(k+1)}(x)>f^{(k)}(x)>r_2$ for $k=0,1,\dots ,9$. Therefore, $a_{n+5}=f^{(10)}(a)>f^{(9)}(a)>\cdots >a\ge a^4=a_{n-5}^4$, as desired. (iii) $a>1$. Notice that for all $k$, $a_{k+1}>a_k^2$. Therefore, $a_{n+5}>a_{n-5}^{10}=a^6\cdot a_{n-5}^4>a_{n-5}^4$, as desired. (iv) $a\in (r_1,r_2)$. For $x\in (r_1,r_2)$, observe that $r_1=f(r_1)<f(x)<f(r_2)=r_2$. Therefore, $a_{n+5}=f^{(10)}(a)>r_1$. Hence, if we can verify that $r_1>r_2^4$, then we would have $$a_{n+5}>r_1>r_2^4>a^4=a_{n-5}^4,$$ as desired. Note that $$r_2^4=\frac{{\sum }_{k=0}^4\left(\genfrac{}{}{0ex}{}{4}{k}\right)(\sqrt{5}{)}^k{5}^{4-k}}{10000},$$ which expands to $$\frac{5^4+4\cdot 5^3\cdot \sqrt{5}+6\cdot 5^2\cdot (\sqrt{5}{)}^2+4\cdot 5\cdot (\sqrt{5}{)}^3+(\sqrt{5}{)}^4}{10000}.$$ Hence $r_2^4=(7+3\sqrt{5})/50$. Then $$\begin{array}{rl}320<324& ⟹8\sqrt{5}<18\\ & ⟹7+3\sqrt{5}<5(5-\sqrt{5})\\ & ⟹\frac{7+3\sqrt{5}}{50}<\frac{5-\sqrt{5}}{10}\\ & ⟹r_2^4<r_1,\end{array}$$ as needed. This completes the proof.