12
$\begingroup$

I would like to see some clue for the following problem:

Let $a_1=1$ and $a_n=1+\frac{1}{a_1}+\cdots+\frac{1}{a_{n-1}}$, $n>1$. Find $$ \lim_{n\to\infty}\left(a_n-\sqrt{2n}\right). $$

$\endgroup$
  • $\begingroup$ Notice that $a_n=a_{n-1}+1/a_{n-1}$ and read the "Babylonian method" in this Wiki article. $\endgroup$ – user378947 Jan 30 '17 at 2:29
  • $\begingroup$ @mathbeing according to this ${a_n} $ converges to 2? $\endgroup$ – DIEGO R. Jan 30 '17 at 2:47
  • $\begingroup$ No, $a_n$ must diverge to $+\infty$, and I suspect that $\lim_n(a_n-\sqrt{2n})=0$, but I wasn't able to prove it so far. Actually I am no longer sure that the link I posted can be of much help... In what context did you find this question? $\endgroup$ – user378947 Jan 30 '17 at 20:03
  • $\begingroup$ Let $f(x)=2 \cosh(\ln(x))$ and $f^{oh}(x)$ the h'th iterate, then $f^{on}(1)=a_{n+1}$ For large $x$ the $\cosh(x)$ and $\sinh(x)$ are neighboured and roughly $0.5 \exp(x)$ Perhaps one can do something for the proof from this ... $\endgroup$ – Gottfried Helms Feb 4 '17 at 0:17
  • 1
    $\begingroup$ No worries -- I mostly linked them for indexing and search purposes. $\endgroup$ – Clement C. Feb 7 '17 at 14:04
11
+50
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ trivial induction $\endgroup$ – user141614 Feb 1 '17 at 20:52
  • $\begingroup$ Only one thing is not clear to me. The inequality of the 7th line of this paragraph, which involves logarithm $\endgroup$ – DIEGO R. Feb 2 '17 at 2:09
  • $\begingroup$ $1+\frac13+\frac15+\ldots+\frac1{2n-3} < 1+\frac12+\frac13+\ldots+\frac1{n-1}<1+\log(n-1)$. $\endgroup$ – user141614 Feb 2 '17 at 6:42
4
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ Your approach is very interesting. It constitude a numerical method, I'll try to develop the ideas behind. $\endgroup$ – DIEGO R. Feb 4 '17 at 22:45
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I kinda like your answer, but I don't see how it proves the existence of the limit. Clearly we can expect some contradiction if we assume there is not such constant $S$, but you haven't found any, so, unless it is implicitly implied and I am missing something, your answer does not provide a proof of the existence of the limit. (?) $\endgroup$ – user378947 Feb 3 '17 at 11:36
  • $\begingroup$ I'm not sure I'm convinced by this argument. You have not found a contradiction, true, but I don't think you've shown that a contradiction doesn't exist. $\endgroup$ – Antonio Vargas Feb 3 '17 at 11:52
  • 1
    $\begingroup$ Thanks for you comments, I fully agree with you. The solution was not provided to give a proof that such limit exists, but only to confirm that, if such value $S $ exists, it must be $1$. Sorry for not having better clarified this when highlighting the assumption at the beginning of the answer. Probably, repeating the steps assuming non-existence of such $S $ could lead us to a contradiction. I will try it. $\endgroup$ – Anatoly Feb 3 '17 at 12:31
  • $\begingroup$ I edited my answer to better clarify this. $\endgroup$ – Anatoly Feb 3 '17 at 12:38
1
$\begingroup$

Quick and dirty proof.
Assume for a moment that the sequence $\,a_n\,$ is a continuous and differentiable function $\,a(n)\,$ of $\,n\,$ as is suggested in the picture below.
enter image description here

Then consider the following sequence. Fasten your seatbelts! $$ a_{n+1} = a_n + \frac{1}{a_n} \\ \frac{a_{n+1} - a_n}{1} = \frac{1}{a_n} \\ \frac{a(n+dn) - a(n)}{dn} = \frac{1}{a(n)} \\ a'(n)\,a(n) = 1 \\ \frac{da^2(n)}{dn} = 2 \\ a^2(n) = 2n+C $$ [Scaling argument deleted. I see no way to get it consistent, let it be rigorous. See edits of this post] Now we would like to have $\,C=0$ ; and fortunately there is a boundary condition, for $\,n=2$ , that fits the bill : $\,C = a_2^2 - 2\cdot 2 = 0$ . So: $\;a_n = \sqrt{2n}$ .
The larger $n$ , the better all of the approximations. A much neater way to express the end-result is: $$ \large \boxed{\lim_{n\to\infty} \frac{a_n}{\sqrt{2n}} = 1} $$ BONUS. Lemma: $$ a_{n+1} = a_n + \frac{1}{a_n} \quad \Longrightarrow \quad a_{n-1}^2 - a_na_{n-1} + 1 = 0 \quad \Longrightarrow \quad a_{n-1} = \frac{a_n}{2} + \sqrt{\left(\frac{a_n}{2}\right)^2-1} $$ Now compute (the discretization of) the second derivative, assuming again that $\,a_n\,$ is large: $$ a''(n) = a_{n+1} - 2a_n + a_{n-1} = a_n + \frac{1}{a_n} - 2a_n + \frac{a_n}{2} + \frac{a_n}{2}\sqrt{1-\frac{1}{(a_n/2)^2}} \approx \\ \frac{1}{a_n} - \frac{a_n}{2} + \frac{a_n}{2} \left[1-\frac{1}{2}\frac{1}{(a_n/2)^2} - \frac{1}{8}\left(\frac{1}{(a_n/2)^2}\right)^2\right] = -\frac{1}{a_n^3} $$ Which means that the discrete function $\,a_n\,$ for large $\,n\,$ is actually very smooth , when seen as a continuous and differentiable $\,a(n)$ . This is an even stronger motivation for the above treatment.
It is noticed that the "true" derivatives exhibit the same structure as the discretizations: $$ \left(\sqrt{2x}\right)'' = \left(\frac{1}{\sqrt{2x}}\right)' = -\frac{1}{\left(\sqrt{2x}\right)^3} $$ There are no coincidences in mathematics.

$\endgroup$

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.