# Basic Sequence Proof

Given these condition, I am seeking a proof:

Define a sequence of real numbers by $x_1 = 3$ and then, for $n \geq 2$,

$x_n = \sqrt{2 \; x_{n-1} + 1 }$

Prove that for all positive integers $n$, $x_n \geq x_{n+1}$.

I began a proof by induction, but ran out of steam. I tested the base case for $n=2$ , but I could not seem to get anywhere after that. I feel like there is not enough information (ie recursion, sequence, etc) to prove by induction. Is an induction proof an efficient way to proceed? Are there easier methods of proof?

-
If you basically prove $x_n >= \sqrt{2}+1$ and $x_n >= \sqrt{2}-1$ for every $n$, you are done –  Kirthi Raman Mar 15 '12 at 22:32
@Kirthi Raman : You should learn how to use LaTeX coding properly. Use \le to type $\le$ when you are between cash symbols (math mode). –  Patrick Da Silva Mar 15 '12 at 22:50
Set $x_n = 2y_n$ and you get it in the form $y_{n+1} = \sqrt{y_n + c}$. Which is a dupe. –  Aryabhata Mar 16 '12 at 0:06
possible duplicate of [On the sequence $x_{n+1} = \sqrt{c+x_n}$ ](math.stackexchange.com/questions/115501/…) –  Aryabhata Mar 16 '12 at 0:06
Thank you Patrick, I have to learn many more things and latex is sure in my list –  Kirthi Raman Mar 16 '12 at 0:52
show 1 more comment

For the induction, assume that $x_n\leq x_{n-1}$. Then

\begin{align*} x_n &\leq x_{n-1}\\ 2x_n &\leq 2x_{n-1}\\ 2x_n+1 &\leq 2x_{n-1}+1\\ \sqrt{2x_n+1} &\leq \sqrt{2x_{n-1}+1}\\ \end{align*}

-
@Henry: Thanks. –  Joe Johnson 126 Mar 15 '12 at 22:51
can I simply make that assumption though? Wouldn't a typical induction proceed by assuming the given $x_{n+1} \leq x_n$ rather than $x_n \leq x_{n-1}$? –  Dominick Gerard Mar 15 '12 at 22:54
It doesn't matter. If you'd like, you can change all the $n$'s to $n+1$ and all the $n-1$'s to $n$'s. –  Joe Johnson 126 Mar 15 '12 at 23:05
I see what you mean. I'm sorry but I can't see how this induction would be completed? –  Dominick Gerard Mar 15 '12 at 23:09
The last line is exactly $x_{n+1}\leq x_n$. –  Joe Johnson 126 Mar 16 '12 at 10:48

$x_n \geq x_{n+1}$ if and only if $x_n \geq \sqrt{2x_n+1}$ and this is true if and only if ${x_n}^2 \geq 2x_n+1$ which is same as ${x_n}^2 -2x_n-1 \geq 0$, and this expression can be written as $(x_n+\sqrt{2}-1)(x_n-\sqrt{2}-1) \geq 0$

The signs in first expression was flipped, just fixed it (Patrick was right)

So try to show that expression is always positive for every $n$

Now how do we show $x_n \geq \sqrt{2}+1$ and $x_n \geq 1-\sqrt{2}$ for every $n$ by induction?

I think Joe Johnson has better proof, follow that.

-
The roots of the equation are $\frac 12 \left(-(-2) \pm \sqrt{(-2)^2 - 4(-1)(1)} \right) = \frac 12 \left( 2 \pm \sqrt 8 \right) = 1 \pm \sqrt 2$. So the factorization should be $$x_n^2 - 2x_n -1 = (x_n - (1+\sqrt 2))(x_n - (1-\sqrt 2))$$ which is not the same as your expression. But you got the idea so I upvoted anyway. (I noticed this because the roots should be $a \pm \sqrt b$ something, so the sign should change on the $\sqrt{b}$, not on the other term.) –  Patrick Da Silva Mar 15 '12 at 22:53
I understand what you guys have done here, but do you have any hints on how to proceed to prove that $x_n \geq (1+\sqrt{2})$ and $x_n \geq (1-\sqrt{2})$? –  Dominick Gerard Mar 15 '12 at 22:59
@Patrick I think it is the same expression without the parenthesis, i.e. $(x_n-\sqrt{2}+1)(x_n-\sqrt{2}-1)=(x_n-(\sqrt{2}-1))(x_n-(\sqrt{2}+1))$ –  Jeremy Carlos Mar 15 '12 at 23:50
@Jeremy : it cant be the same, the roots are not$\sqrt 2 \pm 1$, theyre $1\pm 2$. Recall that a polynomial with two distinct roots a and b is always of the form$(x-a)(x-b)$ or expand it correctly, youll see i am right –  Patrick Da Silva Mar 16 '12 at 4:23
Hm at first i thought you said i was wrong. But yes the parenthesis.dont matter, i was putting emphasis on the roots ; it is a good mathematician reflex, since a polynomial with as many distinct roots as its degree is a product of linear factors of the form $x-a_i$, where $a_i$'s are the roots. Therefore since my roots are $1\pm \sqrt 2$ i dont want to remove my parenthesis to show the roots better. –  Patrick Da Silva Mar 16 '12 at 4:27
show 1 more comment

Calculate $x_2$, and notice that $x_{n+1}-x_n$ has the same sign as $x_{n}-x_{n-1}$, and inductively, the same sign as $x_2-x_1$, which you just calculated.

-