# Limit involving a recursively-defined sequence

$$A_{n+1}=A_n+\frac{1}{\sum_{i=1}^n A_i}$$ with $$A_1=1$$

Find out the value of $$\lim_{n→∞}A_n/\sqrt{\log(n)}$$

I used Stolz Theorem, but it seems to be useless.

• For what it's worth, you could try to look at the sequence $a_n = \sum_{k=1}^n A_n$, which has $a_1=1$ and satisfies $$a_{n+1} = 2a_n-a_{n-1}+\frac{1}{a_n}.$$ – Clement C. Feb 15 '16 at 12:57
• @ClementC. I have tried it, but I didn't find out what to do next. – Yijun Yuan Feb 15 '16 at 13:14
• The series is increasing. @Clement C.'s method thus suggests the series is divergent. – Laurent Duval Feb 15 '16 at 13:27
• But it's the rate of divergence that seems to be the question. – Clement C. Feb 15 '16 at 13:36
• Using heuristic arguments, the limit should (may) be $\frac{1}{\sqrt{2}}$ -- not sure it helps. (I can detail below if needed, but if one assumes $A_n \sim_{n\to\infty} B_n = a\sqrt{\ln n}$ and plugs $B_n$ in the recurrence relation, one only has $B_{n+1}-B_n \sim_{n\to\infty} \frac{1}{\sum_{k=1}^n B_k}$ for $a = \sqrt{2}$.) – Clement C. Feb 15 '16 at 13:57

First, you have that $A_n \ge 1$ for all $n \ge 1$.

Now let $B_n = {A_n}^2$ and $C_n=\sum\limits_{k=1}^n A_k$ so you have $C_n \ge n$ , $\frac{1}{C_n} \le \frac{1}{n}$, $A_n =A_1 + \sum\limits_{k=1}^n \frac{1}{C_k} \le 1+\sum\limits_{k=1}^n \frac{1}{k} = 1+H_n = O( \log(n))$ and $C_n = \sum_{k=1}^n A_k = \sum_{k=1}^n O( \log(k)) = O(n\log(n))$.

Moreover $B_{n+1}={A_{n+1}}^2 = {A_n}^2 + \frac{1}{ {(\sum_1^n A_i)}^2} + 2 \frac{A_n}{(\sum_1^n A_i)} = B_n + \frac{1}{{C_n}^2} + 2\frac{A_n}{C_n}$.

Since $\frac{1}{{C_n}^2} = o\left(\frac{A_n}{C_n}\right)$, $B_{n+1}-B_n \sim 2 \frac{A_n}{C_n}$, therefore $B_n \sim 2 \sum\limits_{k=1}^{n} \frac{A_k}{C_k}$.

Now you have for all $k\ge2$ ,$\frac{A_k}{C_k} \le \int\limits_{C_{k-1}}^{C_k} \frac{dt}{t}$ so $\sum_{k=1}^n \frac{A_k}{C_k} \le \int\limits_{C_{0}}^{C_n} \frac{dt}{t}= \log({C_n})$.

I let you do the other inequality to show that $\sum_{k=1}^n \frac{A_k}{C_k} \sim \log({C_n}) \sim \log(n)$.

So finally $A_n \sim \sqrt{ 2\log(n)}$

• Thanks for pointing out, it was a typo. – yultan Feb 15 '16 at 14:15
• Nice solution! ${}$ – Clement C. Feb 15 '16 at 14:21