Show that $x_n$ is monotone and bounded: $x_{1} = 1$ and $x_{n+1}$ = $\sqrt{4x_n -1}$ A sequence is given by $X_{1} = 1$ and $X_{n+1}$ = $\sqrt{4x_n -1}$ for $n \in \mathbb{N}$.

*

*Show that $x_n$ is monotone and bounded.


*Find $\lim n \to \infty$ $x_n$.
Proposed solutions:

*

*I claim that $|x_n| \leq 4$ for $n \in \mathbb{N}$
By induction:
Base case: $x_1 = 1 < x_2 = \sqrt{3} < 4 $
Induction hypothesis: $|x_n| \leq 4$, prove that $|x_{n+1}| \leq 4$
$|x_{n+1}| = |\sqrt{4x_n -1}| \leq |\sqrt{4x_n}| = 2 |\sqrt{x_n}| \leq 4$
Induction step: $|x_n| \leq 4$ for all $n \in \mathbb{N}$

*

*Now, show that the sequence is increasing???



*$\lim n \to \infty$ $x_n = \lim n \to \infty \sqrt{4x_n -1} = L$
$\lim n \to \infty$ $4x_n - 1 = L^2$
$4L - 1 = L^2$
$L^2 - 4L + 1 = 0$
$L = 2 + \sqrt{3}$ (by the quadratic formula)
 A: Assume $x_n > x_{n-1} \implies x_{n+1} = \sqrt{4x_n - 1}> \sqrt{4x_{n-1}-1}=x_n$. Thus by induction, the sequence is monotonically increasing. The rest is the same to what you did.
A: $\underline{\text{Overview}}$
To Show: the sequence is strictly increasing.
In trying to show that the sequence is increasing, I normally work backwards.  That is, I start with the conclusion, derive the premise, and then verify that

*

*the premise is true

*the premise implies the desired conclusion.


$\underline{\text{Scratch Work Derivation}}$
The desired conclusion is that
$a_{n+1} > a_n \implies \sqrt{4x_n - 1} > x_n$.
Here, I have to note a problem.  How do I know that $(4x_n - 1)$ is always non-negative?  I will leave that issue for the moment.  That particular issue actually resolves to finding a lower bound for $x_n$.
If $A,B$ are both non-negative, then
$A > B \iff A^2 > B^2.$
So, under the assumption that $(4x_n-1) \geq 0$, I derive that I want $(4x_n - 1) > x_n^2.$
This implies that $x_n^2 - 4x_n + 1 < 0.$
This implies that
$$(x_n - 2)^2 - 3 < 0. \tag1 $$
Here, I note that $x_1 = 1, x_2 = \sqrt{3}$ and
$\displaystyle x_3 = \sqrt{4\sqrt{3} - 1} \approx 2.43.$
I then note that if I can prove that $x_n$ is bounded below by  $(2) : n \geq 3$, then this will prove that
$\displaystyle (x_n - 2) = \sqrt{(x_n - 2)^2}.$
So, it looks like I will need the intermediate results that

*

*$x_n$ is bounded below so that $(4x_n - 1) \geq 0$.

*$x_n$ is bounded below so that $(x_n) \geq 2 ~: ~n \geq 3.$
Assuming that I am able to prove both of the above results,
then (1) above translates to
$(x_n - 2) < \sqrt{3} \implies x_n < 2 + \sqrt{3}$.

$\underline{\text{Plan of Attack}}$
At this point, my tentative plan is clear.

*

*Show that $(4x_n - 1) \geq 0$.

*Show that $x_n \geq 2 ~: ~n \geq 3.$

*Show that $x_n < (2 + \sqrt{3})$.

*Use the 3rd result above, to work backwards, with the goal of implying that $x_{n+1} > x_n.$
Note that the 2nd intermediate result above implies the first one.
Personally, I try to avoid analyzing my scratch work implications, to see which ones are bi-conditional.  For me, it is simpler just to try to follow the scratch-work bread-crumbs backwards, verifying that the desired implication holds in each step.

$\underline{\text{Show that} ~x_n \geq 2 ~: ~n \geq 3}$
$x_3 \geq 2.$
Suppose that $x_n \geq 2.$  Then $x_{n+1} \geq \sqrt{(4 \times 2) - 1} = \sqrt{7} \geq 2.$

$\underline{\text{Show that} ~x_n < (2 + \sqrt{3}) ~: ~n \geq 3}$
Note that $(2 + \sqrt{3})^2 = 7 + 4\sqrt{3}.$
$2 \leq x_3 < (2 + \sqrt{3})$.
Suppose that $2 \leq x_n < (2 + \sqrt{3}).$
Then, $7 \leq (4x_n - 1) < 7 + 4\sqrt{3} = (2 + \sqrt{3})^2$.
Therefore, $2 < \sqrt{7} \leq x_{n+1} = \sqrt{4x_n - 1} < (2 + \sqrt{3}).$

$\underline{\text{Show that the sequence is strictly increasing}}$
$x_1 < x_2 < x_3$.
So, it is sufficient to prove the results for $x_3, x_4, \cdots.$
Use the already proven results (for $n \geq 3$) that

*

*$x_n \geq 2$

*$x_n < 2 + \sqrt{3}$.

Then $0 \leq (x_n - 2) < \sqrt{3}.$
Therefore, $(x_n - 2)^2 < 3.$
Therefore, $(x_n^2 - 4x_n + 1) < 0.$
Therefore, $x_n^2 < 4x_n - 1.$
Therefore, $x_n < \sqrt{4x_n - 1} = x_{n+1}.$
Here, the intermediate result that $x_n \geq 2$ implies that $\sqrt{4x_n - 1}$ is well defined.
