2
$\begingroup$

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?

  • 0
    If you basically prove $x_n >= \sqrt{2}+1$ and $x_n >= \sqrt{2}-1$ for every $n$, you are done2012-03-15
  • 0
    @Kirthi Raman : You should learn how to use LaTeX coding properly. Use \le to type $\le$ when you are between cash symbols (math mode).2012-03-15
  • 0
    Set $x_n = 2y_n$ and you get it in the form $y_{n+1} = \sqrt{y_n + c}$. Which is a dupe.2012-03-16
  • 0
    possible duplicate of [On the sequence $x_{n+1} = \sqrt{c+x_n}$ ](http://math.stackexchange.com/questions/115501/on-the-sequence-x-n1-sqrtcx-n)2012-03-16
  • 0
    Thank you Patrick, I have to learn many more things and latex is sure in my list2012-03-16
  • 0
    Aryabhata is a veteran here, it is indeed a duplicate.I have been on this group only past 23 days and have to learn every day. (I am his fan!)2012-03-16

3 Answers 3

4

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

  • 0
    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}$?2012-03-15
  • 0
    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.2012-03-15
  • 0
    I see what you mean. I'm sorry but I can't see how this induction would be completed?2012-03-15
  • 1
    The last line is exactly $x_{n+1}\leq x_n$.2012-03-16
1

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

  • 0
    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.)2012-03-15
  • 0
    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})$?2012-03-15
  • 0
    @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))$2012-03-15
  • 0
    @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 right2012-03-16
  • 0
    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.2012-03-16
  • 0
    But my expression is different from kirthi's thats for sure.2012-03-16
0

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.