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

• I try to find out the upper bound of $x_n$ and then apply the squeeze theorem, but I failed. – SundayCat Oct 23 '13 at 18:38
• The sequence $\{x_n\}$ itself is unbounded, so you need to be studying the sequence given by $y_n = \dfrac{x_n}n$. – Ted Shifrin Oct 23 '13 at 18:40
• Yes, but it is always have a number bigger than it. Like ${x_n} \le 2 + \frac{1}{2}(n-2)$. – SundayCat Oct 23 '13 at 18:44
• @Ted, sundaycat: Oops, my bad. I confused it with the sequence with recursive rule $$x_{n+1}=1+\frac1{x_n}.$$ – Cameron Buie Oct 23 '13 at 18:45

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.$$
• At least numerically, it looks like $\frac{x_n}{\sqrt{2n}}\to1$. Still, I wouldn't mind the proof using Landscape's idea. – Martin Argerami Oct 23 '13 at 19:04
• @MartinArgerami: Thanks for your comment. I completely changed my argument after reading other answers. – 23rd Oct 26 '13 at 20:26
• Nice.${\ \ \ \ \ \ \ \ \ }$ – Martin Argerami Oct 26 '13 at 22:20
• @GotLost: At the last part of your proof, what is the purpose to state $\theta_n<\delta_n\le \delta$? – SundayCat Oct 27 '13 at 3:28
• @sundaycat: To take limit in $(5)$, I need assumption (ii) to apply $(1)$, where a reasonable requirement is $\theta_n$ cannot be too large. Without any assumption, I only know $0<\theta_n<\delta_n$. To control the upper bound of $\theta_n$, I need assumption $(1)$ to obtain $\delta_n\le\delta$ when $n$ is large. For example, consider $f(x)=x^p$($p\ge 1$) and an arbitrary $\theta:(0,\infty)\to (0,\infty)$. Then you need some condition on $\theta$ to get $\lim_{x\to\infty}\frac{f'(x+\theta(x))}{f'(x)}=1$. – 23rd Oct 27 '13 at 5:30

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

• I don't know how you obtain $x_k\geq\sqrt{k}$, but you can say right away from your argument that $y_k\geq 2k-1$. – Martin Argerami Oct 23 '13 at 22:04
• @kedrigern, how you obtain $\sum_{k=1}^n \frac{1}{k} \le ln(n) + 1$ – SundayCat Oct 23 '13 at 22:50
• @Martin Argerami Yes, I overcomplicated it there a bit :-) Will use directly that upper bound on $\frac{1}{y_k}$ – kedrigern Oct 24 '13 at 4:33
• @kedrigern how you obtain $x_k \ge \sqrt(k)$, could you show me the process? thanks! – SundayCat Oct 24 '13 at 6:24
• If follows from (1) as it proves that $y_n\ge 2(n-1)+1=2n-1\ge n$ for every $n\ge 1$. – kedrigern Oct 24 '13 at 12:38

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

• N. S.: $x_{n+1}> x_n$ is not obvious , it is not said that $x_n>0$ , though it would follow by induction. – Souvik Dey Oct 24 '13 at 4:54
• @SouvikDey That is a trivial induction, looks obvious to me :) – N. S. Oct 24 '13 at 4:58

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

• From my answer you can see that letting $y_n=x_n^2$ is a good choice for your question (1) but not as good a choice for your question (2). The reason for letting $y_n=x_n^2$ in question (1) can be understood in this way: the associated function $f$ is question (1) is $c x^2$ for some $c>0$. For the same reason, in question (2), a good choice is letting $y_n=x_n^{3/2}$. – 23rd Oct 25 '13 at 21:19