$a_{n+1} = a_n/2 + 1/a_n$ is Cauchy but has no limit in $\mathbb{Q}$

Question

I want to show that the sequence recursively defined by

$a_{n+1} = \frac{a_n}{2} + \frac{1}{a_n}, \:\: a_1=1$

is a Cauchy sequence that does not converge in $\mathbb{Q}$.

My idea was to show that this is a bounded sequence with bounds $1\leq a_n \leq 2$ and with a monotone tail, so that the monotonicity principle implies convergences in $\mathbb{R}$. But then how do I show that the limit is not in $\mathbb{Q}$?

Is there a way to use the definition of a Cauchy sequence directly?

Any help would be much appreciated!

Answer 1

The comments have already basically given the answer but it is always good practice to write a full response to a question. As you mention, one way to go about proving this is to show that the sequence is bounded and then eventually monotonic. I won't do that here, but if we utilize a different sequence then monotinicity is easy to prove.

Following your idea, note that $1\leq a_1\leq 2$. Then $1\leq a_n\leq 2$ implies

$$a_{n+1} = \frac{a_n}{2}+ \frac{1}{a_n}\leq \frac{2}{2}+ \frac{1}{1}=2$$

$$a_{n+1} = \frac{a_n}{2}+ \frac{1}{a_n}\geq \frac{1}{2}+ \frac{1}{2}=1$$

as desired. We conclude by induction that $1\leq a_n\leq 2$. Now, to prove that the sequence converges we will define a new sequence and show that it goes to $0$. Define

$$b_n=|a_n-\sqrt{2}|$$

Where does the $\sqrt{2}$ come from? Well, its basically an ansatz that we got by assuming the limit exists and then solving for said limit. Continuing

$$b_{n+1}=|a_{n+1}-\sqrt{2}|=\left|\frac{a_n}{2}+ \frac{1}{a_n}-\sqrt{2}\right|$$

$$=\left|\frac{a_n^2-2\sqrt{2}a_n+2}{2a_n}\right|=\frac{|a_n-\sqrt{2}|^2}{2a_n}=\frac{b_n^2}{2a_n}\leq \frac{1}{2}b_n^2$$

Now, computing $b_1$ we have

$$b_1=|a_1-\sqrt{2}|=|1-\sqrt{2}|=\sqrt{2}-1<2-1=1$$

Next, if $b_n<1$ then

$$b_{n+1}\leq \frac{1}{2}b_n^2<\frac{1}{2}<1$$

and we conclude by induction that $0\leq b_n<1$. It is obvious that since $b_n$ is less than $1$ we have

$$b_n>b_n^2>\frac{1}{2}b_n^2\geq b_{n+1}$$

This implies $b_n$ is a monotonically decreasing sequence bounded below by $0$. It thus converges and we can solve for the limit $L$ using

$$L=\lim_{n\to\infty}b_{n+1}\leq \lim_{n\to\infty}\frac{1}{2}b_n^2=\frac{1}{2}L^2$$

This implies $L=0$ since $L=2$ is impossible by the conditions on $b_n$. But then

$$0=\lim_{n\to\infty}b_n=\lim_{n\to\infty}|a_n-\sqrt{2}|$$

$$\Rightarrow \lim_{n\to\infty}a_n=\sqrt{2}$$

As to your original question, there are many resources to proving $\sqrt{2}$ is not rational.

Answer 2

Maybe this is overkill, but one approach would be to use the Banach Fixed Point Theorem. On closed intervals, it simplifies to:

Let $f:[a,b]\to[a,b]$ be such that there exists $0\leq K<1$ with $|f(x)-f(y)|\leq K|x-y|$ for all $x,y$. This is called a contraction on $[a,b]$. Then $f$ has a unique fixed point in $[a,b]$ i.e. there is a unique $x^*\in[a,b]$ with $f(x^*)=x^*$. Furthermore, if we let $x_1\in X$ and define $x_{n+1}:=f(x_n)$ for all $n\geq 1$, then $x_n\to x^*$.

Applying this to the interval $[1,2]$, we define $f:[1,2]\to[1,2]$ by $f(x):=\frac{x}{2}+\frac{1}{x}$. Then $|f(x)-f(y)|\leq\frac{1}{2}|x-y|$ gives that $f$ is a contraction. Since $a_{n+1}=f(a_n)$ for all $n$, we have that $a_n$ converges to the unique fixed point of $f$ by BFPT, which one can easily check is $\sqrt{2}$. Since $a_n$ converges, it must be Cauchy and, of course, it converges outside of $\mathbb{Q}$.

Answer 3

I could obtain $a_n$ in a closed form. $$a_{n+1} = \frac{a_n}2 + \frac1{a_n}$$ Substituting $\,b_n=a_n-\sqrt2$ (so that $\,\lim b_n\rightarrow0$), $$b_{n+1}+\sqrt2=\frac{b_n+\sqrt2}2 + \frac1{b_n+\sqrt2}$$ $$b_{n+1}=\frac{b_n-\sqrt2}2 + \frac1{b_n+\sqrt2}=\frac{{b_n}^2}{2(b_n+\sqrt2)}$$ Taking reciprocal on both sides: $$\frac1{b_{n+1}}=\frac2{b_n}+\frac{2\sqrt2}{{b_n}^2}$$ Adding a constant $C$: $$\frac1{b_{n+1}}+C=\frac{2\sqrt2}{{b_n}^2}+\frac2{b_n}+C=2\sqrt2\left(\frac1{b_n}+C\right)^2\rightarrow C=\frac{\sqrt2}{4}$$ $$2\sqrt2\left(\frac1{b_{n+1}}+\frac{\sqrt2}{4}\right)=(2\sqrt2)^2\left(\frac1{b_n}+\frac{\sqrt2}{4}\right)^2$$ Substituting $\,c_n=2\sqrt2\left(\frac1{b_n}+\frac{\sqrt2}{4}\right)$, $$c_{n+1}={c_n}^2={c_{n-1}}^4=\cdots={c_1}^{2^n}$$ $$c_n={c_1}^{2^{n-1}}=\left(\frac{2\sqrt2}{1-\sqrt2}+1\right)^{2^{n-1}}=(-3-2\sqrt2)^{2^{n-1}}$$ $$\therefore\,\,a_n=b_n+\sqrt2=\frac{1}{\frac{c_n}{2\sqrt2}-\frac{\sqrt2}{4}}+\sqrt2=\sqrt2\left(\frac{2}{c_n-1}+1\right)\\ =\sqrt2\left(\frac{2}{(-3-2\sqrt2)^{2^{n-1}}-1}+1\right)$$

Answer 4

Given $a_1=1>0$ by induction $a_n>0$ for all $n$

$$a_{n+1}=\frac{a_n}{2}+\frac{1}{a_n}\underbrace{\geq}_{\text{AM GM}}\sqrt{2}$$ for all $n$, Now we will show sequence $\{a_n\}$ is decreasing

$$a_{n+1}-a_n=\frac{2-a_n^2}{2a_n}<0 $$ proved

Using $\textit{Monotone convergence theorem}$

$\{a_n\}$ converge

Let $\lim a_n=l$ then $$ l=\frac{l}{2}+\frac{1}{l}$$

and we get $\lim a_n=\sqrt{2}\in\mathbb{Q}^c$