An iterative argument involving $f(n + 1) - f(n) $

Question

I am working with an argument involving an inequality of the form: $$ f(n + 1) \leq f(n) + C (f(n))^{1 - \frac{1}{\gamma}} (\ast)$$ where $f$ is a positive function, $\gamma > 0$ and $C > 0$. It is know (but no proved explicitly) that $(\ast)$ leads to the bound $$ f(n) \leq n^{\gamma} ( \forall n > n_0 ) (\ast \ast)$$ for a certain $n_0$ to be choosen. My question is: How to prove $(\ast \ast)$, being that we have $(\ast)$. My failed attemp was to use a telescopic sum to obtain $f(n + \ell) - f(n) \leq C \sum_{k = 0 }^{ \ell - 1}(f(n + k))^{1 - \frac{1}{\gamma}}$ but, this no leads to $(\ast \ast)$ straight.

Answer 1

If you think about the case $f(n)=n^\gamma$ you get $$(n+1)^\gamma\leq n^\gamma+Cn^{\gamma-1}$$ Or equivalently \begin{align}\label{1} (n+1)^\gamma- n^\gamma\leq Cn^{\gamma-1} \end{align} Now, $(n+1)^\gamma- n^\gamma\leq \gamma (n+1)^{\gamma-1}$ (if $\gamma>1$). So, the inequality above will be satisfied for $n$ big enough if $C>\gamma$.

This is what makes me think that if $f(n)=n^\gamma+\hbox{small error}$, will satisfy the recursive inequality if $C>\gamma$. And therefore the inequality $f(n)\leq n^\gamma$ wouldn't be true. Maybe what you want is $f(n)\ll n^\gamma$ or $f(n)\ll n^{\gamma+\epsilon}$ because that seems the case.