# Asymptotic behaviour of $a_{k+1}=a_{k}(1+\frac{1}{\log a_{k}})$

Let $a_{k}$ be a sequence of real numbers defined recursively as follows

$a_{k+1}=a_{k}(1+\frac{1}{\log a_{k}})$ with the initial value $a_{1}=10$.

How can we(or can we?) determine asymptotic behavior of the sequence $a_{k}$ as $k \to \infty$? One can however show that, it doesn't grow exponentially. One can also show that for any $n$ positive real

$$a_{k} \gg k^n$$ where the implied constant depends only on $n$.

-

Following mjqxxx let $b_k = \log a_k$, and we have $b_{k+1} = b_k + \log(1+1/b_k)$.

We first show $b_k \to \infty$.

If $b_k > 0$ for some $k$ then $1+1/b_k > 1$ and $b_{k+1} - b_k = \log( 1 + 1/b_k) > 0$ and hence $b_{k+1} > b_k > 0$. Since we have $b_1 = \log 10 > 0$, this means $b_k$ increases and each $b_k > 0$. If $b_k \to \infty$ is not true then there is a real $b$ such that $b_k \to b$ and it satisfies $b = b + \log(1+1/b)$, i.e., $\log(1+1/b) = 0$ which is impossible, hence $b_k \to \infty$.

We have $b^2_{k+1} = b^2_k + 2b_k\log(1+1/b_k) + \log^2(1+1/b_k)$, hence $b^2_{k+1} - b^2_k = 2 \log(1+1/b_k)/(1/b_k) + \log^2(1+1/b_k) \to 2.$

The means of $d_k = b^2_{k+1}-b^2_{k}$ must converge to the same limit as $d_k$, hence $\sum_{k=1}^{n}d_k / n \to 2$, i.e., $b^2_{n+1}/n -b^2_1/n \to 2$ so : $b^2_{n+1}/n \to 2$ and $b_{n+1}/\sqrt{n} \to \sqrt{2}$, i.e., $b_n \sim \sqrt{2n}$.

Now we will show $a_n = \exp\left( \sqrt{2n} + \text{O}(1) \right)$.

From $b_{k+1} = b_k + \log(1+1/b_k)$ we have $b_{k+1} = b_k + 1/b_k - 1/2b^2_k + 1/3b^3_k + \text{O}(1/b^4_k)$.

So $b^2_{k+1} = b^2_k+2-1/b_k + 5/3\times1/b^2_k + d_k,$ where $d_k = \text{O}(1/b_k^3) = \text{O}(1/k^{3/2})$ and hence $\sum_{k\geq 1} |d_k| < \infty$.

We have from $b^2_{k+1} - b^2_k = 2-1/b_k + 5/3\times1/b^2_k + d_k$ that

\begin{align} \sum_{k=1}^{n-1} (b^2_{k+1} - b^2_k) &= 2n - 2 - \sum_{k=1}^{n-1} 1/b_k + 5/3 \times \sum_{k=1}^{n-1}1/b^2_k + \text{O}(1) \end{align}

\begin{align} b^2_n &= 2n - \sum_{k=1}^{n}1/b_k + 5/3 \times \sum_{k=1}^{n} 1/b^2_k + \text{O}(1)\\ b_n &= \sqrt{ 2n - \sum_{k=1}^{n}1/b_k + 5/3 \times \sum_{k=1}^{n} 1/b^2_k + \text{O}(1)} \end{align}.

We will show $\sum_{k=1}^{n}1/b_k = \text{O}(\sqrt{n})$ and $\sum_{k=1}^{n}1/b^2_k = \text{O}(\log n)$.

Assuming the truth of the above we have, $a_n = \exp \sqrt{ 2n + \text{O}(\sqrt{n}) + \text{O}(\log n) + \text{O}(1)} = \exp \sqrt{2n + \text{O}(\sqrt{n})}$.

Consider any $c_n$ with $c_n = \text{O}(\sqrt{n})$, then $\sqrt{2n + c_n} - \sqrt{2n} = \dfrac{c_n}{\sqrt{2n+c_n} + \sqrt{2n}} = \dfrac{\dfrac{c_n}{\sqrt{2n}}}{{\sqrt{1+\dfrac{1}{2\sqrt{n}}\dfrac{c_n}{\sqrt{n}}} + 1}} = \text{O}(1)$ i.e., $\sqrt{2n+\text{O}(\sqrt{n}}) = \sqrt{2n} + \text{O}(1).$

Proof ${\bf \sum_{k=1}^{n} 1/b_k = \text{O}(\sqrt{n})}$

Since, $b_k \sim \sqrt{2k}$, given any $0 < \alpha^* < 1 < \beta^*$ we have for sufficiently large $k$, say $k \geq m$, $\alpha^* < \sqrt{2k} / b_k < \beta^*$.

Letting $\alpha = \min \{ \alpha^{*},\sqrt{2}/b_1,\dots, \sqrt{2(m-1)}/b_{m-1} \}$ and $\beta = \max \{\beta^*, \sqrt{2}/b_1,\dots, \sqrt{2(m-1)}/b_{m-1} \}$ then $\alpha > 0$ and $\beta > 0$ are such that $\alpha < \sqrt{2k} / b_k < \beta$ for all $k$.

So $$\frac{\alpha}{\sqrt{2}} \sum_{k=1}^{n} \dfrac{1}{\sqrt{k}} \leq \sum_{k=1}^{n} \dfrac{1}{b_k} \leq \frac{\beta}{\sqrt{2}} \sum_{k=1}^{n} \frac{1}{\sqrt{k}}.$$

Now, $$\frac{\beta}{\sqrt{2}} \sum_{k=1}^{n} \dfrac{1}{\sqrt{k}} \leq\frac{\beta}{\sqrt{2}} \int_{0}^{n} \dfrac{1}{\sqrt{x}}dx = 2\frac{\beta}{\sqrt{2}} \sqrt{n}.$$

Similarly, $$\frac{\alpha}{\sqrt{2}} \sum_{k=1}^{n} \dfrac{1}{\sqrt{k}} \geq \frac{\alpha}{\sqrt{2}} \int_{1}^{n+1} \frac{1}{\sqrt{x}}dx = 2\frac{\alpha}{\sqrt{2}}( \sqrt{n+1}-1).$$

Hence proved.

Proof that $\sum_{k=1}^{n}1/b_k^2 = \text{O}(\log n)$ is similar.

-

Letting $b_k=\log a_k$, you have $$b_{k+1}=b_{k} + \log\left(1+\frac{1}{b_k}\right)=b_k+\frac{1}{b_k}+O(b_k^{-2}),$$ or $$\Delta(b_{k}^2)=2b_k\Delta b_{k}=2+O(b_k^{-1}).$$ This suggests that $$b_k^2\sim 2k + C,$$ plus corrections of lower order; hence $b_k\sim \sqrt{2k + C}$ and $$a_k=e^{b_k} \sim e^{\sqrt{2k + C}}.$$

-
$a_k \sim b_k$ does not imply $\exp a_k \sim \exp b_k$ example $a_k = k$ and $b_k = k + \ln k$. – Arin Chaudhuri Nov 19 '13 at 0:21
@ACARCHAU: Right, but $a_k \sim b_k + o(1)$ does imply $\exp a_k \sim \exp b_k$. That's why I included the "+C" term. – mjqxxxx Nov 19 '13 at 0:44
You are correct, I missed that. – Arin Chaudhuri Nov 19 '13 at 0:53

Corrected: my previous answer had a mistake. However, the sequence can still be asymptotically analysed using the same approach:

$a_{k+1}-a_k=\frac{a_k}{log(a_k)}$

A decent thumb rule would be to replace the above finite difference with a smooth version:

$\frac{d a}{d n}=\frac{a}{log(a)}$

which solves easily by separation of variables:

$\frac{log(a)}{a}da=dn$

now let $t = log(a)$

$t\cdot dt = log(a)\cdot \frac{1}{a} da=dn$

$t^2/2=n+C$

$log(a)=t=\pm\sqrt{2n+2C}$

$a=e^{\pm\sqrt{2n+2C}}$

-
Something is wrong here. The sequence you study is not the same as I ask. – user80242 Nov 18 '13 at 19:52
I like the approach, but it should be $da/dn = a/\log a$ as pointed out. – Jonathan Nov 18 '13 at 20:27