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.
 A: 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$ 

The previous answer:
Hint: Consider $(a_n)^2$ and try to apply similar reasoning as you did for $a_n$.
A: 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$.
A: 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}$$
A: Hint: prove by induction that $a_n \leq 2\sqrt{n}$.
A: Use $a_{n+1} = \frac{1}{a_n} + \frac{1}{a_{n-1}} + \cdots + 1$ and $a_n \longrightarrow \infty$.
A: 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}.$
