11
$\begingroup$

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.

Please help me.

Thank You.

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

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.