# Asymptotic of specific type of recurrence using Riemann integral approximation

So I've seen this technique used before, but can't find where I saw it nor do I remember how to finish. The general idea was let's say you have a recurrence of the form $$a_n=a_{n-1}+\frac{f(n)}{g(a_{n-1})}$$ Where $$g$$ is an increasing and positive function and $$f$$ is positive (it's usually something simple like the identity or constant). You want to compute an asymptotic for $$a_n$$. The idea is that you can rewrite it as $$g(a_{n-1})(a_n-a_{n-1})=f(n)$$ And then sum from $$n=1$$ to $$N$$ to get $$\sum_{n=1}^N g(a_{n-1})(a_n-a_{n-1})=\sum_{n=1}^N f(n)$$ Now the LHS looks like a riemann sum, and since $$g$$ is increasing, we have that it is bounded above by $$\int_{a_0}^{a_N} g(x)\, dx$$. If $$\frac{d}{dx} G(x)=g(x)$$, we can say that $$G(a_N)-G(a_0)\geq \sum_{n=1}^N f(n)$$ $$G(a_N)\geq G(a_0)+\sum_{n=1}^N f(n)$$ $$a_N\geq G^{-1}\left(G(a_0)+\sum_{n=1}^N f(n)\right)$$ And this gives a lower bound. But to make any conclusions about the asymptotics we would also need an upper bound and I am stuck there. We can't really use the same approach for the upperbound because we can't make it a right riemann sum.

I'm honestly just curious if anyone has a source for this type of approach or solutions that solve this type of problem this way as I can't remember where I initially saw this approach. But also if anyone knows how to solve it, that would of course also be appreciated

• Do we have any assumptions about $f$ or is it just a function? I'd hope it is positive as otherwise the $a_n$ might not be increasing? Commented Aug 10, 2023 at 7:14
• Oh yes, let's assume it is positive. I think usually in the cases I've seen it's something simple like the identity function. Commented Aug 10, 2023 at 12:16
• In the second half of your question, $a_n$ should be $a_N$. Commented Aug 14, 2023 at 17:42
• This is usually encountered as the Newton iteration scheme of finding solutions/roots to $f(a)=0$ where $g=f'$ is the first derivative, so $g$ is the integral of $f$, and $a_{n-1}$, $a_n$ are consecutive approximations. Commented Aug 17, 2023 at 15:45
• @R.J.Mathar Interesting that the forms are similar, but the numerator in Newton's method would be $f(a_{n-1})$ as opposed to just $f(n)$. Commented Aug 18, 2023 at 0:07