# A seemingly tricky sequence

Let be the sequence $(x_{n})$, $n \geq 0$ with $x_{0}>0$, and for any $n$ natural number, $x_{n+1}=x_{n}+\frac{1}{\sqrt{x_{n}}}$. I'm required to calculate: $$\lim_{n\rightarrow\infty} \frac{{x_{n}}^{3}}{{n}^{2}}$$

I still try to figure out what part I should start with. Any solution is very welcomed.

-
Hint: $x_1 \geq 1$ (Why?) and so $x_0 \leq x_{n+1} \leq x_{n} +1$. –  cardinal May 31 '12 at 19:51

The associated differential equation is $\xi'(t)=\frac1{\sqrt{\xi(t)}}$, whose solutions are $\xi(t)^{3/2}=\frac32t+C$. This suggests to look at the sequence $(z_n)$ defined by $z_n=x_n^{3/2}$. Thus, $$z_{n+1}=z_n(1+z_n^{-1})^{3/2}.$$ First, $(1+u)^{3/2}\geqslant1+\frac32u$ for every $u\geqslant0$ hence $z_{n+1}\geqslant z_n+\frac32$, thus $z_n\geqslant\frac32n+z_0$ and in particular $z_n\to+\infty$.

On the other hand, $(1+u)^{3/2}\leqslant1+\frac32u+\frac38u^2$ for every $u\geqslant0$ hence $z_{n+1}\leqslant z_n+\frac32+\frac38z_n^{-1}$. This shows that $z_n\leqslant\frac32n+z_0+\frac38t_n$ with $t_n=\sum\limits_{k=0}^{n-1}z_k^{-1}$. Since $z_n\to+\infty$, $t_n=o(n)$ and $z_n\leqslant\frac32n+o(n)$. Finally, $\frac{z_n}n\to\frac32$ hence $$\lim\limits_{n\to\infty}\frac{x_n^3}{n^2}=\frac94.$$

-
There might be a typo in the question, the exponents $2$ and $3$ being exchanged in $x_n^2/n^3$. –  Did May 31 '12 at 20:02
See here. –  Did May 31 '12 at 20:13
(+1) For clairvoyance. –  cardinal May 31 '12 at 20:15
No. The differential equation is an indication of a possible behaviour of the sequence $(x_n)$, which has to be proved. By the way, $x_n^3$ is not $(\frac32n+C)^2$ because $z_n$ is not $\frac32n+C$. One only knows that $z_n$ is between $\frac32n+z_0$ and $\frac32n+nu_n$ with $u_n\to0$. –  Did Jun 1 '12 at 10:36

You had a typo in the question, so let's explore a slightly more general solution.

Suppose there is a positive finite limit of $\lim_{n\to\infty}\dfrac{x_n}{n^k} = c$ for some $c$ and $k$.

Then for large $n$, $x_n \approx c n^k$ and $x_{n+1}-x_n \approx \dfrac{1}{\sqrt{c} n^{k/2}}$ but taking $n$ as real $\frac{dx}{dn} \approx kcn^{k-1}$. To make these two correspond you need $k-1=-k/2$ and $kc=1/\sqrt{c}$ which have the solutions $k=\dfrac{2}{3}$ and $c=\sqrt[3]{\dfrac94}$.

So the limit of $\dfrac{x}{n^{2/3}}$ is $\sqrt[3]{\dfrac94}$ and of $\dfrac{x^3}{n^{2}}$ is ${\dfrac94}$.

For a formal proof see did's answer.

-
@Chris: OK $\frac{x_n}{n^k}$. I didn't put a power for $x_n$ at that stage because I hadn't calculated it. –  Henry May 31 '12 at 20:25