Is the following limit finite ....?

Solution 1:

The recurrence can be re-written as $a_{n+1}=a_n+\dfrac1{a_n}$. Let $x_n=a_n^2$; then we have $x_1=1$ and $$ x_{n+1} = a_{n+1}^2 = \left(a_n+\dfrac1{a_n}\right)^2 = a_n^2+2+\dfrac1{a_n^2} = x_n+2+\dfrac1{x_n}. $$ From this we can conclude $x_{n+1}>x_n+2$, so $$ x_n \ge 2n-1; $$ then $x_{n+1}=x_n+2+\dfrac1{x_n}<x_n+2+\dfrac1{2n-1}$, so $$ x_n < 2n-1 + \left(1+\dfrac13+\dfrac15+\ldots+\dfrac1{2n-3}\right) < 2n+\log n. $$ Finally, $$ \big|a_n-\sqrt{2n}\big| = \dfrac{|a_n^2-2n|}{a_n+\sqrt{2n}} < \dfrac{|x_n-2n|}{\sqrt{2n}} < \dfrac{\log n}{\sqrt{2n}}. $$ Therefore, $\big|a_n-\sqrt{2n}\big|\to0$.

Solution 2:

Suppose that the sequence is a Newton–Raphson method for calculating numerically the zeroes of a function. What would that function look like then? $$ x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}} \quad \Longleftrightarrow \quad a_{n+1}=a_n+\frac{1}{a_n} $$ Identify $\,a_n = x_n\,$ in the first place, and solve for the function: $$ \frac{f'(x)}{f(x)} = -x \quad \Longleftrightarrow \quad f(x) = C\,e^{-x^2/2} $$ Interpretation: the sequence is a Newton–Raphson iterative method : for finding the zeroes of a Gaussian. However, it is clear from the start that the numerical calculations are not going to find those zeroes, for the simple reason that there aren't any.

But suppose that we modify the problem a bit, as follows: find the zeroes of $\;f(x) = e^{-x^2/2} - e^{-N}\;$ with $N$ some large positive integer, then we have instead the sequence: $$ x_{n+1}=x_{n}+\frac{1}{x_n}\left[1-\frac{e^{-N}}{e^{-x_n^2/2}}\right] $$ And now the iterations stop when: $$ x_{n+1} = x_n \quad \Longleftrightarrow \quad e^{-x_n^2/2} = e^{-N} \quad \Longleftrightarrow \quad x_n = \sqrt{2N} $$ Here is a little (Delphi Pascal) program that does the job:

program Diego;

procedure main(N : integer);
var
  x,y : double;
  t : integer;
begin
  Writeln('sqrt(2N) =',sqrt(2*N));
  x := 1; y := 0; t := 0;
  Writeln(t:4,' : x =',x);
  while not (y=x) do
  begin
    y := x; t := t + 1;
    x := x + 1/x*(1-exp(-N)/exp(-sqr(x)/2));
    Writeln(t:4,' : x =',x);
  end;
end;

begin
  main(8);
end.

Output:

sqrt(2N) = 4.00000000000000E+0000
   0 : x = 1.00000000000000E+0000
   1 : x = 1.99944691562985E+0000
   2 : x = 2.49834687643857E+0000
   3 : x = 2.89556809260418E+0000
   4 : x = 3.23325795454623E+0000
   5 : x = 3.52322153181656E+0000
   6 : x = 3.75982762597611E+0000
   7 : x = 3.92105171808397E+0000
   8 : x = 3.98953172402065E+0000
   9 : x = 3.99979758749457E+0000
  10 : x = 3.99999992320208E+0000
  11 : x = 3.99999999999999E+0000
  12 : x = 4.00000000000000E+0000
  13 : x = 4.00000000000000E+0000

So far so good. Now, what will happen if the value of $N$ is increased indefinitely? Then the sequence will become longer and longer; in the end it will never stop. Moreover, the following will be true: $$ \lim_{N\to\infty} e^{-N} = 0 \quad \Longrightarrow \quad x_{n+1}=x_{n}+\frac{1}{x_n} $$ It is clearly seen, however, that the number of iterations in the finite case ($n = 13$) does not equal $N = 8$ . So I doubt if the conjectured limit is true. Still apart from the fact that subtraction of two (infinitely) large numbers is highly unstable numerically (i.e. "bad" limit).

Update. Further numerical experiments reveal that indeed our iterands $\,x_n\,$ as well as the OP's original $\,a_n\,$ are close to $\,\sqrt{2n}\,$ and the larger $\,n\,$ the better, it seems. Here is an example, with $\,\sqrt{2\times 8192} = 128$ :

8188 : x = 1.27991318734407E+0002 , a = 1.27993080007178E+0002
8189 : x = 1.27996559906482E+0002 , a = 1.28000892929564E+0002
8190 : x = 1.27999342587009E+0002 , a = 1.28008705375065E+0002
8191 : x = 1.27999973101217E+0002 , a = 1.28016517343767E+0002
8192 : x = 1.27999999953749E+0002 , a = 1.28024328835758E+0002 <==
8193 : x = 1.27999999999999E+0002 , a = 1.28032139851126E+0002
8194 : x = 1.28000000000000E+0002 , a = 1.28039950389958E+0002
8195 : x = 1.28000000000000E+0002 , a = 1.28047760452340E+0002

So it may be conjectured that for all $\,n$ : $$ x_n < \sqrt{2n} < a_n $$ With: $$ x_{n+1} = x_n + \frac{1}{x_n}\left[1 - \frac{e^{-n}}{e^{-x_n^2/2}}\right] \quad ; \quad a_{n+1} = a_n + \frac{1}{a_n} $$ I have not (yet) been able to prove that this conjecture is true.

Solution 3:

As other answers indicate, this sequence obeys to the following recurrence relation :

$$a_1=1\quad\mathrm{and}\quad\forall n\in\mathbb{N},\,a_{n+1}=a_n+\frac{1}{a_n}$$

This proves that the sequence is increasing. Supposing its convergence to some finite limit $L>0$ would lead to $L=L+\dfrac{1}{L}$, a contradiction. Hence the sequence diverges towards $+\infty$.

Now, for all $n\in\mathbb{N}$, we have :

$$a_{n+1}^2-a_n^2=\left(a_n+\frac{1}{a_n}\right)^2-a_n^2=2+\frac{1}{a_n^2}\longrightarrow 2$$

By Cesaro's lemma :

$$\frac{1}{n}\left(a_n^2-a_0^2\right)=\frac{1}{n}\sum_{k=0}^{n-1}\left(a_{k+1}^2-a_k^2\right)\longrightarrow 2$$

Thus $$a_n\sim\sqrt{2n}$$ Now, we will use ...

Lemma Given a sequence $(u_n)_{n\ge1}$ of positive real numbers such that $u_n\sim\dfrac{1}{n}$, we have : $$\sum_{k=1}^nu_k\sim\ln(n)$$

(See below for a proof.)

Since $a_{n+1}^2-a_n^2-2\sim\dfrac{1}{2n}$ and by the previous lemma :

$$a_n^2-2n\sim\frac{\ln(n)}{2}$$

which can be written :

$$a_n=\sqrt{2n}\,\sqrt{1+\frac{\ln(n)}{4n}+o\left(\frac{\ln(n)}{n}\right)}$$

Using now the Taylor expansion $\sqrt{1+t}=1+\frac{t}{2}+o(t)$ as $t\to0$, we get finally :

$$\boxed{a_n=\sqrt{2n}\left(1+\frac{\ln(n)}{8n}+o\left(\frac{\ln(n)}{n}\right)\right)}$$

In particular, we see that $\lim_{n\to\infty}\left(a_n-\sqrt{2n}\right)=0$, but the result above is much more accurate.

---

Proof of the above lemma

Given $\epsilon>0$, there exists $N\in\mathbb{N}^\star$ such that :

$$k>N\implies\left|u_k-\frac{1}{k}\right|\le\epsilon$$

As soon as $n>N$, we have :

$$\left|\sum_{k=1}^nu_k-\sum_{k=1}^n\frac{1}{k}\right|\le\underbrace{\left|\sum_{k=1}^N\left(u_k-\frac{1}{k}\right)\right|}_{=A}+\sum_{k=N+1}^n\left|u_k-\frac{1}{k}\right|\le A+\epsilon\sum_{k=N+1}^n\frac{1}{k}$$

And a fortiori :

$$\left|\sum_{k=1}^nu_k-\sum_{k=1}^n\frac{1}{k}\right|\le A+\epsilon\sum_{k=1}^n\frac{1}{k}$$

Since $\lim_{n\to\infty}\sum_{k=1}^n\frac{1}{k}=+\infty$, there exists $N'\in\mathbb{N}^\star$ such that :

$$n>N'\implies\sum_{k=1}^n\frac{1}{k}>\frac{A}{\epsilon}$$

Finally :

$$n>\max\{N,N'\}\implies\left|\sum_{k=1}^nu_k-\sum_{k=1}^n\frac{1}{k}\right|\le2\epsilon\sum_{k=1}^n\frac{1}{k}$$

This proves that :

$$\sum_{k=1}^nu_k\sim\sum_{k=1}^n\frac{1}{k}$$

But we know that $\sum_{k=1}^n\frac{1}{k}\sim\ln(n)$ as $n\to\infty$, hence the conclusion (by transitivity of $\sim$).

Solution 4:

Alternative solution: let us assume that there exists a real number $S $ such that $$ \lim_{n\to\infty} \left(a_n-S\sqrt{2n} \right)=0$$

If this constant (and necessarily positive) value exists, we should be able to determine it. On the other hand, if such constant value does not exist (for example, if $S $ is not a constant but a function of $n $), we could expect some contradiction.

Under the assumption that a real $S $ exists, we have

$$ \lim_{n\to\infty} \frac {1}{a_n}= \lim_{n\to\infty} \frac {1}{S \sqrt {2n}}$$

Also, because by definition the recurrence of the OP can be written as $a_{n+1}=a_n+1/a_n \,\, \,\,$, we have

$$ \lim_{n\to\infty} \frac {1 }{a_n}=\lim_{n\to\infty} \left( a_{n+1}-a_n \right) \\ =\lim_{n\to\infty} \left( S \sqrt {2(n+1)} -S \sqrt {2n}\right) $$

Combining the two equations above we get

$$\lim_{n\to\infty} \frac {1}{S \sqrt {2n}}= \lim_{n\to\infty} S \left( \sqrt {2(n+1)} - \sqrt {2n} \right)$$

Solving for $S $ and taking into account that $S$ cannot be negative, we obtain

$$S= \lim_{n\to\infty} \frac { \sqrt {n+1} + \sqrt {n}}{2 \sqrt {n} } = 1$$

Thus, assuming existence of real $S $, we obtain $S=1\,\,$ with no contradiction. We conclude that

$$ \lim_{n\to\infty} \left(a_n-\sqrt{2n} \right)=0$$

It should be pointed out that this solution does not give a proof that such limit exists, but only shows that, assuming its existence, it must be $1$.