Recurrence problem: find $a_{1000}$ from $a_{0}$

Solution 1:

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$.