Where did I go wrong in my proof that for all $n \in \mathbb{Z}^+$, $\sqrt{2} < a_n$ with $(a_n)$ being a particular recursive sequence?

Question

I am in Introduction to Abstract Math, and I have taken Calculus 1, Linear Algebra, and Discrete Math. I got stuck with an apparent contradiction in my proof and wanted to know where I messed up:

Consider the sequence $(a_n)$ defined recursively by: $$a_1 = 3, \:\:\:\:\:\:\: a_{n+1} = \frac{a_n}{2}+\frac{1}{a_n} \:\:\:\:\:\:\: (n \geq 1).$$ Prove that $\sqrt{2}$ is a lower bound for $(a_n)$.

This can be rewritten as: Prove for all $n \in \mathbb{Z}^+$, $\sqrt{2} < a_n$, which we can prove with strong induction.

Base Step Check for $n=1$.

$$a_1 = 3 > \sqrt{2}$$

Check for $n=2$.

$$a_2 = \frac{a_1}{2} + \frac{1}{a_1} = \frac{3}{2} + \frac{1}{3} = \frac{11}{6} > \sqrt{2}$$.

Therefore, the statement holds true for $n=1, n=2$.

Inductive Step Assume that $a_n > \sqrt{2}$ for $1 \leq n \leq k$ with $k \in \mathbb{Z}^+$. Prove $a_{k+1} > \sqrt{2}$.

$$a_k = \frac{a_{k-1}}{2} + \frac{1}{a_{k-1}} > \sqrt{2}$$ $$a_{k+1} = \frac{a_k}{2} + \frac{1}{a_k}$$ $$a_{k+1} = \frac{\frac{a_{k-1}}{2} + \frac{1}{a_{k-1}}}{2} + \frac{1}{\frac{a_{k-1}}{2} + \frac{1}{a_{k-1}}}$$ $$a_{k+1} = \frac{2a_{k-1}}{a_{k-1}^2 + 2}+\frac{a_{k-1}}{4}+\frac{1}{2a_{k-1}}$$ $$a_{k+1} = \frac{2a_{k-1}}{a_{k-1}^2 + 2}+\frac{1}{2}(\frac{a_{k-1}}{2}+\frac{1}{a_{k-1}})$$ $$a_{k+1} = \frac{2a_{k-1}}{a_{k-1}^2 + 2}+\frac{1}{2}(a_k)$$ $$a_{k+1} = (\frac{2a_{k-1}}{a_{k-1}^2 + 2} \times \frac{1}{a_k})a_k+\frac{1}{2}(a_k)$$ $$a_{k+1} = a_k (\frac{2a_{k-1}}{a_{k-1}^2 + 2} \times (\frac{2}{a_{k-1}}+a_{k-1}) +\frac{1}{2})$$

Here's where I got stuck. I plugged it into Wolfram Alpha to do the algebra for that step and see if there was equivalent forms, and I saw that what was in the parenthesis was equal to $\frac{5}{2}$, which gives $$a_{k+1} = \frac{5a_{k}}{2}$$ which doesn't make sense as the sequence would be increasing way too fast.

Where did I mess up in my proof?

Answer 1

As another approach, let $f(x)=\frac x2+\frac 1x$ for $x>0$. It is easy to confirm that $$f(x)=\sqrt 2\iff x=\sqrt 2$$

As $f(x)$ is clearly continuous for all $x>0$ we see that $x>\sqrt 2$ must then imply that $f(x)>\sqrt 2$ and we are done.

Answer 2

You didn't really "mess up". You just got stuck because this approach leads nowhere. However, there is certainly something wrong in what you typed in Wolfram Alpha.

You could do this, assuming $a_n>0$:

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

And there is equality only if $a_n=\sqrt{2}$. Given that $a_1=3>\sqrt{2}$, you get that $a_n>\sqrt{2}$ for all $n\ge1$.