# Given $x_1 := \sqrt{2}$ and $x_{n+1} :=\sqrt{2x_n}$, prove $\sqrt{2} ≤ x_n ≤ 2$

Let $x_1 := \sqrt{2}$ and $x_{n+1} :=\sqrt{2x_n}$ for all $n \in \mathbb{N}$.

By using proof by induction:

(i) Prove that $\sqrt{2} ≤ x_n ≤ 2$ for all $n \in \mathbb{N}$.

(ii) Prove that $x_n ≤ x_{n+1}$ for all $n \in \mathbb{N}$.

For (i)

Let's prove the case base case, for $n=1$ we have that $\sqrt{2} \leq x_1\leq 2$ which is clearly true by $x_1=\sqrt{2}$

Now we assume true for $n=k$ $\Longrightarrow$ $\sqrt{2}\leq x_k\leq2$ and we are required to prove $\sqrt{2}\leq x_{k+1} \leq 2$.

From our hypothesis : $\sqrt{2}\leq x_k\leq2$ however we know that $x_{k+1} =\sqrt{2x_k}\Longrightarrow x_k = \frac{(x_{k+1})^2}{2}$ so we have $\sqrt{2}\leq \frac{(x_{k+1})^2}{2}\leq2 \Leftrightarrow \sqrt{2\sqrt{2}}\leq x_{k+1} \leq 2$.

How do I proceed?

• the last "iff" must be with "$x_k$" – Martín Vacas Vignolo Dec 28 '17 at 21:17
• $\sqrt{2\sqrt{2}}=\sqrt{2}\sqrt{\sqrt{2}}$ what can you say about $\sqrt{\sqrt{2}}$ ? – Atmos Dec 28 '17 at 21:17

Note that $\sqrt{2} \leq \sqrt{2\sqrt{2}}\leq x_{k+1} \leq 2$ so more generally, we can say that $\sqrt{2} \leq x_{k+1} \leq 2$ because if $\sqrt{2} \leq \sqrt{2\sqrt{2}}$ and $\sqrt{2\sqrt{2}}\leq x_{k+1}$, then by transitivity of partial ordering, $\sqrt{2} \le x_{k+1}$ (What happened to the numbers between $\sqrt{2}$ and $\sqrt{2\sqrt{2}}$? Well, I think we can make this generalization because in this sequence, there is no number between them. This is the result of second part).

From

$$\sqrt2<x_n<2$$ you can deduce

$$\sqrt{2\sqrt2}<\sqrt{2x_n}<2$$

and obviously

$$\sqrt{2}<\sqrt{2x_n}<2,$$ which is nothing but

$$\sqrt{2}<x_{n+1}<2.$$

Hints:

• $\;\displaystyle \frac{x_{n+1}}{2}=\sqrt{\frac{x_{n}}{2}}\,$, so $\;\displaystyle \frac{x_{n+1}}{2} \le 1 \;\iff\; \frac{x_{n}}{2} \le 1 \;\iff\; \cdots \;\iff\; \frac{x_1}{2} \le 1\,$

• $\;\displaystyle \frac{x_{n+1}}{x_n}=\sqrt{\frac{x_{n}}{x_{n-1}}}\,$, so $\;\displaystyle \frac{x_{n+1}}{x_n} \ge 1 \;\iff\; \frac{x_{n}}{x_{n-1}} \ge 1 \;\iff\; \cdots \;\iff\; \frac{x_2}{x_1} \ge 1\,$

Let $f(x) = \sqrt{2x}$ and note that if $x \in [0,2]$ we have $x \le f(x) \le 2$.

To see this note that for $y \in [0,1]$ we have $0 \le y \le \sqrt{y} \le 1$. Now let $y={x \over 2}$ and multiply across by $2$.

• I'm sorry but I can't understand the answer... I mean, clearly it is a generalization of what he is proving but in order to show that $x\leq f(x)$ the OP needs other tools I don't believe he has. – Yanko Dec 28 '17 at 21:23
• @yanko: The only tool needed is to know that $x \le \sqrt{x}$ for $x \in [0,1]$. – copper.hat Dec 28 '17 at 21:32

In a reverse order ...

Having $f(x)=\sqrt{2x}$ where $x_{n+1}=f(x_n)$ we know that $f'(x)=\frac{1}{\sqrt{2x}}>0, \forall x>0$. This means function $f(x)$ is ascending on $x>0$. We also have that $\sqrt{2}<\sqrt{2\sqrt{2}} \iff 0<x_1<x_2$ and then $f(x_1) \leq f(x_2) \iff x_2 \leq x_3$ and by induction $x_n\leq x_{n+1}$ and part $(ii)$ is done.

But then, from $(ii)$ we have $x_n \geq x_1=\sqrt{2}, \forall n$. And for $\forall x$ s.t. $\sqrt{2}\leq x \leq 2 \Rightarrow f(\sqrt{2}) \leq f(x) \leq f(2)$ which is $\sqrt{2}\leq \sqrt{2\sqrt{2}}\leq f(x) \leq 2$. Altogether: $$\sqrt{2}\leq x \leq 2 \Rightarrow \sqrt{2}\leq f(x) \leq 2 \tag{1}$$

As a result, since $\sqrt{2}\leq x_1\leq 2$ and if we assume $\sqrt{2}\leq x_n\leq 2$, we obtain from $(1)$ $\sqrt{2}\leq f(x_n)\leq 2 \iff \sqrt{2}\leq x_{n+1}\leq 2$ and this completes part $(i)$, by induction.

The base case $\sqrt{2}\le x_1\le2$ is obviously true.

Now $\sqrt{2}\le x_{n+1}\le 2$ if and only if $$2\le 2x_n\le 4$$ that is, $$1\le x_n\le 2$$ which is true by the induction hypothesis, because $x_n\ge\sqrt{2}>1$.

Also $$x_{n+1}-x_n=\sqrt{2x_n}-x_n=\frac{2x_n-x_n^2}{\sqrt{2x_n}+x_n} =\frac{x_n}{\sqrt{2x_n}+x_n}(2-x_n)\ge0$$

By logarithms:

Let $y_n:=\log_2x_n$.

$$\frac12\le y_n\le1\implies\frac12\le\frac{y_n+1}2\le1\iff0\le y_n\le1.$$