7
$\begingroup$

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?

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

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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\,$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yanko Dec 28 '17 at 21:23
  • $\begingroup$ @yanko: The only tool needed is to know that $x \le \sqrt{x}$ for $x \in [0,1]$. $\endgroup$ – copper.hat Dec 28 '17 at 21:32
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

By logarithms:

Let $y_n:=\log_2x_n$.

The recurrence reads

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.