Asymptotic behavior of $x_{n+1}=x_n+\frac{1}{x_n}, \space\space\space x_0=1$

Question

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.

Answer 1

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

Answer 2

I will borrow some notation from Will Fisher's answer. We can estimate your limit by looking at it this way: we have $$ x_n - x_0 = \sum_{i=0}^{n-1} \Delta x_i = \sum_{i=0}^{n-1} \frac 1{x_i}. $$ We also have $$ b_n - b_0 = \sum_{i=0}^{n-1} \Delta b_i = \sum_{i=0}^{n-1} (\sqrt{2i+3} - \sqrt{2i+1}) = \sum_{i=0}^{n-1} \frac 2{\sqrt{2i+3} + \sqrt{2i+1}}. $$ Since we have no closed form for $x_n$ but our approximation $b_n$ is very good, I will now look at the closed forms of $\Delta b_n$ and $\frac 1{b_n}$.

We have $$ \frac 1{b_n} - \Delta b_n = \frac 1{\sqrt{2n+1}} - \frac 2{\sqrt{2n+3}+\sqrt{2n+1}} \\ = \frac{\sqrt{2n+3} - \sqrt{2n+1}}{\sqrt{2n+1}(\sqrt{2n+3} + \sqrt{2n+1})} \\ = \frac{(2n+3) - (2n+1)}{\sqrt{2n+1}(\sqrt{2n+3} + \sqrt{2n+1})^2} \\ = \frac 2{\sqrt{2n+1}(\sqrt{2n+3} + \sqrt{2n+1})^2} $$ By replacing $3$'s by $1$'s and vice-versa, we obtain the following bounds for all $n \ge 0$: $$ \frac 1{2(2n+3)^{3/2}} \le \frac 1{b_n} - \Delta b_n \le \frac 1{2(2n+1)^{3/2}}. $$ This suggests that if we add up the $\frac 1{b_i}$'s instead of $\Delta b_i$ in the expression $b_n - b_0 = \sum_{i=0}^{n-1} \Delta b_i$, we would have an error term which would look roughly like a sum of terms of the form $i^{-3/2}$, thus giving an error roughly like $n^{-1/2}$, which goes to $0$ with $n$. Therefore, we can use the $\frac 1{b_i}$ instead of $\Delta b_i$ to compare with $\frac 1{x_i}$ (we will do this more formally in a second).

Writing $\varepsilon_n \overset{def}= x_n - b_n$, we also have as in the other answer $$ f(b+\varepsilon) - f(b) = \left( (b+\varepsilon) + \frac 1{b+\varepsilon} \right) - \left( b + \frac 1b \right) \\ = \varepsilon - \frac {\varepsilon}{b(b+\varepsilon)} $$ Therefore $$ x_{n+1} - b_{n+1} = \left( x_n + \frac 1{x_n} \right) - (\Delta b_n + b_n) \\ = \left( x_n + \frac 1{x_n} \right) - \left( b_n + \frac 1{b_n} \right) + \left( \frac 1{b_n} - \Delta b_n \right) \\ = \left( f(x_n) - f(b_n) \right) + \left( \frac 1{b_n} - \Delta b_n \right) \\ = (x_n - b_n)\left( 1 - \frac 1{x_nb_n} \right) + \left( \frac 1{b_n} - \Delta b_n \right). $$ so that letting $c_n = 1 - \frac 1{x_nb_n}$ and $d_n = \frac 1{b_n} - \Delta b_n$, we have $x_{n+1} - b_{n+1} = (x_n - b_n) c_n + d_n$, hence by induction on $k$, we deduce $$ x_{n+k} - b_{n+k} = (x_n - b_n) \left( \Pi_{i=0}^{k-1} c_{n+i} \right) + \sum_{i=0}^{k-1} \left( \Pi_{j=i+1}^{k-1} c_{n+j} \right) d_{n+i}. $$ We now show that as $n+k$ go to infinity, both terms go to zero.

The second term goes to $0$ with $n$ since $$ \sum_{i=0}^{k-1} \left( \Pi_{j=i+1}^{k-1} c_{n+j} \right) d_{n+i} \le \sum_{i=0}^{k-1} d_{n+i} \\ \le \sum_{i=0}^{k-1} \frac 1{2(2(n+i)+1)^{3/2}} \\ \le \int_{n-1}^{\infty} \frac 1{2(2x+1)^{3/2}} dx \\ = \frac 12 \left( \left. \frac {-1}{\sqrt{2x+1}} \right|_{n-1}^{\infty} \right) \\ = \frac 12 \left( \frac 1{\sqrt{2n-1}} \right) \to 0. $$ Note that this bound is uniform over $k$, i.e. only depends on $n$.

For the first term, note that $|x_n - b_n| \le C$ is uniformly bounded for all $n$ (see Will Fisher's answer for why $C \approx 0.56$), so it suffices to show that $\Pi_{i=0}^{k-1} c_{n+i}$ goes to $0$ with $k$ for $n$ fixed. In this way, we can fix $n$ so that the second term is arbitrarily small, and then take $k$ large enough to make the first term arbitrarily small; this implies the sum of both terms can be arbitrarily small, given that $n+k$ is large enough.

Since $x_n - b_n \ge 0$, we have $x_n \ge b_n$, hence $\frac 1{x_n} \le \frac 1{b_n}$, so that $c_n \le 1 - \frac 1{x_n^2} < 1$. Using $\log(1-x) \le -x$ for $x \ge 0$, it follows that $$ \log \left( \Pi_{i=0}^{k-1} c_{n+i} \right) = \sum_{i=0}^{k-1} \log c_{n+i} \le \sum_{i=0}^{k-1} \log \left( 1 - \frac 1{x_{n+i}^2} \right) \le - \sum_{i=0}^{k-1} \frac 1{x_{n+i}^2} \underset{k \to \infty}{\longrightarrow} -\infty $$ where the limit over $k$ follows from the following argument: since $x_n \le b_n + C \le 2b_n$ where $C \approx 0.56 \le 1 = b_0 \le b_n$ (see Will Fisher's answer for why $C \approx 0.56$), we have $\frac 1{x_n} \ge \frac 1{2b_n}$, thus $$ \sum_{i=0}^{k-1} \frac 1{x_{n+i}^2} = \sum_{m=n}^{n+k-1} \frac 1{x_m^2} \ge \frac 14 \sum_{m=n}^{n+k-1} \frac 1{2m+1} \underset{k \to \infty}{\longrightarrow} \infty. $$ Hope that helps,