# 3. Show convergence of infinite simple continued fractions.

Show the convergence of the infinite simple continued fraction in Problem 2, representing the recurrence relation ${a_n=a_{n-1}+a_{n-2}}$.

Let ${\dfrac{p_ {n}}{q_{n}}}$ be the fraction represented by the ${n}$th term in the continued fraction. Thus ${\dfrac{p_ {2n}}{q_{2n}}}$ are the even convergents; ${\dfrac{p_ {2n+1}}{q_{2n+1}}}$ are the odd convergents; both ${p_n}$ and ${q_n}$ satisfy the recurrence relation.

One needs to show that ${\dfrac{p_{2n}}{q_{2n}}}$ is bounded and monotonic increasing and ${\dfrac{p_{2n+1}}{q_{2n+1}}}$ is bounded and monotonic decreasing, and that these two subsequences converge to the same limit.

A formula for the difference of convergents will help:

${\dfrac{p_n}{q_n}-\dfrac{p_{n-1}}{q_{n-1}}=\dfrac{p_nq_{n-1}-p_{n-1}{q_n}}{q_nq_{n-1}}}$.

Expanding the numerator on the right side by substitution from the recurrence relation,

${p_nq_{n-1}-p_{n-1}q_n=(p_{n-1}+p_{n-2})q_{n-1}-p_{n-1}(q_{n-1}+q_{n-2})=-(p_{n-1}q_{n-2}-p_{n-2}q_{n-1})}$.

Repeat the substitution on the right until the result is in terms of the sequence initial constants:

${p_nq_{n-1}-p_{n-1}q_n=(-1)^{n-1}(p_1q_0-p_0q_1)=(-1)^{n-1}}$.

Thus, ${\dfrac{p_n}{q_n}-\dfrac{p_{n-1}}{q_{n-1}}=\dfrac{(-1)^{n-1}}{q_nq_{n-1}}}$.

Similarly, ${\dfrac{p_n}{q_n}-\dfrac{p_{n-2}}{q_{n-2}}=\dfrac{(-1)^{n-1}}{q_nq_{n-2}}}$.

Since ${q_n>0}$, ${\dfrac{p_{2n}}{q_{2n}}-\dfrac{p_{2n-2}}{q_{2n-2}}>0}$ and ${\dfrac{p_ {2n}}{q_{2n}}}$ is monotonic increasing.

Similarly ${\dfrac{p_{2n+1}}{q_{2n+1}}-\dfrac{p_{2n-1}}{q_{2n-1}}<0}$ and ${\dfrac{p_ {2n+1}}{q_{2n+1}}}$ is monotonic decreasing.

Both subsequences are bounded, for ${\dfrac{p_ {2n}}{q_{2n}} < 2}$ and ${\dfrac{p_ {2n+1}}{q_{2n+1}}>1}$.

Thus it remains to show that both subsequences converge to the same limit, by showing the difference between the sequences tends to ${0}$ for large ${n}$. Observing that ${q_n>n}$ when ${n>3}$:

${\left| \dfrac{p_{2n}}{q_{2n}}-\dfrac{p_{2n-1}}{q_{2n-1}} \right|=\dfrac{1}{q_{2n}q_{2n-1}}\le \dfrac{1}{2n(2n-1)}\rightarrow 0}$.