How fast does the sequence $b_{n+1}=b_n+\frac{1}{b_n}$ grow?

Question

$b_{n+1}=b_n+\frac{1}{b_n}$, where $b_0=1$.

I have proven that this sequence is $O(\ln n)$ and $o(n)$.

Can anyone give a more precise estimation of the order of $b_n$? i.e. a $f(n)$ such that $0<\lim_{n \to \infty}\frac{b_n}{f(n)}<\infty$

Answer 1

Note that $$b_{n+1}^2-b_n^2=2+\frac{1}{b_n^2}>2$$ So, a simple induction shows that $$\forall n\ge0,\qquad b_n\ge \sqrt{2n+1}$$ It follows that $$\forall k\ge1,\qquad b_{k+1}-b_k\le \frac{1}{\sqrt{2k+1}}\le\sqrt{2k+1}-\sqrt{2k-1}$$ Adding, we get $$\forall n\ge2,\qquad b_{n}-b_1\le\sqrt{2n-1}-1$$ or $$\forall n\ge1,\qquad \sqrt{2n+1}\le b_{n}\le\sqrt{2n-1}+1$$ This shows that $$b_n\sim \sqrt{2n}.$$

Answer 2

Another idea (that needs some additional work).
Approximate your discrete sequence $b_n$ using a continuous function $\beta(x)$: $$ b_{n+1}-b_n = \frac{1}{b_n}, \qquad b_0=1\tag{1} $$

$$ \beta'(x) = \frac{1}{\beta(x)},\qquad \beta(0)=1\tag{2} $$ with solution $$ \beta(x) = \sqrt{2x+1} $$ Then what remains is to determine how well the solution of (2) approximates the solution of (1). Perhaps using the mean value theorem.