I have a non-linear recurrence given by
$$n_0 = N \\ n_{i+1} = n_i - n_i^{3/4}$$
Are there any techniques to solve this for an exact closed form? Or in lieu of that, an asymptotic estimation?
I'm mostly interested in how far I need to go to ensure $n_i = O(N^{3/4})$, and I conjecture that $O(\log (N))$ is necessary. But I hope that it can be done in $O(1)$ steps.
Define $u = N^{1/4}$. At every step, $u$ is reduced by at least $1/4$ and at most $1$, since for large $u$
$$(u-\frac{1}{4})^4 \geq u^4 - u^3 \geq (u-1)^4.$$
The process proceeds at a linear rate in $u$ coordinates, about $-1/4$ per step being the correct rate (this needs more complicated analysis to make precise), but for purposes of simple $O()$ estimates any upper and lower bounds on the rate are enough.
Thus, to get from $u$ to a smaller value $u'$ takes $O(u - u')$ steps and actually about $4(u - u')$ steps, up to smaller powers of $u$.
Returning to $N$ coordinates, reducing $N$ to $N^{1/4}$ takes about $4N^{1/4}$ steps.