# Limit of a Recurrence Sequence

$a_0=c$ where $c$ is positive, with $a_n=\log{(1+a_{n-1})}$,Find \begin{align}\lim_{n\to\infty}\frac{n(na_n-2)}{\log{n}}\end{align}

I'have tried Taylor expansion, but I can't find the way to crack this limit. Thanks alot for your attention!

-

You may find an asymptotic formula for $a_n$ by improving the accuracy in an adaptive manner.

Step 1. Since $$0 < a_{n+1} = \log (1+a_n) < a_n,$$ it is a monotone decreasing sequence which is bounded. Thus it must converge to some limit, say $\alpha$. Then $\alpha = \log(1 + \alpha)$, which is true precisely when $\alpha = 0$. Therefore it follows that $$a_n = o(1). \tag{1}$$

Before going to the next step, we make a simple observation: it is easy to observe that the function $$\frac{x}{\log(1+x)}$$ is of class $C^3$. In particular, whenever $|x| \leq \frac{1}{2}$, we have $$\frac{x}{\log (1+x)} = 1+\frac{x}{2}-\frac{x^2}{12}+O(x^3).$$ This can be rephrased as $$\frac{1}{\log(1+x)} = \frac{1}{x}+\frac{1}{2}-\frac{x}{12}+O(x^2). \tag{2}$$ Here, we note that the bound, say $C > 0$, for the Big-Oh notation does not depend on $x$ whenever $|x| \leq \frac{1}{2}$.

Step 2. By noting $(1)$, we fix a positive integer $N$ such that whenever $n \geq N$, we have $|a_n| \leq \frac{1}{2}$. Then by $(2)$, $$\frac{1}{a_{n+1}} - \frac{1}{a_n} = \frac{1}{2} + O(a_n),$$ where the bound for Big-Oh notation depends only on $N$. Indeed, we may explicitly choose a bounding constant as $$C'=\frac{1}{12} + \frac{1}{2}C,$$ where $C$ is the same as in $(2)$. Thus if $n > m > N$, we then have \begin{align*} \frac{1}{a_n} &= \frac{1}{a_{m}} + \sum_{k=m}^{n-1} \left( \frac{1}{a_{k+1}} - \frac{1}{a_k} \right) \\ &= \frac{1}{a_{m}} + \sum_{k=m}^{n-1} \left( \frac{1}{2} + O(a_k) \right) \\ &= \frac{1}{a_{m}} + \frac{n-m}{2} + O((n-m)a_m). \end{align*} Thus we have $$\left|\frac{1}{n a_n} - \frac{1}{2}\right| \leq \frac{1}{n}\left(\frac{1}{a_m} + \frac{m}{2} + C'm a_m \right) + C' a_m.$$ Taking limsup as $n\to\infty$, we have $$\limsup_{n\to\infty}\left|\frac{1}{n a_n} - \frac{1}{2}\right| \leq C' a_m.$$ Since now $m$ is arbitrary, the right-hand side can be made as small as we wish. Thus the left-hand side must vanish, yielding $$\frac{1}{n a_n} = \frac{1}{2} + o(1),$$ or equivalently $$n a_n = 2 + o(1). \tag{3}$$

Step 3. Let $N$ be as in the previous step. Then $(3)$ suggests that it is natural to consider $$\left( \frac{1}{a_{n+1}} - \frac{n+1}{2} \right) - \left( \frac{1}{a_{n}} - \frac{n}{2} \right) = -\frac{a_n}{12} + O(a_n^2).$$ Now from $(3)$, we have $$a_n = \frac{2}{n} + o\left(\frac{1}{n}\right) = 2(\log(n+1) - \log n) + o\left(\frac{1}{n}\right) = O\left(\frac{1}{n}\right).$$ Plugging this to the equation above, we have $$\left( \frac{1}{a_{n+1}} - \frac{n+1}{2} \right) - \left( \frac{1}{a_{n}} - \frac{n}{2} \right) = -\frac{1}{6}\left( \log(n+1) - \log n \right) + o\left(\frac{1}{n}\right).$$ Now for each $\epsilon > 0$, choose $m > N$ such that whenever $n > m$, the Small-Oh term is bounded by $\epsilon / n$. Then for such $n$ we have $$\left| \left( \frac{1}{a_{n+1}} - \frac{n+1}{2} + \frac{1}{6}\log(n+1) \right) - \left( \frac{1}{a_{n}} - \frac{n}{2} + \frac{1}{6}\log n \right) \right| \leq \frac{\epsilon}{n}.$$ Thus summing up from $m$ to $n-1$, we have $$\left| \frac{1}{a_{n}} - \frac{n}{2} + \frac{1}{6}\log n \right| \leq \left| \frac{1}{a_{m}} - \frac{m}{2} + \frac{1}{6}\log m \right| + \epsilon (\log n - \log m).$$ Dividing both sides by $\log n$ and taking $n \to \infty$, we have $$\limsup_{n\to\infty} \frac{1}{\log n} \left| \frac{1}{a_{n}} - \frac{n}{2} + \frac{1}{6}\log n \right| \leq \epsilon.$$ Since this is true for every $\epsilon > 0$, it must vanish. Therefore we have $$\frac{1}{a_{n}} = \frac{n}{2} - \frac{1}{6}\log n + o(\log n).$$ In particular, \begin{align*}a_n &= \left( \frac{n}{2} - \frac{1}{6}\log n + o(\log n) \right)^{-1} \\ &= \frac{2}{n} \left( 1 - \frac{1}{3n}\log n + o\left( \frac{\log n}{n} \right) \right)^{-1} \\ &= \frac{2}{n} + \frac{2}{3n^2} \log n + o\left( \frac{\log n}{n^2} \right). \end{align*} Therefore $$\frac{n(na_n - 2)}{\log n} = \frac{2}{3} + o(1)$$ and it follows that the limit is $$\lim_{n\to\infty} \frac{n(na_n - 2)}{\log n} = \frac{2}{3}.$$

Further discussions. In fact, we can show that $$a_n = \frac{2}{n} + \frac{2}{3n^2} \log n + O\left( \frac{1}{n^2} \right).$$ More generally, we have the following proposition.

Proposition. Suppose $(a_n)$ is a sequence of positive real numbers converging to 0 and satisfying the recurrence relation $a_{n+1} = f(a_n)$.

1. If $f(x) = x \left( 1 - (a + o(1)) x^m \right)$ for some real $a \neq 0$ and integer $m \geq 1$, then $$a_n = \frac{1}{\sqrt[m]{man}}(1 + o(1)).$$

2. If $f(x) = x \left( 1 - a x^m + (b+o(1)) x^{2m} \right)$ for some some reals $a \neq 0$ and $b$, and integer $m \geq 1$, then $$a_n = \frac{1}{\sqrt[m]{man}} \left( 1 - \frac{(m+1) a^2 - 2 b}{2m^2a^2} \frac{\log n}{n} + o \left( \frac{\log n}{n} \right) \right).$$

3. If $f(x) = x \left( 1 - a x^m + b x^{2m} + O(x^{3m}) \right)$ for some reals $a \neq 0$ and $b$, and integer $m \geq 1$, then $$a_n = \frac{1}{\sqrt[m]{man}} \left( 1 - \frac{(m+1) a^2 - 2 b}{2m^2a^2} \frac{\log n}{n} + O \left( \frac{1}{n} \right) \right).$$

-
Thank you for your sooo..o detailed proof! –  Golbez Oct 21 '12 at 13:10