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$

M	T	W	T	F	S	S
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Continued fractions: The basics

Published by Random

One thought on “Continued fractions: The basics”

Leave a comment Cancel reply

Share this:

Related

Published by Random

One thought on “Continued fractions: The basics”

Leave a comment Cancel reply