# Let $\{a_n\}$ be defined as follows: $a_1 = 2$, $a_{n+1}=\frac{1}{3-a_n}$, if $n \geq 1$. Does $\{a_n\}$ converge?

Let $\{a_n\}$ be defined as follows: $$a_1 = 2, a_{n+1}=\dfrac{1}{3-a_n}$$ $n \geq 1$.

Does $\{a_n\}$ converge?

Using the monotone convergence thereom, if the sequence is both bounded below and decreasing, $\forall n\in\mathbb{N}, n\geq 1$, then we can say the sequence converges.

I'm having trouble proving that the sequence is bounded below by induction.

Claim: The sequence is bounded below by $0$.

Base Case:

$n=1$

$a_1 = 2 \geq 0$, so this holds.

Induction Step

Suppose that $a_k \geq 0$, for some $k \in\mathbb{N}$. (IH)

Prove $a_k \geq 0\to a_{k+1} \geq 0$

I have some difficulty here.

$a_{k}=\dfrac{1}{3-a_{k-1}} \geq 0$

$a_{k+1}=\dfrac{1}{3-a_{k}}$, but we know $a_k \geq 0$, but we don't know how much bigger. It could be that $a_k = 4$, and then I have $a_{k+1}=\dfrac{1}{3-4}$, which is negative, and does not confirm with my claim of being bounded below by $0$. Have I gone somewhere wrong in my induction?

• If you can prove that it's decreasing, then you know that $a_n\leq2$, which in turn implies $a_{n+1}\geq1$. Now it just remains to see whether it actually is decreasing. – Arthur Mar 15 '17 at 19:22
• It took the first few terms and say that it was, but how can I fix the flaw in the induction? – K Split X Mar 15 '17 at 19:31
• @Arthur don't you mean it implies $a_{n + 1} \leq 1$? – Pratyush Sarkar Mar 15 '17 at 19:33
• If the given sequence admits a limit, the limit must satisfy $l=\frac1{3-l}$, this gives two solutions $l_1,l_2$, then set $b_n=\frac{a_n-l_1}{a_n-l_2}$, then observe that the sequence $\left\{b_n\right\}$ is a geometric sequence. this is a general route appropriate to homographic recurrences. – Olivier Oloa Mar 15 '17 at 19:42
• @OlivierOloa: nice insight (I just skipped to the final closed form) and that approach is clearly outlined in many answers on MSE, but I cannot seem to find them. Would you mind giving me a hand in adding an appropriate reference? – Jack D'Aurizio Mar 15 '17 at 19:52

Claim:

$$a_n \geq \frac{3-\sqrt{5}}{2}$$

Since $\sqrt{5} \geq 1$, we have $\sqrt{5} \geq 3-2$, $2 \geq 3-\sqrt{5}$ and hence

$$a_1=1 \geq \frac{3-\sqrt{5}}{2}$$

Suppose that we have $a_k \geq \frac{3-\sqrt{5}}{2}$,

$$3-a_k \leq 3-\frac{3-\sqrt{5}}{2}=\frac{3+\sqrt{5}}{2}$$

Assuming that you have the proof that $a_k$ is decreasing, then we know that $3-a_k >0$,

$$a_{k+1}=\frac{1}{3-a_k}\geq \frac{2}{3+\sqrt{5}}=\frac{2(3-\sqrt{5})}{9-5}=\frac{3-\sqrt{5}}{2}$$

Remark: the sequence is not bounded below by $1$. In particular, $a_3=\frac12$.

• Yes I changed it to $0$ – K Split X Mar 15 '17 at 19:43
• We started from $a_1=2$, if we can prove that it is decreasing, then $a_k \leq 2$. $3-a_k>0$. – Siong Thye Goh Mar 15 '17 at 19:47
• How does $a_k \leq 2$ imply $3-a_k > 0$? – K Split X Mar 15 '17 at 19:48
• $a_k \leq 2$ implies $-a_k \geq -2$ which implies $3-a_k \geq 1$ – Siong Thye Goh Mar 15 '17 at 19:49
• Okay I see that. Can I instead prove $a_n \geq 0$, instead of the ratio you have above? – K Split X Mar 15 '17 at 19:51

This is quite an overkill, but since a solution of $x=\frac{1}{3-x}$ is given by the squared golden ratio, one might wonder about Fibonacci numbers being involved. A reasonable conjecture is

$$a_n = \frac{F_{2n-5}}{F_{2n-3}}$$ and that is straightforward to prove by induction, making the whole question trivial: the given sequence is decreasing and converging to $\frac{2}{3+\sqrt{5}}$.

• Yeah unforunately it is an overkill Dx – K Split X Mar 15 '17 at 19:38
• I agree fib is involved in this but I don't know I'm supposed to think of it in that way – K Split X Mar 15 '17 at 19:42
• I hope you are supposed to think in any way you like! – Jack D'Aurizio Mar 15 '17 at 19:43
• For a general approach to such problems, have a look at en.wikipedia.org/wiki/Rational_difference_equation (thanks to Olivier Oloa). – Jack D'Aurizio Mar 15 '17 at 20:08

The Moebius transform $$T(z):={1\over3-z}$$ has the two fixed points $z_1={1\over2}(3+\sqrt{5})$ and $z_2={1\over2}(3-\sqrt{5})$. One computes $$T'(z)={1\over(3-z)^2}\ ,$$ so that $$T'(z_1)=\left({3+\sqrt{5}\over2}\right)^2\doteq6.85\ ,\qquad T'(z_2)=\left({3-\sqrt{5}\over2}\right)^2\doteq0.146\ .$$ The general theory of these transforms then guarantees that any recursive sequence $a_{n+1}=T(a_n)$ with $a_0\ne z_1$ converges to $z_2$, the reason being that the given $T$ is conjugate to $\hat T:\> w\mapsto \lambda w$ with $\lambda\doteq0.146$.

Try to prove that a_n is monotone decreasing and bound from below by 1/3.

Let $\alpha$ and $\beta$ be the zero of $x^2-3x+1=0$, with $\alpha<\beta$, i.e. $$\alpha=\dfrac{3-\sqrt{5}}{2}\approx0.381966,\quad \beta=\dfrac{3+\sqrt{5}}{2}\approx 2.618033$$ Claim 1: We have $\alpha<a_k<\beta$ for all $k$.

Proof:

Consider the function $$f:[0,3) \to \left[\dfrac13,\infty\right),\quad f(x)=\dfrac{1}{3-x}$$ It is clear that $f$ is continuous and increasing. Furthermore, $\alpha$ and $\beta$ are the only number satisfying $f(x)=x$. Therefore $f([\alpha,\beta])=[\alpha,\beta]$

We have \begin{eqnarray} a_1&=&2 \in [\alpha,\beta]\\ a_2&=&\dfrac{1}{3-2}=1\in [\alpha,\beta]\\ a_3&=&\dfrac{1}{3-1}=\dfrac12 \in [\alpha,\beta]\\ a_4&=&\dfrac{2}{5} \in [\alpha,\beta] \end{eqnarray} If we assume that $a_k \in [\alpha,\beta]$ for $k\le 4$, then $$a_{k+1}=f(a_k) \in [\alpha,\beta]$$ Hence $a_k\in (\alpha,\beta)$ for all $k$ because $a_k\ne \alpha,\beta$ for all $k$.

Claim 2: We have $a_{k+1}<a_k$ for all $k$.

Proof:

Since $0<\alpha<\beta<3$, for all $x\in (\alpha,\beta)$ we have $$x-f(x)=x-\dfrac{1}{3-x}=\dfrac{x^2-3x+1}{x-3}=\dfrac{(x-\alpha)(x-\beta)}{x-3}>0,$$ i.e. $$f(x)<x \quad \forall x\in (\alpha,\beta)$$ therefore, for all $k$ we have $$a_{k+1}=f(a_k)<a_k \quad \forall k$$

Claim 3: $\lim_ka_k=\alpha$.

Proof:

Since $a_k$ is decreasing and bounded below, there it is convergent, and its limit $l$ satisfies the equation $f(l)=l$, i.e. $l^2-3l+1=0$. Hence $l\in\{\alpha,\beta\}$. It follows $l=\alpha$ because $a_k\le 2<\beta$.

$\newcommand{\bbx}{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}{\mathcal{#1}} \newcommand{\mrm}{\mathrm{#1}} \newcommand{\pars}{\left(\,{#1}\,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}{\left\vert\,{#1}\,\right\vert}$ Write $\ds{a_{n} = p_{n}/q_{n}}$ with $\ds{p_{n + 1} = q_{n}}$ and $\ds{q_{n + 1} = 3q_{n} - p_{n}}$ which leads to $\pars{~\mbox{choose, for example,}\ p_{1} = 2\ \mbox{and}\ q_{1} = 1~}$: \begin{align} {p_{n + 1} \choose q_{n + 1}} & = \pars{\begin{array}{cc}\ds{0} & \ds{1} \\ \ds{-1} & \ds{3}\end{array}}{p_{n} \choose q_{n}} = \pars{\begin{array}{cc}\ds{0} & \ds{1} \\ \ds{-1} & \ds{3}\end{array}}^{n}{p_{1} \choose q_{1}} \,\,\,\stackrel{\mrm{as}\ n\ \to\ \infty}{\sim}\,\,\, \lambda^{n}\,\mathbf{u}\mathbf{u}^{\mrm{T}}{2 \choose 1} = \bracks{\lambda^{n}\mathbf{u}^{\mrm{T}}{2 \choose 1}}\mathbf{u} \end{align} where $\ds{\lambda}$ is the the largest magnitude eigenvalue and $\ds{\mathbf{u}}$ is the correspondent normalized eigenvector of the above matrix. It turns out that $\ds{\mathbf{u} = {a \choose 1}/\root{a^{2} + 1}}$ where $\ds{a \equiv \pars{3 - \root{5}}/2}$.

Then, \begin{align} a_{n} & \,\,\,\stackrel{\mrm{as}\ n\ \to\ \infty}{=}\,\,\, {\pars{1 \quad 0}\mathbf{u} \over \pars{0 \quad 1}\mathbf{u}} = {a \over 1} = \bbx{\ds{3 - \root{5} \over 2}} \end{align}