Finding Limit of Expression involving Recursive Sequence

Question

Let $(x_n)_{n\geq1}$ be a sequence such that $x_1 = x >1$ and

\begin{align} x_{n+1}=x_n + \sqrt{x_n} - 1, n\geq 1\\ \end{align}

Evaluate

\begin{align} \lim_{n\to \infty} \frac{4x_n -n^2}{n \log n} \end{align}

My attempt: Let $y_n=\sqrt{x_n}$, we now have $\lim_{n\to \infty} \frac{4y_{n}^2 -n^2}{n \log n}$

I am trying to find an upper bound to the absolute value of this expression by removing the log, however I'm not sure of any lower bound to log.

Update: Since $y_{n+1}^2 = y_n^2 + y_n - 1 = (y_n + \frac{1}{2})^2 - \frac{5}{4}$, we have $y_{n+1} < y_n + \frac{1}{2}$ so $2y_n -n = O(n)$ (Not sure if this is valid). Writing $\frac{4y_{n}^2 -n^2}{n \log n}$ as $\frac{2y_n - n}{n} \frac{2y_n + n}{\log n}$ the first fraction's abs value will approach one. However then I''m stuck with the second fraction.

Any hints appreciated.

Answer 1

Since $y_1>1$, we see by induction that $y_{n+1}>y_n>1$. The sequence is monotone increasing, but it can't have a finite limit $\alpha>1$, because we can't have $\alpha^2=\alpha^2+\alpha-1$, then. This means $y_n\to\infty$ as $n\to\infty$. We have $$y_{n+1}-y_n=\frac{y^2_{n+1}-y^2_n}{y_{n+1}+y_n}=\frac{y_n-1}{y_{n+1}+y_n},$$ so $$2(y_{n+1}-y_n)-1=-\frac{2+y_{n+1}-y_n}{y_{n+1}+y_n}\tag1.$$ The numerator of the RHS is between $2$ and $5/2$, so the RHS converges to $0$ as $n\to\infty$, and $$\lim_{n\to\infty}(y_{n+1}-y_n)=\frac12.$$ By the Stolz–Cesàro theorem, $$\lim_{n\to\infty}\frac{2y_n+n}{n}=\lim_{n\to\infty}\frac{2(y_{n+1}-y_n)+1}{(n+1)-n}=2.$$ In the same way, using (1), \begin{align}\lim_{n\to\infty}\frac{2y_n-n}{\log n}&=\lim_{n\to\infty}\frac{2(y_{n+1}-y_n)-1}{\log(n+1)-\log n}\\ &=-\lim_{n\to\infty}\frac n{y_{n+1}+y_n}\cdot\frac{2+y_{n+1}-y_n}{n\,(\log(n+1)-\log n)}\\&=-1\cdot\frac{2+\frac12}1=-\frac52 \end{align} So the final result is $$\lim_{n\to\infty}\frac{4\,x_n-n}{n\log n}=-5.$$