Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
@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
1  
The last line is exactly $x_{n+1}\leq x_n$. –  Joe Johnson 126 Mar 16 '12 at 10:48
add comment

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

share|improve this answer
    
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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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