$\lim_{k \to \infty} \frac{x_k}{k^2}$ Let $(x_k)$ be the sequence of real numbers defined as follows: $x_1=1$; $x_{k+1}=x_k+\sqrt {x_k}$ for $k>0$. Find $$\lim_{k \to \infty} \frac{x_k}{k^2}$$ My thought is to find some $y_k$ which is a function of $x_k$ and find the limit of this $y_k$, but I'm not sure if this will work, or what my $y_k$ should be.
 A: Let $l=\lim_{k\to\infty}\frac{x_k}{k^2}$. Then by the Stolz-Cesàro theorem,
\begin{eqnarray}
l=\lim_{k\to\infty}\frac{x_k}{k^2}=\lim_{k\to\infty}\frac{x_{k+1}-x_k}{(k+1)^2-k^2}=\lim_{k\to\infty}\frac{\sqrt x_k}{2k+1}=\lim_{k\to\infty}\sqrt{\frac{x_k}{k^2}}\frac{k}{2k+1}=\frac12\sqrt{l}
\end{eqnarray}
and hence $l=0$ or $l=\frac14$. Note that $x_1>\frac1{16}$. Assume that $x_k>\frac{k^2}{16}$. Then
$$ x_{x+1}=x_k+\sqrt x_k>\frac{k^2}{16}+\frac{k}{4}=\frac{k^2+4k}{16}>\frac{(k+1)^2}{16}. $$
Thus $x_k>\frac{k^2}{16}$ for $k\ge 1$ and hence $\frac{x_k}{k^2}>\frac1{16}>0$.
So you can rule out $l=0$ and hence
$$ l=\lim_{k\to\infty}\frac{x_k}{k^2}=\frac14. $$
A: Write $y_k=2\sqrt{x_k}$. 
Then the given equation becomes $y_{k+1}^2+1=(y_k+1)^2$.
Now prove by induction that $\sqrt{k^2-1}-1 \leq y_k \leq k+1$.
Thus, $y_k/k \to 1$ and $x_k/k^2 \to 1/4$. 
A: Here is an argument that avoids the Stolz-Cesaro theorem:
You can prove by induction that $\dfrac {k^2}{9} \le x_k \le \dfrac{(k+1)^2}4$ for all $k$. Clearly $\dfrac 19 \le x_1 \le 1$, $$x_k \ge \frac{k^2}{9} \implies x_{k+1} = x_k + \sqrt{x_k} \ge \frac{k^2}{9} + \frac{k}{3} > \frac{k^2 + 2k + 1}{9} = \frac{(k+1)^2}{9},$$ and $$ x_k \le \frac{(k+1)^2}{4} \implies x_{k+1} = x_k + \sqrt{x_k} \le \frac{(k+1)^2}{4} + \frac{k+1}2 = \frac{k^2 + 4k + 3}4 < \frac{(k+2)^2}4.$$
Let $I = \liminf \dfrac{x_k}{k^2}$ and $J = \limsup \dfrac{x_k}{k^2}$. The remarks above imply $\dfrac 19 \le I \le J \le \dfrac 14$. Fix $0 < \epsilon < I$. Then there exists an index $K$ so that $k \ge K$ implies $\dfrac{x_k}{k^2} > I - \epsilon$. Consequently $$k \ge K \implies \frac{x_{k+1} - x_k}{k} = \sqrt{ \frac{x_k}{k^2}} > \sqrt{I - \epsilon} \implies x_{k+1} - x_k \ge k \sqrt{I - \epsilon}.$$ Now let $N > K$. It follows that $$x_N - x_K = \sum_{k=K}^{N-1} (x_{k+1} - x_k) \ge \sqrt{I - \epsilon} \sum_{k=K}^{N-1} k = \sqrt{I - \epsilon} \left( \frac{N(N-1)}2 - \frac{K(K+1)}{2} \right).$$ Divide the last inequality by $N^2$ and let $N \to \infty$ to find that $$I = \liminf_{N \to \infty} \frac{x_N}{N^2} \ge \frac{\sqrt{I - \epsilon}}2.$$ Now take $\epsilon \to 0^+$ to find $I \ge \dfrac{\sqrt{I}}2$ which implies (since $I > 0$) that $I \ge \dfrac 14$.
It follows that $\dfrac 14 \le I \le J \le \dfrac 14$ so that $I = J = \dfrac 14$ and thus $\dfrac{x_k}{k^2} \to \dfrac 14.$
