SMO 2004 Question 21

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?

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}.$$
• @Mattew Tan $b_{n}>2+b_{n-1}\implies b_n>2(n-1)+b_1=2n-1\\b_n=b_{n-1}+2+\cfrac 1{b_{n-1}}<b_{n-1}+2+\cfrac 1{2n-3}, \\ \cdots \\ b_2<b_1+2+\cfrac 1{2\cdot 2-1},\\ \text{add above and cancel out }b_{n-1} \text{ to } b_2, \text{ to arrive at the 2nd inequality.}$ – Lance Dec 22 '18 at 22:12
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$$
• In numerical algorithms for (P)DE we usually replace $\frac{d}{dx}$ with the forward difference operator. Here we are (reasonably) doing the opposite (since the associated DE is very simple to solve), but how to be sure such approximation does not change the leading term of the asymptotic behaviour of $a_n$ (and ultimately leads to the same value for $\lfloor a_n\rfloor$)? – Jack D'Aurizio Dec 21 '18 at 20:38