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

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

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.$$