I have defined a sequence $x_n$ as follows: $$x_{n+1}=x_n+\frac{1}{x_n}, \space\space\space x_0=1$$ After convincing myself that there is no nice closed-form formula for $x_n$, I decided to try and find an asymptotic formula for $x_n$ (unfortunately, I have very little experience with asymptotic formulae). I noticed that the recurrence is equivalent to $$\Delta x_{n}=\frac{1}{x_n}$$ and so a solution can be approximated by solving the corresponding differential equation for $y(t)$: $$y'=\frac{1}{y}$$ This differential equation (with initial value $y(0)=1$) yielded $$y=\sqrt{2t+1}$$ which led me to believe that $$x_n\approx \sqrt{2t+1}$$ When I plotted $x_n$ and $y(n)$ side by side, it did indeed appear that they were very close to each other. However, this isn't enough for me... I would like to prove that $y(n)$ is a good approximation for $x_n$, either by proving that $$\lim_{n\to\infty}(x_n-\sqrt{2n+1})=0$$ ...or, even better, by finding a zero-approaching function $f$ satisfying $$x_n=\sqrt{2n+1}+O(f(x))$$ This is where I got stuck. How do can I prove (or disprove?) the statement in the first equality, and find $f$ satisfying the second?

NOTE: There may be a closed-form that I wasn't able to find. In fact, the similar sequence $$y_{n+1}=\frac{y_n}{2}-\frac{1}{2y_n}$$ has closed form formula $$y_n=\frac{1}{\tan(2^n\arctan(y_0^{-1}))}$$ ...but even if you do find a closed form, I would still like to know how to prove the above statements, since the techniques would be useful to know for future problems.

  • $\begingroup$ I think $\int_n^{n+1} f(x) dx = \frac 1 {\int_0^n f(x)}$ is more accurate. But its probably nastier to solve. $\endgroup$ – mathreadler Nov 29 '17 at 0:15
  • 3
    $\begingroup$ See OEIS sequence A073833 and related sequences. $\endgroup$ – Robert Israel Nov 29 '17 at 0:21
  • 1
    $\begingroup$ Probably the first step, based on this guess, would be to write a recurrence for $a_n := x_n^2$: $a_{n+1} = a_n + 2 + \frac{1}{a_n}$. So, to start a bootstrapping argument, it would be easy to prove $a_n \ge 2n - 1$ for each $n$... And then $a_{n+1} \le a_n + 2 + \frac{1}{2n-1}$ so also $a_n \le 2n + \frac{1}{2} \log(n) - C$, etc. ... $\endgroup$ – Daniel Schepler Nov 29 '17 at 0:28
  • 1
    $\begingroup$ Here is a class of arguments that could work. You can try to prove inductively both an upper and a lower bound simultaneously, say $\sqrt{2n+a} \le x_n \le \sqrt{2n+b}$ for some $a, b$, because when bounding $x_{n+1}$ in terms of $x_n$ you need both a lower and an upper bound on $x_n$ to establish either an upper bound or a lower bound on $x_n + \frac{1}{x_n}$. $\endgroup$ – Qiaochu Yuan Nov 29 '17 at 0:55
  • 2
    $\begingroup$ Possible duplicate of Closed form for the sequence defined by $a_0=1$ and $a_{n+1} = a_n + a_n^{-1}$ $\endgroup$ – Aryabhata Nov 29 '17 at 3:10

You can show it's a quite nice bound by doing the following. First let $$f(x)=x+\frac{1}{x}$$ and then define $b_n=\sqrt{2n+1}$, $\epsilon_n=x_n-b_n$, and $\xi_n=f(b_n)-b_{n+1}$. First notice that $$f(x+\epsilon)-f(x)\le \epsilon$$ when $x,\epsilon \ge 0$ (we will later show that $\epsilon_n\ge 0$, for now assume this). We then have that $$\begin{aligned} \epsilon_{n+1} &= x_{n+1}-b_{n+1} \\ &= f(x_n)-f(b_n)+\xi_n \\ &= f(b_n+\epsilon_n)-f(b_n)+\xi_n \\ &\le \epsilon_n+\xi_n \end{aligned}$$ Combined with $\epsilon_0=0$, this tells us that $$0\le \epsilon_{n}\le \sum_{i=0}^{\infty}\xi_i\approx 0.56$$ The above being a convergent series (according to Wolfram by comparison). This of course gives $$\sqrt{2n+1}\le x_n\le \sqrt{2n+1}+0.56$$ for all $n$, making it a very good approximation.

To show that $\epsilon_n\ge 0$ we first see that $\epsilon_0=0$. Then assume $\epsilon_n\ge 0$, by the above we have $\epsilon_{n+1}=f(b_n+\epsilon_n)-f(b_n)+\xi_n$. It is easy to see that $f$ is increasing on $x\ge 1$, and that $b_n\ge 1$, thus since $\epsilon_n\ge 0$ we see that $f(b_n+\epsilon_n)-f(b_n)\ge 0$ finally yielding $\epsilon_{n+1}\ge \xi_n\ge 0$, where $\xi_n\ge 0$ is easy to verify since we have an explicit formula for $\xi_n$. This completes the induction.

The bound numerically looks like it can be improved and it might also be good to very find the series that Wolfram is comparing ours to. And this still doesn't resolve whether $\lim_{n\to \infty}(x_n-b_n)=0$.


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.