SMO 2004 Question 21

Question

Let $\frac{1}{a_1}$, $\frac{1}{a_2}$, $\frac{1}{a_3}$.... be a sequence of positive numbers defined by: $$a_1=1, a_{n+1}=a_n+\frac{1}{a_n}$$ Find the integer part of $a_{100}$. This question was given in the Singapore Mathematics Olympiad in 2004 and it doesn't follow any of the typical recursion functions. Does anyone know how to even start approaching this question and what kind of motivation would make you use such an approach?

Answer 1

This was given in a competition? I am quite surprised, since it is a very classical problem.
Let us define $b_n$ as $a_n^2$. Then $$ b_{n+1} = b_n + 2 + \frac{1}{b_n} $$ easily leads (by induction) to $b_n\geq 2n-1$. By plugging back this approximation in the above recursion, we get $b_n \leq 2n-1+\left(\frac{1}{1}+\frac{1}{3}+\ldots+\frac{1}{2n-3}\right)$. In particular $a_{100}$ is bounded between $\sqrt{199}$ and $$ \sqrt{199+H_{198}-\frac{H_{99}}{2}}\leq \sqrt{205}, $$ so $\lfloor a_{100}\rfloor = \color{red}{14}.$

Answer 2

The growth rate of this sequence can be approximately modeled by the differential equation $y' = \frac {1}{y}$

$a_n\approx \sqrt{2n}\\ a_{100}\approx 14.14$