4
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How did you get b_n is less than or equal to 2n-1? $\endgroup$ – Matthew Tan Dec 22 '18 at 10:02
  • $\begingroup$ @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.}$ $\endgroup$ – Lance Dec 22 '18 at 22:12
5
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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$)? $\endgroup$ – Jack D'Aurizio Dec 21 '18 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.