Difficult limit proof Let $a_1 = 1$ and define a sequence recursively by $$a_{n+1} = \sqrt{a_1+a_2+\dots+a_n}.$$ Show that $\lim_{n \to \infty} \frac{a_n}{n} = \frac{1}{2}$.
So far, I've written $a_{n+1} = \sqrt{a_n^2 + a_n}$, and have shown that if $a_n/n < 1/2$, then so is $a_{n+1}/{(n+1)}$. I'm really not sure how to relate the recurrence relation to the limit we want, though.
 A: The Stolz-Cesaro theorem states the following:

Let $a, b$ be sequences of real numbers such that $b$ is monotone increasing and $\lim\limits_{n \to \infty} b_n = \infty$. If $\lim\limits_{n \to \infty} \frac{a_{n + 1} - a_n}{b_{n + 1} - b_n} = \ell$ then $\lim\limits_{n \to \infty} \frac{a_n}{b_n} = \ell$.

It's basically the discrete version of L'Hopital's rule. For more details, see the Wikipedia page.
In this case, let $b_n = n$. Then we must compute $\lim\limits_{n \to \infty} \frac{a_{n + 1} - a_n}{b_{n + 1} - b_n} = \lim\limits_{n \to \infty} a_{n + 1} - a_n$.
We have
\begin{equation}
\begin{split}
 a_{n + 1} - a_n &= \sqrt{a_n^2 + a_n} - a_n \\
&= (\sqrt{a_n^2 + a_n} - a_n) \frac{\sqrt{a_n^2 + a_n} + a_n}{\sqrt{a_n^2 + a_n} + a_n} \\
&= \frac{a_n}{\sqrt{a_n^2 + a_n} + a_n} \\
&= \frac{1}{\sqrt{1 + 1 / a_n} + 1}
\end{split}
\end{equation}
Therefore, we see that $\lim\limits_{n \to \infty} a_{n + 1} - a_n = \lim\limits_{n \to \infty} \frac{1}{\sqrt{1 + 1/a_n} + 1} = \frac{1}{2}$.
Note that this does require showing that $\lim\limits_{n \to \infty} a_n = \infty$. But this is trivial, since we know that $a$ is increasing, and therefore $a_{n + 1} - a_n = \frac{1}{\sqrt{1 + 1 / a_n} + 1} \geq \frac{1}{\sqrt{1 + 1 / 1} + 1} = \frac{1}{\sqrt{2} + 1}$. From this it follows that $a_n \geq n \frac{1}{\sqrt{2} + 1}$ for all $n$.
