# Using induction to prove a sequence $a_1=1$ and $a_{n+1}=3-\frac{1}{a_n}$ is increasing

I have a sequence defined by $$a_1=1$$ and $$a_{n+1}=3-\frac{1}{a_n}$$. I need to use induction to show that the sequence is increasing and $$a_n<3$$ for all $$n$$.

Also to deduce that $$a_n$$ is convergence and find its limit.

So far I have found: $$a_n and $$a_{n+1}>0$$

Then $$a_{n+1}=3-\frac{1}{a_n}$$ with $$a_{n+2}=3-\frac{a_n}{3a_n-1}$$

But not really sure how to go any further even if this is the right way to go in the first place? Any input would be greatly be appreciated!

## 2 Answers

You have already done most of the work. By showing that $$1 \leq a_n < a_{n+1} < 3$$ where $$n \in \mathbb{Z}_+$$, you have demonstrated that the sequence is increasing and bounded above by $$3$$. Now the Monotone Convergence Theorem says that any increasing sequence that is bounded above converges; indeed it converges to the supremum of $$\{a_n\}_{n \in \mathbb{Z}_+}$$. So you now know that $$\lim\limits_{n \to \infty} a_n = \alpha \in \mathbb{R}$$ for some $$\boxed{1 \leq \alpha \leq 3}$$

To find $$\alpha$$, note that $$f(x) = 3 - \frac{1}{x}$$ is a continuous real valued function for real $$x > 0$$. So, by continuity, and the fact that $$\alpha > 0$$, we can put limits inside the function like so: $$\lim\limits_{n \to \infty}f(a_n) = f(\lim\limits_{n \to \infty}a_n)$$ But the LHS is just $$\lim\limits_{n \to \infty}f(a_n) = \lim\limits_{n \to \infty}(3 - \frac{1}{a_n}) = \lim\limits_{n \to \infty} a_{n + 1} = \alpha$$ while the RHS is just $$f(\lim\limits_{n \to \infty}a_n) = f(\alpha) = 3 - \frac{1}{\alpha}$$. So, putting LHS $$=$$ RHS we get $$\alpha = 3 - \frac{1}{\alpha}$$ $$\boxed{\alpha^2 - 3 \alpha + 1 = 0}$$ Now, solve this quadratic equation to get the value of $$\alpha$$. You will get two values but only one of them is the answer. See if you can eliminate the wrong one using the properties of $$\alpha$$.

• Thank you very much! – Olly Reynolds Apr 20 at 11:54
• No problem, you're welcome. – ZeroXLR Apr 20 at 11:56

Let $$P(n)$$ be the assertion “$$a_n\in\left[1,\frac{3+\sqrt5}2\right)$$ and $$a_{n+1}>a_n$$”.

If $$n=1$$, then this is true, since $$a_1=1$$ and $$a_2=2>1=a_1$$.

Let $$n\in\mathbb N$$ and assume that $$P(n)$$ holds. Then:

• $$a_{n+1}=3-\frac1{a_n}<3$$. since $$a_n\geqslant1>0$$;
• $$a_{n+1}\geqslant1$$, since $$a_{n}\geqslant1$$ and so $$3-\frac1{a_n}\geqslant3-\frac11=2$$.
• $$a_{n+2}-a_{n+1}=3-\dfrac1{a_{n+1}}-a_{n+1}=\dfrac{3a_{n+1}-1-{a_{n+1}}^2}{{a_{n+1}}^2}=\dfrac{\varphi(a_{n+1})}{{a_{n+1}}^2}$$, where $$\varphi(x)=-x^2+3x-1$$. But the roots of the quadratic polynomial $$\varphi(x)$$ are $$\dfrac{3\pm\sqrt5}2$$ and so, since $$a_{n+1}$$ is between them and the coefficient of $$x^2$$ in $$\varphi(x)$$ is negative, $$\varphi(a_{n+1})>0$$.

So, $$P(n+1)$$ is proved.

What I wrote above is an inductive proof of the fact that we always have $$P(n)$$. And it is very easy now to conclude that $$\lim_{n\to\infty}a_n=\dfrac{3+\sqrt5}2$$.

• Great explanation thank you – Olly Reynolds Apr 20 at 11:54