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?

Question

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?

Answer 1

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$.

Answer 2

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}}$.

Answer 3

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

Answer 4

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$.

Answer 5

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$.

Answer 6

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\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}