# Prove a limit exists and find it if $x_{n+1} = 1- {1\over 4x_n}$, where $x_1 = a$ and range of $a$ is given.

Given a recurrence relation: $$x_{n+1} = 1- {1\over 4x_n} \\ x_1 = a \in\Bbb R \\ n\in\Bbb N$$ Prove that the limit exists and evaluate: $$\lim_{n\to\infty}x_n$$ given $$a$$: \begin{align*} a &> {1\over 2} \tag 1\\ a &\in \left(0, {1\over 4}\right) \tag 2\\ a & < 0 \tag3 \end{align*}

First find possible values of the limit by finding fixed points of the recurrence. Suppose $$\lim x_n = L$$, then: $$L = 1 - {1\over 4L} \iff L = {1\over 2}$$

Start with case $$(1)$$.

Boundedness. Using induction one may show that the sequence is bounded below, after that what is left to prove is monotonicity of $$x_n$$: \begin{align} x_1 > {1\over 2} &\iff 4x_1 > 2 \\ &\iff {1\over 4x_1} < {1\over 2} \\ &\iff -{1\over 4x_1} > -{1\over 2} \\ &\iff \underbrace{1-{1\over 4x_1}}_{x_2} > {1\over 2} \end{align} Suppose $$x_n > {1\over 2}$$, then: $$x_n > {1\over 2} \implies \underbrace{1 - {1\over 4x_n}}_{x_{n+1}} > {1\over 2}$$ Monotonicity. Consider the following expression: $$x_{n+1} - x_n = 1 - {1\over 4x_n} - x_n \\ x_{n+1} - x_n = \frac{4x_n - 1 - x_n^2}{4x_n} = \frac{\overbrace{-(x_n - 1)^2}^{<0}}{\underbrace{2x_n}_{>0}} \\ \implies x_{n+1} < x_n$$ Now by monotone convergence theorem: $$\boxed{\lim_{n\to\infty}x_n = {1\over 2}}$$

Proceed to case $$(2)$$. Here we have: \begin{align} x_1 \in \left(0, {1\over 4}\right) &\implies {1\over x_1} \in (4, +\infty) \\ &\implies {1\over 4x_1} \in (1, +\infty) \\ &\implies -{1\over 4x_1} \in (-\infty, -1)\\ &\implies \underbrace{1-{1\over 4x_1}}_{x_2} \in (-\infty, 0) \end{align}

By this we have that $$x_2$$ is less than $$0$$. Try one more: \begin{align} x_2 \in(-\infty, 0) &\implies {1\over x_2} \in (-\infty, 0) \\ &\implies -{1\over 4x_2} \in (0, +\infty) \\ &\implies \underbrace{1-{1\over 4x_2}}_{x_3} \in (1, +\infty) \\ \end{align}

Here we got $$x_3 > 1 > {1 \over 2}$$. That means we could reindex the sequence from case $$(1)$$ and set $$x_3$$ as $$x_1$$ in $$(1)$$. Which by monotone convergence theorem once again yields: $$\boxed{\lim_{n\to\infty} x_n = {1\over 2}}$$

There is actually a third case which was not originally in the post. Here is the reasoning related to it: \begin{align} x_1 \in (-\infty, 0) &\implies {1\over 4x_1} \in (-\infty, 0) \\ &\implies -{1\over 4x_1} \in (0, +\infty) \\ &\implies 1-{1\over 4x_1} \in (1, +\infty) \end{align}

As in case $$(2)$$ lets consider one more term: \begin{align} x_2 \in (1, +\infty) &\implies {1\over x_2} \in (0, 1)\\ &\implies {1\over 4x_2} \in \left(0, {1\over 4}\right) \\ &\implies -{1\over 4x_2} \in \left(-{1\over 4}, 0\right) \\ &\implies \underbrace{1-{1\over 4x_2}}_{x_3} \in \left({3\over 4}, 1\right) \\ \end{align}

Here we may either proceed with induction or, since $$x_3 > {1\over 2}$$, use this result in $$(1)$$. From which it follows that the limit: $$\boxed{\lim_{n\to\infty}x_n = {1\over 2}}$$

Thanks to @Did I know a cobweb plot gives a lot of useful information. So here is a sandbox I've been using.

I would like to kindly request a verification of the solution above, any notes or nitpicks are appreciated. Thank you!