# Bounded recursive sequence - Proof by induction

Given the sequence $$(x_n)$$ defined by

$$\begin{cases} x_1 &= 1\\ x_{n+1} &= \frac{1}{2}\left(x_n + \frac{2}{x_n}\right), \end{cases}$$ prove that $$1 \leq x_n \leq \frac{3}{2}, \forall n \in N$$.

I verified the base case for $$n=1$$ and $$n=2$$. Assumed that the boundaries hold for all $$k \leq n$$. Used the induction hypothesis to show that $$1 \leq x_n \leq \frac{3}{2} \Rightarrow \frac{1}{2} \leq \frac{x_n}{2} \leq \frac{3}{4}$$ and $$1 \leq x_n \leq \frac{3}{2} \Rightarrow \frac{2}{3} \leq \frac{1}{x_n} \leq 1$$.

Adding term by term I got $$1 \leq \frac{7}{6} \leq \frac{1}{2}(x_n + \frac{2}{x_n}) \leq \frac{7}{4}$$.

Is my reasoning correct? How could I show that $$\frac{3}{2}$$ is also an upper boundary, since it is smaller than $$\frac{7}{4}$$?

PS: I found similar questions for which $$x_n \leq \sqrt{2}$$.

For induction step we have to prove $$1\leqslant x\leqslant\frac32\Rightarrow 2\leqslant x+\frac2x\leqslant3$$ that is $$x^2-3x+2\leqslant0$$ and $$x^2-2x+2\geqslant0$$ for $$1\leqslant x\leqslant\frac32$$

Can you finish?

• I'll try to work it out. Apr 4 '19 at 1:46

Let $$a \gt 0$$.

Exercise 1: $$\left(\frac{a}{2} + \frac{1}{a}\right)^2 = 2 \Leftarrow\Rightarrow a = \sqrt 2$$.

Exercise 2: $$\left(\frac{a}{2} + \frac{1}{a}\right)^2 \ge 2$$.

Hint: Apply the quadratic formula to a quartic polynomial.

Using the exercises, if $$n \gt 1$$ then $$x_n \gt \sqrt 2 \gt 1$$, and we get 'one half' (and something stronger) of what the OP was looking for.

Since $$x_2 = \frac{3}{2}$$, $$x_2 \le \frac{3}{2}$$.

Assume for some fixed $$k \gt 2$$ that $$x_k \leq \frac{3}{2}$$.
We will show that $$x_{k+1} \leq \frac{3}{2}$$ is also true, allowing us to employ induction and find the bounds for the OP's sequence.

In general, if $$\sqrt 2 \leq a \leq \frac{3}{2}$$ then

$$\tag 1 \frac{a}{2} \leq \frac{3}{4}$$

and

$$\tag 2 \frac{1}{a} \leq \frac{1}{\sqrt 2}$$

So

$$\tag 3 \frac{1}{2}\left(a + \frac{2}{a}\right) = \frac{a}{2} + \frac{1}{a} \le \frac{3}{4} + \frac{1}{\sqrt 2} \lt \frac{3}{2}$$

Applying induction we conclude that for $$n \gt 1$$,

$$\sqrt 2 \le x_n \le \frac{3}{2}$$

and we can also state that for $$n \ge 1$$ that

$$1 \le x_n \le \frac{3}{2}$$

With the above work completed and working out some terms of the sequence $$x_n$$, an observant analyst would be naturally drawn to the question

If $$\delta \gt 0$$ and $$a = \sqrt 2 + \delta$$, can we assert that $$\frac{a}{2} + \frac{1}{a}$$ is less than $$a$$?

The answer is yes and is demonstrated using simple algebra.