Prove that iterated $x_{i + 1} = x_i - \log x_i$ is sublinear. Define a recurrence as: $$x_0 = n, x_{i + 1} = x_i - \log x_i, \forall i \geq 0.$$ Let $N_n$ be such that $x_{N_n} < 1$. Is it possible to show that $N_n \in o(n)$?
Some thoughts: if $x_{i + 1} = x_i - f(x_i)$ and $f$ is constant then $N_n = \frac{n}{f(1)}$ and is thus not sublinear. If $f$ is $\Omega(n)$ then $N_n$ is constant and thus trivially sublinear.  Is $f(x) = \log x$ sufficient to make $N_n$ sublinear?

Edit: As pointed out in the comments, the criteria $x_{N_n} < 1$ can never be met for this question. The correct question should be
Let $N_n$ be the smallest integer such that $x_{N_n} < 10$. Is it possible to show that $N_n \in o(n)$?
 A: The other answers adress the speed of convergence to $1$, which I think is not your question.
I want to reverse the problem. Write $f(x) = x-\log(x)$. Let $M>1$ and $(u_n)$ be the sequence defined by:
$$u_0 = M \text{ and } u_{n+1} = g(u_n),$$
where $g : [1, +\infty) \to [1, +\infty)$ is the inverse bijection to $f$. Then $x_i = g(x_{i+1})$, so that $n = x_0 = g^{(N_n)} (x_{N_n}) < g^{(N_n)} (M) = u_{N_n}$ and $n = x_0 = g^{(N_n-1)} (x_{N_n-1}) \geq g^{(N_n-1)} (M) = u_{N_n-1}$. Note also that
$$\lim_{n \to + \infty} \frac{f(n)}{n} = 1 \text{ so } \lim_{n \to + \infty} \frac{g(n)}{n} = \lim_{n \to + \infty} \frac{f(g(n))}{g(n)} \frac{g(n)}{n} = 1.$$
Since $u$ is increasing, we get that $N_n = \inf \{k \geq 0 : \ u_k > n\}$. This is convenient, since we have translated the initial problem to the study of the growth rate of a single sequence.
Let $L>0$. For $x \geq M$, we have $f(x) = x-\log(x) \leq x-\log(M)$, so that $x \leq g(x-\log(M))$, whence $g(x) \geq x+\log(M)$. It follows that $u_n \geq M + n \log(M)$, so that $\lim_{n \to + \infty} u_n = +\infty$.
Now, let me prove that $u_n$ grows super-linearly. Let $L>0$. Let $n_0$ be such that $u_n \geq 10^L$ for all $n \geq n_0$. By the same argument as above, $g(x) \geq x+L$ for all $x \geq 10^L$. Hence, for all $n \geq n_0$,
$$u_n = u_{n_0} + (u_n-u_{n_0}) \geq u_{n_0} + (n-n_0)L.$$
It follows that $\liminf_{n \to +\infty} u_n/n \geq L$. Since this holds for all $L> 0$, we finally get
$$\lim_{n \to + \infty} \frac{u_n}{n} = +\infty.$$
Specializing to the subsequence $(N_n)$, which also converges to $+\infty$,
$$\lim_{n \to + \infty} \frac{u_{N_n}}{N_n} = +\infty.$$
But $n < u_{N_n} \leq g(n)$, so
$$\lim_{n \to + \infty} \frac{g(n)}{N_n} = +\infty.$$
Finally, since $g(n) \sim n$, we get
$$\lim_{n \to + \infty} \frac{N_n}{n} = 0,$$
that is, $N_n = o(n)$.
The reasoning above can be adapted to many functions instead of $\log$, although many details have to be checked. I think that the result should hold for the recursion $x_{i+1} = x_i-h(x_i)$, where $\inf h>0$ and $\lim_{x \to +\infty} h(x) = +\infty$ as well as $\lim_{x \to +\infty} h(x)/x = 0$, but that is not completely trivial.
A: This is one approach using power series. Define sequence
$$ x_i := 1+y_i, \tag{1}$$ and function
$$ g(x) := x - \log(1+x). \tag{2}$$ Using the recursion we have
$$ y_{i+1} = g(y_i). \tag{3}$$
From previous experience with these iterations, such as
Newton's method, we expect that
$$ f(x^2) = g(f(x)) \tag{4}$$ for some function expressed as
a power series
$$ f(x) := a_1\,x + a_2\,x^2 + a_3\,x^3 + \dots \tag{5}$$
where we solve for the "undetermined coefficients" $\,a_i\,$
one at a time using equation $(4).$
The result of the computations is that we must have
$$ f(x) := 2x + 4/3x^2 + 8/9x^3 + 112/135x^4 + 76/135x^5 + \dots. \tag{6}$$
Thus,
$$ y_0 = n-1 = f(t_0), \tag{7}$$ for some $\,t_0\,$ and
$$ y_n = f(t_0^{\,2^n}) \approx 2t_0^{\,2^n} \tag{8}$$ which implies
$$ x_n \approx 1+2t_0^{\,2^n}. \tag{9}$$
The convergence of $\,x_n\,$ to $1$ is called "quadratic"
or of "second order".
