# Given $a_{1}=1, \ a_{n+1}=a_{n}+\frac{1}{a_{n}}$, find $\lim \limits_{n\to\infty}\frac{a_{n}}{n}$

I started by showing that $1\leq a_{n} \leq n$ (by induction) and then $\frac{1}{n}\leq \frac{a_{n}}{n} \leq 1$ which doesn't really get me anywhere.

On a different path I showed that $a_{n} \to \infty$ but can't see how that helps me.

-
Maybe this is obvious, but people sometimes forget obvious methods: try writing out first few terms (10, say) and you might get an idea about how fast they grow. Then you bound the terms by some simple function. If the bound is tight enough to give you a limit (0 in this case) then you proceed to actually prove the bound (which may or may not be easy). – Marek Nov 13 '10 at 2:12
that's what I tried by showing $a_{n}\leq n$ but it wasn't tight enough. – daniel.jackson Nov 13 '10 at 8:08
for sequence (1, 2, 2.5, 2.9, 3.2, 3.6, 3.8, ...) your bound is obviously pretty crude and in particular it doesn't help you at all. You should try to get a crudest bound that will help you (to make proving easier), but no cruder :-) In this case a_n ~ sqrt(2n), so that for any epsilon in [1/2, 1) Kn^{epsilon} is good enough. – Marek Nov 13 '10 at 12:37

Use $a_{n+1} = \frac{1}{a_n} + \frac{1}{a_{n-1}} + \cdots + 1$ and $a_n \longrightarrow \infty$.

-
I like this better, but unfortunately, I am out of votes for today. – Aryabhata Nov 12 '10 at 23:23
+1: As promised :-) – Aryabhata Nov 13 '10 at 8:51
I ended up using Stolz-Cesàro theorem. Because the number of fractions depends on $n$ I can't determine the limit directly, or did you mean something else? – daniel.jackson Nov 14 '10 at 15:25
For every $\epsilon > 0$, from some point on, all summands $1/a_n$ are smaller than $\epsilon$, so the sum is at most $\epsilon n + C_\epsilon$. – Yuval Filmus Nov 14 '10 at 18:11

I completely forgot about the Stolz-Cesàro theorem, from which we get:

$$\lim_{n\to \infty} \frac{a_n}{n}=\lim_{n\to\infty} \frac{a_{n+1}-a_{n}}{(n+1)-n}=\lim_{n\to \infty}\frac{\frac{1}{a_{n}}}{1}=\lim_{n\to \infty}\frac{1}{a_{n}}=0.$$ The same technique works for $\displaystyle \frac{a_{n}^2}{n}.$

-
Very interesting. Well done :-) – Aryabhata Nov 14 '10 at 15:30

Now that the homework is solved, here is some more investigation into this interesting sequence.

I think we can show that $$\displaystyle a_{n}^2 \sim 2n + \dfrac{\log n}{2} - C$$ for some constant $\displaystyle C \gt 0$

By $\displaystyle x_n \sim y_n$ I mean $\displaystyle \lim_{n \to \infty} (x_n - y_n) = 0$

Consider $b_n = a_{n}^2 - 2n$

Then we have that $\displaystyle b_{n+1} = b_n + \dfrac{1}{b_n + 2n}$

Notice that $b_3 \gt 0$ and thus for sufficiently large $\displaystyle n$, $\displaystyle b_n \gt 0$.

It is also easy to show that $\displaystyle b_n \lt 2n$. In fact, we can easily show that $b_n \lt \log n$

Now we have that, for sufficiently large $\displaystyle m,n$

$\displaystyle b_{m+1} - b_n = \sum_{k=n}^{m} \dfrac{1}{b_k + 2k}$

Since $\displaystyle 0 \lt b_k \lt \log k$

we have that

$\displaystyle \sum_{k=n}^{m} \dfrac{1}{2k} \gt b_{m+1} - b_n \gt \sum_{k=n}^{m} \dfrac{1}{2k}(1- \dfrac{b_k}{2k})$

(Here we used $\displaystyle \dfrac{1}{1+x} \gt \ \ 1-x, 1 \gt x \gt 0$)

Now Since $b_k \lt \log k$, we have that

$\displaystyle \sum_{k=n}^{m} \dfrac{1}{2k} \gt b_{m+1} - b_n \gt \sum_{k=n}^{m} \dfrac{1}{2k} - \sum_{k=n}^{m} \dfrac{\log k}{4k^2}$

Using the fact that $\displaystyle H_m - H_n = \log(\dfrac{m+1}{n}) + O(\dfrac{1}{n} - \dfrac{1}{m})$, where $\displaystyle H_n = \sum_{k=1}^{n} \dfrac{1}{k}$ is the $\displaystyle n^{th}$ harmonic number.

We see that,

if $c_n = b_n - \dfrac{\log n}{2}$, then

$\displaystyle O(\dfrac{1}{n} -\dfrac{1}{m}) \gt c_{m+1} - c_n \gt O(\dfrac{1}{n} -\dfrac{1}{m}) -\sum_{k=n}^{m} \dfrac{\log k}{4k^2}$

Now $\displaystyle \sum_{k=1}^{\infty} \dfrac{\log k}{k^2}$ is convergent and so by the Cauchy convergence criteria, we have that $\displaystyle c_n$ is convergent.

Thus the sequence $\displaystyle a_{n}^2 - 2n - \dfrac{\log n}{2}$ converges and hence, for some $\displaystyle C$ we have that

$$\displaystyle a_{n}^2 \sim 2n + \dfrac{\log n}{2} - C$$

or in other words

$$\displaystyle a_{n} \sim \sqrt{2n + \dfrac{\log n}{2} - C}$$

A quick (possibly incorrect) computer simulation seems to show a very slow convergence to $\displaystyle C = 1.47812676429749\dots$

Hint: Consider $(a_n)^2$ and try to apply similar reasoning as you did for $a_n$.

-
actually the next question is to look at $(a_{n})^2 / n$ ;) – daniel.jackson Nov 12 '10 at 23:29
@daniel: That seems to be a harder problem :-) Does it ask to find the limit of $(a_n)^2/n$? Interesting course you are taking there :-) – Aryabhata Nov 12 '10 at 23:31
yes, I was hoping that $a_{n}/n \to 1$ and then it's easy, but guess not :) – daniel.jackson Nov 12 '10 at 23:35
perhaps you have a hint for $\frac{(a_{n})^2}{n}$? the closest I got was to show that $\frac{1}{n}\leq \frac{(a_{n})^2}{n} \leq 3$ which implies that if $b_{n}=\frac{(a_{n})^2}{n}$ is monotonic then the limit exists. but still I haven't showed that it's monotonic and even if it is, how do I find its limit? – daniel.jackson Nov 13 '10 at 12:21
@Moron: This is very impressive. – Martin Gales Nov 17 '10 at 12:45

As $a_{n+1}^2 = a_n^2 + 2 + \frac{1}{a_n^2}$, we know that

$a_{n+1}^2 \leq a_n^2 + 3$

If $a_n^2 \leq 3n$, then $a_{n+1}^2 \leq 3(n+1)$, and since $a_1^2 = 1 \leq 3$, by the induction hypothesis $a_n^2 \leq 3n$

Thus, $\frac{a_n^2}{n^2} \leq 3/n$ for all $n$, and hence

$\lim_{n \rightarrow \infty} \frac{a_n^2}{n^2} = 0$

from this it follows though that

$\lim_{n \rightarrow \infty} \frac{a_n}{n} = 0$.

-

Lets rewrite:

$$\frac{a_{n+1}-a_n}{n+1-n}=\frac{1}{a_n}$$

Now, as n goes to infinity lets denote $$a_n=f$$ .Then approximately:

$$\frac{d f}{dn}=\frac{1}{f}$$

After integrating:

$$\frac{f^2}{2}=n+c=>\frac{f^2}{n^2}=\frac{2}{n}+\frac{c}{n^2}$$

-
+1: Even though this seems like nonsensical math, Donald J Newman actually suggests using this as a quick method to get an idea of the rough asymptotic behaviour of a series. – Aryabhata Nov 13 '10 at 19:13

Hint: prove by induction that $a_n \leq 2\sqrt{n}$.

-