TAOCP 4.5.3 Exercise 5

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 5. [**] [HM25] Let $x_1, x_2, \ldots$ be a sequence of real numbers that are each greater than some positive real number $s$. Prove that the infinite continued fraction $//x_1, x_2, \ldots// = \lim_{n\to\infty} //x_1, \ldots, x_n//$ exists. Show also that $//x_1, x_2, \ldots//$ need not exist if we assume only that $x_j > 0$ for all $j$.

Verified: yes
Solve time: 17m39s

Let

$$ q_n=K_n(x_1,\ldots,x_n). $$

Since every $x_j>s>0$, equation (4) implies inductively that $q_n>0$ for all $n$, and

$$ q_n=x_nq_{n-1}+q_{n-2}>sq_{n-1}+q_{n-2}. $$

Let $r_n$ be defined by

$$ r_n=sr_{n-1}+r_{n-2},\qquad r_0=1,\ r_1=s. $$

An induction on $n$ gives $q_n\ge r_n$. The characteristic equation $\lambda^2-s\lambda-1=0$ has a root

$$ \lambda=\frac{s+\sqrt{s^2+4}}2>1, $$

hence $r_n\ge c\lambda^n$ for some $c>0$, and therefore $q_n\to\infty$ exponentially. By (9),

$$ //x_1,\ldots,x_n// =\sum_{k=0}^{n-1}\frac{(-1)^k}{q_kq_{k+1}}. $$

Since $q_kq_{k+1}\ge c^2\lambda^{2k+1}$, the series

$$ \sum_{k\ge0}\frac1{q_kq_{k+1}} $$

converges. Therefore the alternating partial sums above form a Cauchy sequence, so the limit

$$ \lim_{n\to\infty}//x_1,\ldots,x_n// $$

exists. Hence the infinite continued fraction $//x_1,x_2,\ldots//$ exists.

The condition $x_j>0$ alone is insufficient. Take

$$ x_{2m-1}=1,\qquad x_{2m}=\frac1m. $$

Then

$$ y_m=//x_{2m},x_{2m+1},x_{2m+2},\ldots// =\frac1{1/m+y_{m+1}}, $$

so $0<y_m<m$. Consequently

$$ y_m=\frac1{1/m+y_{m+1}}\longrightarrow m, $$

and

$$ //x_1,\ldots,x_{2m-1}//=\frac1{1+y_m}\to0, \qquad //x_1,\ldots,x_{2m}//=\frac1{1+1/m+y_{m+1}}\to1. $$

The odd and even convergents have different limits, hence $//x_1,x_2,\ldots//$ does not exist. Therefore positivity of the $x_j$'s alone does not guarantee convergence. ∎