3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}.$$ $\endgroup$ – Clement C. Feb 15 '16 at 12:57
  • $\begingroup$ @ClementC. I have tried it, but I didn't find out what to do next. $\endgroup$ – Yijun Yuan Feb 15 '16 at 13:14
  • $\begingroup$ The series is increasing. @Clement C.'s method thus suggests the series is divergent. $\endgroup$ – Laurent Duval Feb 15 '16 at 13:27
  • $\begingroup$ But it's the rate of divergence that seems to be the question. $\endgroup$ – Clement C. Feb 15 '16 at 13:36
  • $\begingroup$ 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}$.) $\endgroup$ – Clement C. Feb 15 '16 at 13:57
4
$\begingroup$

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

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

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.