Question

What kind of growth does this function have? \(f(n) = f(n-1) + \dfrac{1}{f(n-1)};~n\in\mathbb{N}\), where \(f(0) = 1\)

From http://www.reddit.com/r/CasualMath/comments/2jhwtm/is_fn_fn1_1fn1_f0_1_logarithmic_growth/

Answer 1

One answer said it seemingly approaches to \(\sqrt{2x}\) , so \(O(\sqrt{x})\)

But how can we show that?

I don't understand other answer (differentiation one), though.

Answer 2

You can prove that it's O(sqrt(x)) with induction. I assumed the "tightest fit" equation was 2sqrt(x), as sqrt(2x) proved the base case false, which makes the proof by induction invalid.

http://i.imgur.com/YAr9OpA.jpg
imgur link to my induction since I can't use math notations online well + induction is really horrible to type out

To prove that it's the tightest fit, you have to prove omega(sqrt(x)), which will in turn prove theta(x). Proof is pretty much the same for omega.