Month: October 2008

Continued fractions: The basics


Let x_0, \displaystyle x_1, \displaystyle x_2, \displaystyle \ldots be variables. We define two sequences of polynomials with complex coefficients \displaystyle \{p_n\}_{n\geq 0} and \displaystyle \{q_n\}_{n\geq 0} by conditions following:

(1) For all non negative integer \displaystyle n, \displaystyle p_n and \displaystyle q_n are polynomials in \displaystyle x_0,x_1,\ldots,x_n.

(2) \displaystyle p_0=x_0 and \displaystyle q_0=1.

(3) For all positive integer \displaystyle n, \displaystyle p_n=x_0p_{n-1}(x_1,x_2,\ldots,x_n)+q_{n-1}(x_1,x_2,\ldots,x_n) and

\displaystyle q_n=p_{n-1}(x_1,x_2,\ldots,x_n).

Example. We have

\displaystyle p_1=x_0x_1+1 and \displaystyle q_1=x_1, therefore \displaystyle \frac{p_1}{q_1}=x_0+\frac{1}{x_1}.

\displaystyle p_2=x_0x_1x_2+x_0+x_2 and \displaystyle q_2=x_1x_2+1, hence

\displaystyle \frac{p_2}{q_2}=x_0+\frac{x_2}{x_1x_2+1}=x_0+\cfrac{1}{x_1+\cfrac{1}{x_2}}. \Box

For all non negative integer \displaystyle n we have

\displaystyle [x_0;x_1,x_2,\ldots,x_n]:=\frac{p_n}{q_n}=x_0+\cfrac{1}{x_1+\cfrac{1}{x_2+\cfrac{1}{x_3+\cdots+\cfrac{1}{x_{n-1}+\cfrac{1}{x_n}}}}}.

A rational function of this form is called a continued fraction.

Proposition 1. For all \displaystyle n>1, we have \displaystyle p_n=x_np_{n-1}+p_{n-2} and \displaystyle q_n=x_nq_{n-1}+q_{n-2}.

Proof. We use induction on \displaystyle n. From the above example we have the assertion is true for \displaystyle n=2. Now suppose that the assertion has been established for \displaystyle n-1 (\displaystyle n>2). Then we have

\displaystyle p_{n-1}(x_1,x_2,\ldots,x_n)=x_np_{n-2}(x_1,x_2,\ldots,x_{n-1})+p_{n-3}(x_1,x_2,\ldots,x_{n-2})

and

\displaystyle q_{n-1}(x_1,x_2,\ldots,x_n)=x_nq_{n-2}(x_1,x_2,\ldots,x_{n-1})+q_{n-3}(x_1,x_2,\ldots,x_{n-2}).

Therefore by define of \displaystyle \{p_n\} and \displaystyle \{q_n\},

\displaystyle p_n=x_0p_{n-1}(x_1,x_2,\ldots,x_n)+q_{n-1}(x_1,x_2,\ldots,x_n)=x_np_{n-1}+p_{n-2},

and \displaystyle q_n=x_nq_{n-1}+q_{n-2}. Thus the assertion is true for \displaystyle n. \Box

For convenience, we define \displaystyle p_{-2}=0, \displaystyle p_{-1}=1, \displaystyle q_{-2}=1, and \displaystyle q_{-1}=0.

Proposition 2. For all \displaystyle n>-2, we have \displaystyle p_nq_{n-1}-q_np_{n-1}=(-1)^{n-1}.

Proof. We prove by induction on \displaystyle n. The case \displaystyle n=-1 is trivial. Now suppose that the assertion is true for \displaystyle n-1 (\displaystyle n\geq 0). Then by proposition 1, we have

\displaystyle p_nq_{n-1}-q_np_{n-1}=(x_np_{n-1}+p_{n-2})q_{n-1}-(x_nq_{n-1}+q_{n-2})p_{n-1}

=-(p_{n-1}q_{n-2}-q_{n-1}p_{n-2})=(-1)^{n-1}.

Therefore the assertion is true for \displaystyle n-1. \Box

Proposition 3. For all \displaystyle n>-1, we have \displaystyle p_nq_{n-2}-q_np_{n-2}=(-1)^nx_n.

Proof. Assume \displaystyle n>-1 is an integer number. By propositions 1 and 2, we have

\displaystyle p_nq_{n-2}-q_np_{n-2}=(x_np_{n-1}+p_{n-2})q_{n-2}-(x_nq_{n-1}+q_{n-2})p_{n-2} =x_n(p_{n-1}q_{n-2}-q_{n-1}p_{n-2})=(-1)^nx_n. \Box

Proposition 4. If \displaystyle n\geq 0 and \displaystyle \theta:=[x_0;x_1,x_2,\ldots,x_{n+1}] then \displaystyle p_n-\theta q_n=\frac{(-1)^{n-1}}{q_{n+1}}.

Proof. By proposition 2, we have

\displaystyle p_n-\theta q_n=p_n-\frac{p_{n+1}}{q_{n+1}}\cdot q_n=\frac{-(p_{n+1}q_n-q_{n+1}p_n)}{q_{n+1}}=\frac{(-1)^{n-1}}{q_{n+1}}. \Box