<s>[INST] Recurrence problem: find $a_{1000}$ from $a_{0}$ Hi I'm stuck at yet another question. 
$a_{0}=5$. Given $a_{n+1}a_{n} = a_{n}^{2} + 1$ for all $n \ge 0$, determine $\left \lfloor{a_{1000}}\right \rfloor$. 
So I got $a_{n+1}=a_{n} + \frac{1}{a_{n}}$ and then:  
$a_{1000}=a_{0}+ \frac{1}{a_{0}} + \frac{1}{a_{1}} + \frac{1}{a_{2}} + ... + \frac{1}{a_{999}}$ 
and I even tried writing the relation as $a_{n}^{2} - a_{n+1}a_{n} + 1 = 0$ but I'm still not getting anywhere. Can someone just tell me how to deal with this recurrence relation, to start off? Thanks.
 [/INST] Squaring the given relation $a_{n+1} = a_{n} + \frac{1}{a_n}$, we get
$$ a_{n+1}^2 = a_n^2 + \frac{1}{a_n^2} + 2 \Rightarrow a_{n+1}^2 > a_n^2 +2 $$
and iterating we get (for $n = 999$ we get the right side) 
$$ a_{n+1}^2 > a_0^2 + 2n + 2 \Rightarrow a_{1000} > 2025 = 45^2 $$
Also, using the terms ($\frac{1}{a_i^2} $ terms) we neglected for relation above, and the fact that $a_{n+1}^2 > 2n + 27 > 2n + 2$ or just $ a_n^2 > 2n$,
$$ a_{n+1}^2 = 2025 + \sum_{i=1}^{n} \frac{1}{a_i}^2 < 2025 + \frac{1}{2} \sum_{i=1}^{n} \frac{1}{i}$$ $$ \Rightarrow a_{1000}^2 < 2025 + \frac{1}{2} \sum_{i=1}^{999} \frac{1}{i} = 2025 + H_{999} < 2025 + \ln(1000) < 46^2 $$
where $H_n$ is nth harmonic number. Try to  prove by yourself that $H_n < \ln(n+1)$. (Hint Riemann sums).
It follows that $\lfloor a_{1000} \rfloor = 45$.
</s>