# Problem 98 **

Let (a_n)_{n \ge 0} be a sequence such that a_0 > 0 and \displaystyle a_{n + 1} = a_n + \frac 1 {a_n}.

Show that the sequence (a_n)_{n \ge 0} is divergent.

Find that \displaystyle \lim_{n \to \infty} \frac {a_n} {\sqrt n}.

[originally posted by Mladenov on TSR]

We show by induction that a_{n}>0 for all non-negative integer n:

a_0>0 is the base case.

Suppose a_k>0 for some n=k. Consider n=k+1:

a_{k+1}=a_k+\frac{1}{a_k} and {1 \over a_k}>0 \\ \therefore a_{k+1}>0, as asserted.

Thus a_{n}>0 (and {1 \over a_n}>0) for all non-negative integer n.
Hence, a_{n+1}=a_n+{1 \over a_n}>a_n. Therefore, the sequence is strictly increasing.

It suffices to show that the sequence has no upper bound:

If (a_n)_{n \geq 0} has an upper bound then \lim_{x \to \infty} a_n=c \in \Bbb R^+

But \displaystyle\lim_{x \to \infty} a_n=\lim_{x \to \infty} \left(a_{n-1}+{1 \over a_{n-1}} \right)=c+{1 \over c}

\displaystyle\therefore c=c+{1 \over c} \\ {1 \over c}=0
There is no real solution for the above, hence no such c exists and thus (a_n)_{n \geq 0} has no upper bound. Therefore, the sequence diverges to infinity.

We thus know that \displaystyle\lim_{x \to \infty} \frac1{a_n}=0

Now consider the sequence \left({a^2_n \over n}\right)_{n \geq 1}:

a^2_{n+1}=a^2_n+2+{1 \over a^2_n}
We prove by induction that:
\displaystyle a^2_n=a^2_0+2n+\sum^{n-1}_{r=0}{1 \over a^2_r}
The base case is trivial.
Suppose the conecture is true for n=k Consider n=k+1:
\displaystyle a^2_{k+1}=a^2_k+2+{1 \over a^2_n} \\=a^2_0+2k+\sum^{k-1}_{r=0}{1 \over a^2_r}+2+\frac1{a_k^2} \\=a^2_0+2(k+1)+\sum^{k}_{r=0}{1 \over a^2_r}
By induction, the theorem holds.

Ergo:
\displaystyle \frac{a^2_n}n=2+\frac{a^2_0}n+\frac1n\sum^{n-1}_{r=0}{1 \over a^2_r}

We show that \displaystyle\sum^\infty_{r=0}{1 \over a^2_r} converges:
It is easy to show that \displaystyle a_{n+1}\geq a_n+1, a_0 \geq 1\implies a_{n+1}\geq (n+1) \implies a_{n+1}^2\geq (n+1)^2 \implies \frac1{a_{n+1}^2}\leq \frac1{(n+1)^2}
\displaystyle\sum^\infty_{n=0} \frac1{(n+1)^2}=\sum^\infty_{n=1} \frac1{n^2} is a well-know convergent sum. Thus, by the comparison test, \displaystyle\sum^\infty_{n=0}\frac1{a_{n+1}^2} converges to some d \in \Bbb R.

Hence, \displaystyle \lim_{n \to \infty}\frac1n\sum^{n-1}_{r=0}{1 \over a^2_r}=\lim_{n \to \infty}\frac1n \cdot \lim_{n\to\infty}\sum^{n-1}_{r=0}{1 \over a^2_r}=0

\displaystyle\therefore \lim_{n \to \infty}\frac{a^2_n}n=\lim_{n \to \infty}\left(2+\frac{a^2_0}n+\sum^{n-1}_{r=0}{1 \over na^2_r}\right)=2
\displaystyle\therefore\lim_{n \to \infty}\frac{a_n}{\sqrt n}=\sqrt2