1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Arthur Mar 15 '17 at 19:22
  • $\begingroup$ It took the first few terms and say that it was, but how can I fix the flaw in the induction? $\endgroup$ – K Split X Mar 15 '17 at 19:31
  • 1
    $\begingroup$ @Arthur don't you mean it implies $a_{n + 1} \leq 1$? $\endgroup$ – Pratyush Sarkar Mar 15 '17 at 19:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Olivier Oloa Mar 15 '17 at 19:42
  • 1
    $\begingroup$ @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? $\endgroup$ – Jack D'Aurizio Mar 15 '17 at 19:52
3
$\begingroup$

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

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

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

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.