Suppose that we knew that for $n>N$, we have $$F(n) \le F(n-g(n)) +h(n)$$ for some well behaved functions $g,h$. (for a concrete example, let’s say $N=1,g(n)=n^\alpha, h(n)=n^\beta$ where $\alpha,\beta \in (0,1))$)
I was wondering then how we can get an asymptotic upper bound of $F$. Would this be an easy job for Riemann-Stieltjes integration? (I am not very knowledgeable about this form of integration, so if this is the case, working through my concrete example would be appreciated)
Here's an approach that works well if you don't care about the leading constant. For simplicity assume $F$ is an increasing function, although one could probably do the technicalities to reduce to this case.
Suppose we have $F(n) \le F(n-n^\alpha) + n^\beta$. Starting from $F(N)$, let's iterate this inequality as many times as it takes so that the argument of $F$ in the upper bound is at most $N/2$. Each time we use the inequality, the argument is decreased by $n^\alpha$ for whatever our current value of $n$ is; since that value (by construction) is always at least $N/2$, we decrease the argument of $F$ by at least $(N/2)^\alpha$. Therefore the argument will go below $N/2$ in at most $(N/2)^{1-\alpha}$ iterations.
At each iteration, the upper bound increases by $n^\beta$ for the current value of $n$; since these values are all at most $N$, the upper bound increases by at most $N^\beta$ each time. The result of this iteration is the new recursive upper bound $$ F(N) \le F(N/2) + (N/2)^{1-\alpha}N^\beta = F(N/2) + 2^{\alpha-1}N^{\beta+1-\alpha}. $$ Now we iterate this inequality for $N$, $N/2$, $N/4$, and so on down to $N=1$ or wherever we want to stop. The resulting upper bound is a geometric series $$ F(N) \le F(1) + 2^{\alpha-1} \big( N^{\beta+1-\alpha} + (N/2)^{\beta+1-\alpha} + (N/4)^{\beta+1-\alpha} + \cdots \big); $$ notice that the exponent $\beta+1-\alpha$ is greater than $1$, so the first term is the dominant term (and we might as well bound the finite geometric series by the infinite geometric series it's the start of, whence the $\cdots$). The result is $$ F(N) \le F(1) + 2^{\alpha-1} \frac{N^{\beta+1-\alpha}}{1-2^{\alpha-1-\beta}}. $$ To get tighter and tighter upper bounds, one can reduce the $2$ in $N/2$ to a smaller and smaller constant; but the order of magnitude of this upper bound is probably correct. The limiting case is perhaps a differential equation? (If one assumes that $F(N)$ is bounded by a power of $N$, this could probably be made rigorous.) I'm not sure that I see a way to use Riemann–Stieltjes integration.
