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

• I have edited the question, and have improved the formatting. Please check your question, in case I have edited something wrongly. – Jaideep Khare Jul 24 '18 at 21:36
• In the last step, you seem to have assumed that $\lim\limits_{n\rightarrow\infty}na_n=1$, any particular reasons why? – rtybase Jul 24 '18 at 22:08
• What is the context of this question? Do you believe that the limit is independent of $a_1$? – Mark Viola 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$. – Sangchul Lee 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). – Sangchul Lee Jul 24 '18 at 23:07

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. \$

Notice that we can also express $\ 1/f(x) \$ as a series of powers of $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.$"