Limit of $x_n/n$ for sequences of the form $x_{n+1}=x_n+1/x_n^p$

Question

1. Given $x_1 = 1, x_{n+1} = x_n + \frac{1}{x_n} (n\ge1)$, Prove whether the limit as follow exist or not. If so, find it $$\lim_{n\to\infty}\frac{x_n}{n}$$

2. Given $x_1 = 1, x_{n+1} = x_n + \frac{1}{\sqrt{x_n}} (n\ge1)$, Prove whether the limit as follow exist or not. If so, find it $$\lim_{n\to\infty}\frac{x_n}{n}$$

---

In both cases, $x_n$ is increasing, so I tried to get an upper bound on $x_n$ (possibly depending on $n$) to apply a squeeze theorem; but failed.

Answer 1

Combining the ideas in the answers given by kedrigern and N.S., we can obtain a little more general conclusion as below.

Proposition: Let $f:(0,+\infty)\to (0,+\infty)$ be continuously differentiable with $f'>0$. In addition, assume that there exists $\delta>0$, such that (i) $f'(x)\ge\frac{1}{\delta}$ when $x$ is large, and (ii) for any $\theta:(0,+\infty)\to[0,\delta]$, $$\lim_{x\to\infty}\frac{f'(x+\theta(x))}{f'(x)}=1.\tag{1}$$ Then for any sequence $(x_n)$ satisfying $$x_1>0\quad\text{and}\quad x_{n+1}=x_n+\frac{1}{f'(x_n)},\ \forall n\ge 1, \tag{2}$$ we have: $$\lim_{n\to\infty}\frac{f(x_n)}{n}=1.\tag{3}$$

Proof: Form $(2)$ and $f'>0$ we know that $(x_n)$ is positive and increasing; in particular, $L:=\lim\limits_{n\to\infty}x_n$ eixsts(either finite or $+\infty$). If $L<+\infty$, then by $(2)$ and continuity, $$L=\lim_{n\to\infty}x_{n+1}=\lim_{n\to\infty}x_n+\frac{1}{\lim\limits_{n\to\infty}f'(x_n)}=L+\frac{1}{f'(L)}>L,$$ a contradiction. Therefore, $\lim\limits_{n\to\infty}x_n=+\infty$.

Since $f'>0$, $f$ is increasing. Then from $(x_n)$ being increasing we know that $\big(f(x_n)\big)$ is also increasing, so by Stolz–Cesàro theorem, $$\lim_{n\to\infty}\frac{f(x_n)}{n}=\lim_{n\to\infty}\big(f(x_n)-f(x_{n-1})\big).\tag{4}$$ Denote $\delta_n=\frac{1}{f'(x_n)}$. By $(2)$ and mean value theorem, there exists $\theta_n\in (0,\delta_n)$, such that $$f(x_{n+1})-f(x_n)=f(x_n+\delta_n)-f(x_n)=f'(x_n+\theta_n)\delta_n.\tag{5}$$ Since $\lim\limits_{n\to\infty}x_n=+\infty$, by assumption (i), when $n$ is large, $\theta_n<\delta_n\le \delta$. Letting $n\to\infty$ in $(5)$, by assumption (ii), the limit exists and is $1$, so $(3)$ follows from $(4)$, which completes the proof.

---

Exampes: It is easy to check that for every $c>0$ and every $p\ge 1$, $f(x)=cx^p$ satisfies all the assumptions in the proposition. In particular, for your original question, we have:

1. For $f(x)=\frac{1}{2}x^2$, $f'(x)=x$ and $x_{n+1}=x_n+\frac{1}{x_n}$, so if $x_1>0$, $$\lim_{n\to\infty}\frac{f(x_n)}{n}=1\Longleftrightarrow \lim_{n\to\infty}\frac{x_n}{\sqrt{n}}=\sqrt{2}\Longrightarrow \lim_{n\to\infty}\frac{x_n}{n}=0.$$
2. For $f(x)=\frac{2}{3}x^{\frac{3}{2}}$, $f'(x)=\sqrt{x}$ and $x_{n+1}=x_n+\frac{1}{\sqrt{x_n}}$, so if $x_1>0$, $$\lim_{n\to\infty}\frac{f(x_n)}{n}=1\Longleftrightarrow \lim_{n\to\infty}\frac{x_n}{n^{\frac{2}{3}}}=(\frac{3}{2})^{\frac{2}{3}}\Longrightarrow\lim_{n\to\infty}\frac{x_n}{n}=0.$$

Answer 2

Proof that $\lim\limits_{n\to\infty}\frac{x_n}{\sqrt{2n}}=1$.

Let $y_n=x_n^2$. Then $$y_{n+1}=x_{n+1}^2 = \left(x_n + \frac{1}{x_n}\right)^2 = x_n^2+2+\frac{1}{x_n^2} = y_n + 2 + \frac{1}{y_n}$$ Then $$y_{n+1} = y_n + 2 + \frac{1}{y_n} = y_{n-1} + 2 + \frac{1}{y_{n-1}} + 2 + \frac{1}{y_{n}}=\cdots=y_1+2n+\sum\limits_{k=1}^{n}\frac{1}{y_k}\tag{1}$$ Then $y_{n+1}\ge 2n+1$ and therefore $\frac{1}{y_n}\le\frac{1}{2n-1}\le\frac{1}{n}$ for all $n\ge 1$. Together we get $$2n+1\le y_{n+1}\le 2n+1+\sum\limits_{k=1}^{n}\frac{1}{k}\le 2n+1+\ln(n)+1$$ Then $$\lim\limits_{n\to\infty} \frac{y_n}{2n}=1$$ as since $x_n>0$ $$\lim\limits_{n\to\infty} \frac{x_n}{\sqrt{2n}}=1$$

---

EDIT

$$\sum\limits_{k=1}^{n}\frac{1}{k}=1+\sum\limits_{k=2}^{n}\frac{1}{k}\le 1+ \int\limits_{1}^{n}\frac{1}{x}dx=1+\ln(n)$$

Answer 3

As $x_{n+1}> x_n$ it follows that $x_n$ is either convergent or $\lim_n x_n =\infty$.

The first case is impossible, as $\lim_n x_n =l \in (1, \infty) \Rightarrow l+\frac{1}{l}=l$.

Thus, $\lim_n x_n=\infty$.

Now by the Stolz–Cesàro theorem

$$\lim_n \frac{x_n}{n}=\lim_n(x_{n+1}-x_n)= \lim_n \frac{1}{x_n}=0$$

Answer 4

By the inspiration from @kedrigern, I solved the second one. Hope somebody can find a simple way to solve it:

Let $y_n = x_n^2$,then:

\begin{align*} \ y_{n+1} &= x_{n+1}^2 = x_n + \frac{1}{\sqrt{x_n}}= x_n^2 + 2\sqrt{x_n} + \frac{1}{x_n} \\&= y_n + 2\sqrt{x_n} + \frac{1}{x_n} \\&=y_{n-1} + 2(\sqrt{x_n} + \sqrt{x_{n-1}}) +(\frac{1}{x_n}+\frac{1}{x_{n-1}}) \\&\vdots \\&= y_1 + 2\sum_{i=1}^n\sqrt{x_i} + \sum_{i=1}^n\frac{1}{x_i} \end{align*}

(1)Since $1\le x_n \le n$. then:
\begin{align*} \ y_{n+1} &= 1 + 2\sum_{i=1}^n\sqrt{x_i} + \sum_{i=1}^n\frac{1}{x_i} \\&\ge 1+2\sum_{i=1}^n1+\sum_{i=1}^n\frac{1}{x_i} \\&=1+2n+\sum_{i=1}^n\frac{1}{x_i} \\&\ge n \end{align*} Hence： $$ \frac{1}{x_{n+1}} \le \frac{1}{\sqrt{n}}~~That~~is: \frac{1}{x_{n}} \le \frac{1}{\sqrt{n-1}}(n\ge 2)$$ (2)Since $1\le x_n \le n$,then： $$\sqrt{x_n} \le \sqrt{n}$$

(3)The upper bound of $y_{n+1}$： \begin{align*} \ 0\le y_{n+1}&= 1+2\sum_{i=1}^n\sqrt{x_i}+\sum_{i=1}^n\frac{1}{x_i} \\&\le 1+2\sum_{i=1}^n\sqrt{i}+\sum_{i=1}^n\frac{1}{x_i}~~~~~~~~~~~~~~~~~~~~~\ldots\ldots from~(2) \\&= 1+2\sum_{i=1}^n\sqrt{i}+(1+\sum_{i=2}^n\frac{1}{x_i}) \\&\le 1+2\sum_{i=1}^n\sqrt{i}+(1+\sum_{i=2}^n\frac{1}{\sqrt{i-1}})~~~\ldots\ldots from~(1) \\&= 1+2(\sqrt{n}+\sum_{i=1}^{n-1}\sqrt{i})+(2+\sum_{i=3}^n\frac{1}{\sqrt{i-1}}) \\&\le 1+2(\sqrt{n} + \int_1^n\sqrt{x}dx)+(2+\int_2^n\frac{1}{\sqrt{x-1}}dx) \\&=2\sqrt{n}+2\sqrt{n-1}+\frac{4n^\frac{3}{2}-1}{3} \end{align*} Simplify,we have： $$0\le y_{n+1} \le 2\sqrt{n}+2\sqrt{n-1}+\frac{4n^\frac{3}{2}-1}{3} $$ That is：$$0 \le \frac{x_{n+1}}{n} \le \frac{\sqrt{2\sqrt{n}+2\sqrt{n-1}+\frac{4n^\frac{3}{2}-1}{3}}}{n}$$ By the squeeze theorem： $$ \lim_{n \rightarrow \infty}\frac{x_n}{n}=0 $$