# Using Induction to Prove a Sequence is Strictly Increasing

Let $x_1=0$ and for all n, $x_{n+1}$=$\sqrt{2+x_n}$

a)Prove: $x_n <2$

b)Prove: $x_{n+1} > x_n$

I made it through part a painlessly, however, b is giving me problems

Part a: If $x_k<2$ then $x_{k+1}<2$

Attempt: $x_k+2<2+2$

$\sqrt{x_k+2}<\sqrt{2+2}$

$\sqrt{x_k+2}<2$

$x_{k+1}<2$ substitution from initial statement

Part b: Prove: $x_{n+1} > x_n$

Scratch work: $x_{k+1}$=$\sqrt{2+x_k}$ using algebra

$(x_{k+1})^2-2=x_k$

-
Talk about "race condition" :-) –  Asaf Karagila Oct 15 '11 at 23:59
arete: Are you sure $x_{n+1}<x_n$ and not $x_n<x_{n+1}$? –  Asaf Karagila Oct 16 '11 at 0:01
arete: the race condition comment was about me and Arturo making the same edit at the same time. Nothing about the contents of your question. –  Asaf Karagila Oct 16 '11 at 0:11
+1 for showing what you’ve done. –  Brian M. Scott Oct 16 '11 at 0:24
By definition $x_1=0$ and $x_2=\sqrt{2+x_1}=\sqrt2$, so $0\le x_1<x_2<2$. Now assume that $0\le x_n<x_{n+1}<2$ for some $n\in\mathbb{Z}^+$. Then $$2<2+x_n<2+x_{n+1}<4\;,$$ so $$\sqrt2<\sqrt{2+x_n}<\sqrt{2+x_{n+1}}<2\;.\tag{1}$$ But $\sqrt{2+x_n}=x_{n+1}$, and $\sqrt{2+x_{n+1}}=x_{n+2}$, so $(1)$ immediately implies that $$0\le x_{n+1}<x_{n+2}<2\;,$$ and it follows by induction that $0\le x_n<x_{n+1}<2$ for all $n\in\mathbb{Z}^+$.