Use induction to show $0< x_n < 3$ and find its limit

Question

Q define a sequence by $x_1=1$, $x_{n+1}=3-\frac{1}{x_n}$ for all $n \in \mathbb{N}$

a) Use induction to show $ 0 < x_n < 3$ for all $n \in \mathbb{N}$, and <$x_n$> is monotone increasing

my take: when $n=1$, $x_2=3-\frac{1}{x_1}=3-1=2 < 3$ so this is true $\checkmark$ when $n=n+1$, $x_{n+2} = 3-\frac{1}{x_{n+1}}$ $\to$ $x_{n+1} = \frac{1}{3-x_{n+2}} \to \frac{8}{3} = -\frac{1}{x_{n+2}} + \frac{1}{x_n}$???? I think I am so lost but I don't quite know how to fix it..A question specifically asks to prove it is monotone increasing, so I have to somehow get $x_n < x_{n+1}$

b) Conclude $x_n \to L$ and find $L$

my take: since by $a)$ it's monotone increasing so $L$ is a fixed point, thus we can write $L = 3-\frac{1}L$ then solve for $L$

Could you help me with $a)$ and verify if i am on a right track with $b)$?

Answer 1

Let's first show that the sequence $\{x_n\}$ is monotone.

• $x_1 = 1 \le 2 = x_2$.
• Assume that $0 < x_1 \le x_2 \le x_n \le x_{n+1}$. Notice that $f(x) = 3 - \frac 1x$ is non-decreasing on $(0,\infty)$ since $f'(x) = \frac{1}{x^2} > 0$. Then $x_{n + 1} = f(x_n) \le f(x_{n+1}) = x_{n + 2}$.

Let's now prove that $x_n \in (0,3)$ for all $n$. Again, we procede by induction, the base case being trivially satisfied.

• Assume $0 < x_n < 3$, then $x_{n+1} = 3 - \frac{1}{x_n} < 3$ since $x_n$, and hence $\frac{1}{x_n}$, is strictly positive. To prove that $x_{n + 1} > 0$ we can now use that the sequence is monotone. Indeed, $1 = x_1 \le x_n$ so that $$x_{n + 1} = 3 - \frac{1}{x_n} \ge 3 - \frac{1}{x_1} = 2 > 0.$$

Answer 2

a) I think we can instead prove $1 \le x_n < 3$. Then $0 < x_n < 3$ holds. By induction,

(i) $x_1 = 1 \in [1, 3)$.

(ii) Assume $1 \le x_k < 3 \Rightarrow -1\le -\frac{1}{x_k} < -\frac{1}{3} \Rightarrow 1 \le x_{k+1}= 3-\frac{1}{x_k} < 3$

Thus $1 \le x_n < 3 \Rightarrow 0 < x_n < 3$.

Use induction to prove $\{x_n\}$ is increasing.

(i) $x_1 < x_2$

(ii) Assume $x_n > x_{n-1}$ for $n\ge2$ $$ x_{n+1} - x_{n} = \frac{1}{x_{n-1}} - \frac{1}{x_n} = \frac{x_n - x_{n-1}}{x_n x_{n-1}} > 0 $$ Thus $\{x_n\}$ is increasing.

(b) You should add the condition that $x_n$ is bounded from above as the reason why $\{x_n\}$ converges.

Answer 3

Let $f(x) = 3 -{1 \over x}$ and note that $f$ is increasing for all $x>0$.

Let $\phi(x) = f(x) -x$ and note that $\phi''(x) = -{2 \over x^3}$, hence $\phi$ is concave. Note that $\lim_{x \downarrow 0} \phi(x) = \lim_{x \to \infty} \phi(x) = - \infty$ and $\phi(1) >0$. It follows that there are exactly two points $x_1,x_2$ with $0<x_1 <1 < x_2 < 3$ such that $\phi(x_1) = \phi(x_2) = 0$, and if $x \in [x_1,x_2]$ then $\phi(x) \ge 0$.

Since $f$ is increasing and $f(x_2) = x_2$, we see that if $x \in (0,x_2]$ then $f(x) \le f(x_2) = x_2$.

By the same token, since $f(x_1) = x_1$, we see that if $x \ge x_1$ then $f(x) \ge x_1$.

Hence if $x \in [x_1,x_2]$ then $f(x) \in [x_1,x_2]$ and $\phi(x) \ge 0$.

Since $x_0 = 1 \in [x_1,x_2]$ and $x_{n+1} = f(x_n)$, we see that $x_n$ is increasing and $x_n \le x_2$.

Hence $x_n$ converges to some $\hat{x} \in [x_1,x_2]$ and hence $f(\hat{x}) = \hat{x}$ or $\phi(\hat{x}) = 0$, hence $\hat{x} = x_2$.

Note that $x_2$ solves $x_2^2 = x_2 f(x_2)$, solving the resulting quadratic equation shows that $x_2 = {1 \over 2} (3+\sqrt{5})$.