<s>[INST] $\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.
 [/INST] 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.$
</s>