# 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!

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! – James O'dare Apr 20 '19 at 11:54
• No problem, you're welcome. – 0XLR Apr 20 '19 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 – James O'dare Apr 20 '19 at 11:54