Finding the limits related to $a_1=1$, $a_{k+1}=\sqrt{a_1+a_2+\cdots +a_k}$

Question

Suppose $a_1=1, a_{k+1}=\sqrt{a_1+a_2+\cdots +a_k}, k \in \mathbb{N}$. Find the limits

$$i)\space \lim_{n\to\infty}\displaystyle \frac{\sum_{k=1}^{n} a_{k}}{n\sqrt{n}}$$ $$ii)\space \lim_{n\to\infty}\displaystyle \frac{\sum_{k=1}^{n} a_{k}}{n^2}$$

I'm puzzled with it. What to do?

Answer 1

For $n > 1$, we have $$a_{n+1}^2 = a_{n} + ( a_{n-1} + \ldots + a_{1} ) = a_{n} + a_{n}^2$$ This implies $$\displaystyle a_{n+1} = \sqrt{a_n^2 + a_n} < \sqrt{a_n^2 + a_n +\frac14} = a_n + \frac12$$ Notice $a_2 = \sqrt{a_1} = 1$, this gives us an upper bound $a_m \le \frac{m}{2}$ for $m > 1$.

As pointed out by robjohn, there is a mistake in original derivation of a lower bound.
To obtain a correct lower bound, we will construct it in 3 stages.

1. It is clear $a_k$ is an increasing sequence and since $a_1 = 1$, we have $a_k \ge 1$ for all $k$.

2. Since $\quad a_{n+1} = \sqrt{ a_n^2 + a_n } \ge \sqrt{ a_n^2 + \frac23 a_n + \frac13} > a_n + \frac13\quad$ and $a_1 = a_2 = 1 $,
   we get $a_m > \frac{m}{3}$ for $m > 0$.

3. Observe $\displaystyle\quad(a_n + \frac12 - \frac{1}{8a_n})^2 = a_n^2 + a_n - \frac{1}{8a_n} ( 1 - \frac{1}{8a_n}) < a_{n+1}^2.$
   The lower bound from $2^{nd}$ stage implies $$\begin{align} & a_{n+1} > a_n + \frac12 - \frac{1}{8a_n} > a_n + \frac12 - \frac{3}{8n}\\ \implies & a_m \ge \frac{m}{2} - \frac{3}{8} \sum_{k=2}^{m-1}\frac{1}{k}\;\;\text{ for }m > 2 \end{align}$$

Since $\displaystyle \sum_{k=2}^{m-1}\frac{1}{k} \sim \log m + O(1)$ for large $m$, we find $\displaystyle\quad a_m = \frac{m}{2} + O(\log m)\quad$ as $m \to \infty$.

For the first limit, we have the estimate:

$$\frac{\sum_{k=1}^{n}a_k}{n\sqrt{n}} = \frac{a_{n+1}^2}{n\sqrt{n}} = \frac{\left(\frac{n}{2} + O(\log n)\right)^2}{n\sqrt{n}} \sim O(\sqrt{n})$$

This implies the first limit diverges. For the second limit, we have

$$\frac{\sum_{k=1}^{n}a_k}{n^2} = \frac{a_{n+1}^2}{n^2} = \frac{\left(\frac{n}{2} + O(\log n)\right)^2}{n^2} = \frac14 + O(\frac{\log n}{n})$$

Since $\lim_{n\to\infty} \frac{\log n}{n} = 0$, the second limit exists and equal to $\frac14$.

Answer 2

For $n\ge1$, we have $$ \sum_{k=1}^na_k=a_{n+1}^2\tag{1} $$ $(1)$ leads to $a_{n+1}^2-a_n^2=a_n$ which implies that $a_n$ is increasing and that $$ a_{n+1}-a_n=\frac{a_n}{a_{n+1}+a_n}\le\frac12\tag{2} $$ In fact, $$ \frac12-\frac{a_n}{a_{n+1}+a_n}=\frac12\frac{a_{n+1}-a_n}{a_{n+1}+a_n}\le\frac12\frac{\frac12}{2a_n}=\frac1{8a_n}\tag{3} $$ Thus, $(2)$ and $(3)$ say that $$ \frac38\le\frac12-\frac1{8a_n}\le a_{n+1}-a_n\le\frac12\tag{4} $$ Summing $(4)$ yields $$ \frac{3n+5}{8}\le a_n\le\frac{n+1}{2}\tag{5} $$ We can use $(5)$ to improve $(4)$: $$ \frac12-\frac1{3n+5}\le a_{n+1}-a_n\le\frac12\tag{6} $$ Since $$ \sum_{k=1}^{n-1}\frac1{3n+5}\le\int_0^{n-1}\frac{\mathrm{d}x}{3x+5}=\frac13\log\left(\frac{3n+2}{5}\right)\tag{7} $$ Summing $(6)$ yields $$ \frac{n+1}{2}-\frac13\log\left(\frac{3n+2}{5}\right)\le a_n\le\frac{n+1}{2}\tag{8} $$

---

To handle $i)$, $$ \begin{align} \frac1{n^{3/2}}\sum_{k=1}^na_n &=\frac1{n^{3/2}}a_{n+1}^2\\ &\ge\frac1{n^{3/2}}\left(\frac{n+2}{2}-\frac13\log\left(\frac{3n+5}{5}\right)\right)^2\\[12pt] &\to\infty\tag{9} \end{align} $$ To handle $ii)$, $$ \begin{align} \frac1{n^2}\sum_{k=1}^na_n &=\frac1{n^2}a_{n+1}^2\tag{10} \end{align} $$ Applying $(8)$ yields $$ \frac1{n^2}\left(\frac{n+2}{2}-\frac13\log\left(\frac{3n+5}{5}\right)\right)^2 \le\frac1{n^2}a_{n+1}^2 \le\frac1{n^2}\left(\frac{n+2}{2}\right)^2\tag{11} $$ So by the Squeeze Theorem, we have $$ \lim_{n\to\infty}\frac1{n^2}\sum_{k=1}^na_n=\frac14\tag{12} $$