Math Olympiad Question : $a_na_{n+1} = a_n^2 + 1, a_0 = 5$

Question

Problem

This question is from the Singapore Math Olympiad 2017 Open Section.
The question goes like this :

Let $a_0=5$ and $a_na_{n+1} = a_n^2 + 1$ for all $n\geq0$. Determine $\left \lfloor{a_{1000}}\right \rfloor $.

• It can be deduced that $a_{n+1} = a_n + \frac{1}{a_n}$ and since $a_0 > 0 \implies a_n > 0$.
  
• Hence, $\frac{1}{a_n} > 0 \implies a_{n+1} > a_n$, implying that $a_n$ is an increasing function with respect to $n$.
  
• Moreover, since $a_{n+1} > a_n \implies \frac{1}{a_{n+1}}<\frac{1}{a_n} \implies (a_{n+1} - a_{n}) > (a_{n+2} - a_{n+1})$, implying that $a_n$ is increasing at a decreasing rate.
  

Attempt

Here are my attempts to find $\left \lfloor{a_{1000}}\right \rfloor$.

1. Firstly, I tried to find an explicit functional equation for $a_n$. [Failed]
2. Secondly, I tried to find left and right bound for $a_n$. and I got. $a_n < a_0 + \frac{n}{a+0}$ which is not helpful at all. [Failed]
3. Using the computer as a last resort, I found the answer algorithmically : 45.
   

Question

• How can I solve this question without using any machine assistance.
• What method should I use and what should I look out for?

Answer 1

You have $$a_{n+1}^2=a_n^2+2+\frac{1}{a_n^2}.$$ Therefore $a_n^2\ge2n+25$. In particular $a_{1000}^2\ge2025$. Also $$a_n^2\le 2n+25+\sum_{k=0}^{n-1}\frac1{(2k+25)^2}<2n+25+\frac{\zeta(2)}4<2n+26.$$ Thus $2025<a_{1000}^2<2026$ and $45<a_{1000}<46$.