# Define a sequence {$\ x_n$} recursively, show it is strictly decreasing

Define a sequence {$\ x_n$} recursively by

$$x_{n+1} = \sqrt{2 x_n -1}, \ and \ x_0=a \ where \ a>1$$ Prove that {$\ x_n$} is strictly decreasing. I'm not sure where to start.

• Welcome to Mathematics Stack Exchange! I would suggest you to explain a little bit how you tried to solve it (at least your thoughts), so other people could help you better. Good luck! Commented May 29, 2015 at 0:07

We need to show that $x_{n+1}-x_n<0$ for all $n\ge 1$ whenever x_0=a>1$First note that if$x_n>1$, then$x_{n+1}=\sqrt{2x_n-1}>1$also. And since$x_0>1$, then we have that$x_n>1$for all$n$. Next, to show$x_{n+1}-x_n<0$, all we need to show is that$2x_n-1<x_n^2$. But this is trivially the same as$x_n^2-2x_n+1=(x_n-1)^2>0$. And since we know$x_n>1$, then we are done! One can view it as a function$a_n = f(a_{n-1})$whereas$f(x) = \sqrt{2x-1}$, then the monotonicity of$a_n$depends on$f'(x)$. And$f'(x) = \dfrac{1}{\sqrt{2x-1}} > 0$, this means the sequence is increasing as stated. Hint: It is enough to show the graph of$y=\sqrt{2x-1}$is under the straight line$y=x$. For an increasing sequence it should be over this line. Use induction. Your base case is$a > \sqrt{2a - 1} \Leftrightarrow a^2 > 2a - 1 \Leftrightarrow (a-1)^2 > 0$, which is true since$a > 1$. Furthermore, notice that$x_1 = \sqrt{2a - 1} > 1$. Inductive step: assume that$x_k < x_{k-1}$and$x_k > 1$. We wish to show that$x_{k+1} < x_k$. Well, we have$x_{k+1} = \sqrt{2 x_k - 1}$, so $$\sqrt{2 x_k - 1} < x_k$$ $$0 < (x_k - 1)^2$$ Finally, this last statement is true since we assumed$x_k > 1$. Thus, we get that$x_{k+1} < x_k$and that$x_{k+1} > 1$, so the induction is proven. • Careful with the logic in your base case. You have shown your desired conclusion implies something True, which shows nothing. It can be fixed by changing all your$\Rightarrow$into$\Leftrightarrow$. Commented May 29, 2015 at 0:17 • @SimonS Yeah, it was a typo. Sorry – MT_ Commented May 29, 2015 at 4:47 The condition to prove is that$x_{n+1}<x_n$, that is, $$\sqrt{2x_n-1}<x_n$$ that's equivalent to $$2x_n-1<x_n^2$$ or $$x_n^2-2x_n+1>0$$ that's true provided you prove in advance that$x_n\ne1$, for all$n$, and moreover that$x_n\ge1/2$, for all$n$, in order that the expressions are meaningful. Try proving, instead, that$x_n>1$, by induction on$n$. • Why do you say that$x_n > 1/2$must be true? Isn't it just that$x_n \neq 1$? – MT_ Commented May 29, 2015 at 0:13 • @Soke If$x_n<1/2$, then$2x_n-1<0$and you can't define$x_{n+1}$. Commented May 29, 2015 at 8:20 • Okay, but you're glossing over the fact that$x \neq 1\$ is necessary for the inequality to hold.