Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

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

[Added later]

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} $

which leads to,

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

share|improve this answer
add comment

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

share|improve this answer
1  
$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$. –  ACARCHAU 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. –  ACARCHAU Nov 19 '13 at 0:53
add comment

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}}$

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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