# Calculate $\lim_{n \rightarrow \infty } \frac{n (1- na_n)}{\log n}$

Given the recursive sequence $\{a_n\}$ defined by setting $0 < a_1 < 1, \; a_{n+1} = a_n(1-a_n) , \; n \ge 1$

Calculate : $$\lim_{n \rightarrow \infty } \frac{n (1- na_n)}{\log n}$$

My attempts : $$\lim_{n \rightarrow \infty } \frac{n (1- n a_n)}{\log n} =\lim_{n \rightarrow \infty }\frac {n \left (\frac{1}{n a_n} -1 \right) n a_n} {\log n}= \lim_{n \rightarrow \infty } \frac {\frac{1}{a_n} - n}{ \log n}$$

Now I am not able to proceed further.

Thank You.

• In the last step, you seem to have assumed that $\lim\limits_{n\rightarrow\infty}na_n=1$, any particular reasons why? Jul 24 '18 at 22:08
• What is the context of this question? Do you believe that the limit is independent of $a_1$? Jul 24 '18 at 22:34
• Hint. We have $$\frac{1}{a_{n+1}} = \frac{1}{a_n} + 1 + a_n + \mathcal{O}(a_n^2).$$ You can use this to show first that $1/a_n = (1+o(1))n$ and then $1/a_n = n + (1+o(1))\log n$. Jul 24 '18 at 22:41
• @BlueRoses I am confident that the asymptotic formula for this recurrence relation has already been answered in this community, though I cannot find it now as I am on my cellphone now. I will update it as soon as I find one (otherwise I will post an answer). Jul 24 '18 at 23:07
• @SangchulLee Hi Sangchul. If the asymptotic expansion you expressed were correct, then the limit of interest would be $1$, independent of $a_1$. Empirical experiment indicates that the limit depends on $a_1$. Of course, I might have made an error in the numerical analysis. But if not and my results are correct, then the asymptotic expansion you presented cannot be correct. Jul 24 '18 at 23:35

Note. The answer below may be excessive compared to what OP is asking.

For a quick answer, read the definition of $(x_n)$, jump directly to the proof of proposition, and then read only the first 3 steps.

Let $a_1 \in (0, 1)$ and define $x_n = 1/a_n$. Then $x_n$ solves the following recurrence relation

$$x_{n+1} = x_n + 1 + \frac{1}{x_n} + \frac{1}{x_n(x_n - 1)}. \tag{1}$$

Using this we progressively reveal the asymptotic behavior of $(x_n)$. More precisely, our goal is to prove the following statement.

Proposition. Let $(x_n)$ be defined by $\text{(1)}$, i.e. $x_1 > 1$ and $x_{n+1} = f(x_n)$ for $f(x) = \frac{x^2}{x-1}$. Then there exists a function function $C : (1, \infty) \to \mathbb{R}$ such that

$$x_n = n + \log n + C(x_1) + \mathcal{O}\left(\frac{\log n}{n}\right) \quad \text{as} \quad n\to\infty.$$

Here, the implicit constant of the asymptotic notation may depend on $x_1$. Moreover, $C$ solves the functional equation $C(f(x)) = C(x) + 1$.

We defer the proof to the end and analyze the asymptotic behavior of OP's limit first. Plugging the asymptotic expansion of $x_n$, we find that

$$r_n := \frac{n(1-n a_n)}{\log n} = \frac{n(x_n - n)}{x_n \log n} = 1 + \frac{C(x_1)}{\log n} + \mathcal{O}\left(\frac{\log n}{n}\right).$$

This tells that, not only that $r_n \to 1$ as $n\to\infty$, but also that the convergence is extremely slow due to the term $C/\log n$.

For instance, $f^{\circ 94}(2) \approx 100.37$ tells that $C(100) \approx C(2) + 94$. Indeed, a numerical simulation using $n = 10^6$ shows that

\begin{align*} x_1 = 2 &\quad \Rightarrow \quad (r_n - 1)\log n \approx 0.767795, \\ x_1 = 100 &\quad \Rightarrow \quad (r_n - 1)\log n \approx 94.3883, \end{align*}

which loosely matches the prediction above.

Proof of Proposition.

Step 1. Since $x_{n+1} \geq x_n + 1$, it follows that $x_n \geq n + \mathcal{O}(1)$. In particular, $x_n \to \infty$ as $n\to\infty$.

Step 2. Since $x_{n+1} - x_n \to 1$, we have $\frac{x_n}{n} \to 1$ by Stolz-Cesaro theorem.

Step 3. Using the previous step, we find that

$$\frac{x_{n+1} - x_n - 1}{\log(n+1) - \log n} = \frac{1}{(x_n - 1)\log\left(1+\frac{1}{n}\right)} \xrightarrow[n\to\infty]{} 1$$

So, again by Stolz-Cesaro theorem, we have $x_{n+1} = n + (1+o(1))\log n$. This is already enough to conclude that OP's limit is $1$.

Step 4. By the previous step, we find that $x_{n+1} - x_n = 1 + \frac{1}{n} + \mathcal{O}\left(\frac{\log n}{n^2}\right)$. Using this, define $C$ by the following convergent series

$$C(x_1) = x_1 - 1 + \sum_{n=1}^{\infty} \underbrace{ \left( x_{n+1} - x_n - 1 - \log\left(1+\frac{1}{n}\right) \right) }_{=\mathcal{O}(\log n/n^2)}.$$

Splitting the sum for $n < N$ and $n \geq N$ and using the estimate $\sum_{n\geq N}\frac{\log n}{n^2} = \mathcal{O}\left(\frac{\log n}{n}\right)$,

$$C(x_1) = x_N - N - \log N + \mathcal{O}\left(\frac{\log N}{N}\right),$$

which confirms the first assertion of the proposition.

Once this is established, then the second assertion easily follows by interpreting $x_{n+1}$ as the $n$-th term of the sequence that solves $\text{(1)}$ with the initial value $f(x_1)$. Hence comparing both

$$x_{n+1} = n+1 + \log(n+1) + C(x_1) + o(1)$$

and

$$x_{n+1} = n + \log n + C(f(x_1)) + o(1)$$

the second assertion follows. ////

I solved this in 1999 via email to David Rusin (was on the web). I found $$\,a_n = f(n) \,$$ where $$f(x) := 1 / (x + c - 0 + \log(x + c - 1/2 + \\ \log(x + c - 17/24 + \log(x + c - \dots))))$$ and $$\,c\,$$ is a constant depending on $$\,a_1.\,$$

Calculate $$\,(1 - x f(x)) x /\log(x) = 1 + c/\log(x) + O(1/x).$$

Thus, $$\,\lim_{n\to \infty}\,(1 - n\,a_n)\ n/\log(n) = 1.$$

Observe that $$\,1/f(x)\,$$ is a power series in $$\,1/x\,$$ (where $$\,y := \log(x)$$): $$\frac1{f(x)} = x + (c + y) + \Big(c - \frac12 + y\Big)\frac1x + \\ \Big(\Big(-\frac56 + \frac32 c-\frac{c^2}2\Big) - \Big(\frac32\ + c\Big)y - \frac{y^2}2\Big)\frac1{x^2} + O\Big(\frac1{x^3}\Big).$$

For another answer see MSE question 2471982 "The asymptotic behavior of the iteration series $$x_{n+1} = x_n -x_n^2$$". Yet another answer is in MSE question 1558592 "Convergence rate of the sequence $$a_{n+1}=a_n-a_n^2, a_0=1/2$$".