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.

  • $\begingroup$ I try to find out the upper bound of $x_n$ and then apply the squeeze theorem, but I failed. $\endgroup$ – SundayCat Oct 23 '13 at 18:38
  • 1
    $\begingroup$ The sequence $\{x_n\}$ itself is unbounded, so you need to be studying the sequence given by $y_n = \dfrac{x_n}n$. $\endgroup$ – Ted Shifrin Oct 23 '13 at 18:40
  • $\begingroup$ Yes, but it is always have a number bigger than it. Like ${x_n} \le 2 + \frac{1}{2}(n-2)$. $\endgroup$ – SundayCat Oct 23 '13 at 18:44
  • $\begingroup$ @Ted, sundaycat: Oops, my bad. I confused it with the sequence with recursive rule $$x_{n+1}=1+\frac1{x_n}.$$ $\endgroup$ – 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.$$
  • $\begingroup$ At least numerically, it looks like $\frac{x_n}{\sqrt{2n}}\to1$. Still, I wouldn't mind the proof using Landscape's idea. $\endgroup$ – Martin Argerami Oct 23 '13 at 19:04
  • $\begingroup$ @MartinArgerami: Thanks for your comment. I completely changed my argument after reading other answers. $\endgroup$ – 23rd Oct 26 '13 at 20:26
  • $\begingroup$ Nice.${\ \ \ \ \ \ \ \ \ }$ $\endgroup$ – Martin Argerami Oct 26 '13 at 22:20
  • $\begingroup$ @GotLost: At the last part of your proof, what is the purpose to state $\theta_n<\delta_n\le \delta$? $\endgroup$ – SundayCat Oct 27 '13 at 3:28
  • 1
    $\begingroup$ @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$. $\endgroup$ – 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$$


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

  • $\begingroup$ 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$. $\endgroup$ – Martin Argerami Oct 23 '13 at 22:04
  • $\begingroup$ @kedrigern, how you obtain $\sum_{k=1}^n \frac{1}{k} \le ln(n) + 1$ $\endgroup$ – SundayCat Oct 23 '13 at 22:50
  • $\begingroup$ @Martin Argerami Yes, I overcomplicated it there a bit :-) Will use directly that upper bound on $\frac{1}{y_k}$ $\endgroup$ – kedrigern Oct 24 '13 at 4:33
  • $\begingroup$ @kedrigern how you obtain $x_k \ge \sqrt(k)$, could you show me the process? thanks! $\endgroup$ – SundayCat Oct 24 '13 at 6:24
  • $\begingroup$ If follows from (1) as it proves that $y_n\ge 2(n-1)+1=2n-1\ge n$ for every $n\ge 1$. $\endgroup$ – 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$$

  • 2
    $\begingroup$ N. S.: $x_{n+1}> x_n$ is not obvious , it is not said that $x_n>0$ , though it would follow by induction. $\endgroup$ – Souvik Dey Oct 24 '13 at 4:54
  • 2
    $\begingroup$ @SouvikDey That is a trivial induction, looks obvious to me :) $\endgroup$ – 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 $$

  • 1
    $\begingroup$ 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}$. $\endgroup$ – 23rd Oct 25 '13 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.