Prove that iterated $x_{i + 1} = x_i - \log x_i$ is sublinear.

Question

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)$?

Answer 1

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.

Answer 2

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".

Answer 3

It is interesting to notice that this looks like a Newton iterative scheme for solving the equation $f(x)=a$.

Since we do not know what is $f(x)$, writing $$x_{n+1}=x_n-\frac{f(x_n)-a}{f'(x_n)}$$ we have $$\frac{f(x)-a}{f'(x)}=\log(x)\implies \frac{f'(x)}{f(x)-a}=\frac 1{\log(x)}$$ $$\implies\log(f(x)-a)=\text{li}(x)+c\implies \color{blue}{f(x)=a+c\,e^{\text{li}(x)}}$$ where $\text{li}(x)$ is the logarithmic integral function.

The function $e^{\text{li}(x)}$ is, for sure, always positive and it is equal to $0$ when $x=1$ but, at this point, it is discontinuous.

Around $x=1^-$, we have $$e^{\text{li}(x)}=-e^{\gamma } (x-1)-\frac{1}{2} e^{\gamma } (x-1)^2+O\left((x-1)^3\right)$$ while around $x=1^+$, $$e^{\text{li}(x)}=e^{\gamma } (x-1)+\frac{1}{2} e^{\gamma } (x-1)^2+O\left((x-1)^3\right)$$

Since it is Newton, the process is quadratic.

For illustration purposes, trying for $a=123456$, $c=\pi$ and using $x_0=30$, we have the following iterates $$\left( \begin{array}{cc} n & x_n \\ 0 & 30.000000000000000000000000000000000000000000000000 \\ 1 & \color{red}{2}6.894152524358982809170572349163498313534833470925 \\ 2 & \color{red}{2}4.325223169265492626304969903408926811220213329449 \\ 3 & \color{red}{22.}681722534270713557158529795786301254378897174602 \\ 4 & \color{red}{22.}108470739953112533158686496921157728291987229732 \\ 5 & \color{red}{22.051}702027826858474857702973272665751388334724225 \\ 6 & \color{red}{22.0511991}43990547095115344666363810856986277372042 \\ 7 & \color{red}{22.051199104963862}951102891406188800145947352942244 \\ 8 & \color{red}{22.0511991049638627160819846994044}13283687608959958 \\ 9 & \color{red}{22.051199104963862716081984699404404760615124872753} \end{array} \right)$$ which is typical of a second order method.