Connected graph

Một đồ thị (xem lại [2]) khác rỗng $G$ được gọi là liên thông nếu mỗi hai đỉnh của nó được nối với nhau bởi một đường đi (xem lại [3]).

Định lý 1. Các đỉnh của một đồ thị liên thông $G$ có thể đánh số $v_1$ , $v_2$ , $\ldots$ , $v_n$ sao cho $G_i:=G[v_1,v_2,\ldots,v_i]$ là đồ thị liên thông với mọi $i$ .

Chứng minh. Lấy một đỉnh $v_1$ , và giả sử đã đánh số được các đỉnh $v_1$ , $v_2$ , $\ldots$ , $v_i$ thỏa mãn tính chất trong định lý, ở đây $i<\mid G\mid.$ Giả sử $v$ là một đỉnh khác tất cả các đỉnh đã được đánh số. Vì $G$ là đồ thị liên thông nên tồn tại đường đi $P$ nối $v$ với $v_1$ . Chọn $v_{i+1}$ là đỉnh cuối của $P$ mà không thuộc $G_i$ , khi đó $v_{i+1}$ có một láng giềng trong $G_i$ và $G_{i+1}$ liên thông. $\Box$

Hệ quả. Một đồ thị liên thông trên $n$ đỉnh sẽ có ít nhất $n-1$ cạnh.

Chứng minh. Quy nạp theo $n$ và dùng định lý 1. Bạn đọc tự chứng minh xem như một bài tập. $\Box$

Cho đồ thị $G=G(V,E)$ . Một đồ thị con liên thông cực đại (cực đại theo nghĩa không có đồ thị con liên thông chứa và khác nó, xem lại [2]) của $G$ được gọi là thành phần liên thông của $G$ . Đương nhiên, các thành phần liên thông là các đồ thị con cảm sinh (xem lại [2]) của $G$ , và tập các đỉnh của chúng lập thành một phân hoạch của $V$ . Một đồ thị là liên thông nếu và chỉ nếu nó có đúng một thành phần liên thông.

Ví dụ 1. Cho $G$ là một đồ thị với $m$ cạnh và $p$ thành phần liên thông. Chứng minh rằng $m+p\geq \mid G\mid$ .

Lời giải. Gọi $n_i$ là số đỉnh của thành phần liên thông thứ $i$ . Khi đó số cạnh của thành phần liên thông thứ $i$ không bé hơn $n_i-1$ , do đó

$m\geq \sum (n_i-1)=-p+\sum n_i=\mid G\mid -p,$

và bài toán được giải. $\Box$

Ví dụ 2. Cho $G$ là một đồ thị con không liên thông của $K_n$ . Chứng minh rằng $\overline{G}$ là một đồ thị con liên thông của $K_n$ .

Lời giải. Gọi $G^{\prime}$ là một thành phần liên thông của $G$ . Vì $G$ không liên thông nên $G\setminus G^{\prime}$ khác rỗng. Do tính cực đại của thành phần liên thông, không có cạnh nào của $G$ nối một đỉnh của $G^{\prime}$ với một đỉnh của $G\setminus G^{\prime}$ . Suy ra trong $\overline{G}$ , mỗi đỉnh của $G^{\prime}$ sẽ nối với mỗi đỉnh của $G\setminus G^{\prime}$ .

Vậy muốn chứng minh $\overline{G}$ liên thông, ta chỉ cần chứng minh hai đỉnh cùng thuộc $G^{\prime}$ hoặc $G\setminus G^{\prime}$ được nối với nhau. Nếu hai đỉnh cùng thuộc $G^{\prime}$ thì ta nối chúng với nhau qua một đỉnh của $G\setminus G^{\prime}$ , và ngược lại. $\Box$

Cho số tự nhiên $k$ . Một đồ thị $G=(V,E)$ được gọi là $k-$liên thông nếu $k<\mid G\mid$ và $G\setminus X$ vẫn là đồ thị liên thông với mọi $X\subset V$ mà $\mid X\mid<k$ . Số $k$ lớn nhất sao cho $G$ là $k-$ liên thông được gọi là chỉ số liên thông của $G$ , ký hiệu $k(G)$ .

Ví dụ 3. $k(K_n)=n-1$ với mỗi số nguyên dương $n$ .

Lời giải. Bạn đọc tự giải xem như bài tập. $\Box$

Định lý 2 (Whitney, 1932). Cho đồ thị $G=(V,E)$ với $\mid G\mid\geq 3$ . Khi đó $G$ là $2-$ liên thông khi và chỉ khi với hai đỉnh phân biệt bất kỳ của $G$ , tồn tại hai đường đi rời nhau nối chúng (hai đường đi được gọi là rời nhau nếu chúng không có đỉnh trong chung).

Chứng minh. Khẳng định đúng hiển nhiên khi $\mid G\mid =3$ . Bây giờ ta xét $\mid G\mid >3$ . Đầu tiên, giả sử với hai đỉnh phân biệt bất kỳ của $G$ tồn tại hai đường đi rời nhau nối chúng. Gọi $w$ là một đỉnh bất kỳ và $u,v$ là hai đỉnh khác nhau của $G\setminus\{w\}$ . Giữa $u$ và $v$ sẽ có hai đường đi rời nhau nối chúng, $w$ sẽ không thuộc một trong hai đường này, ký hiệu $P$ . Ta có $P$ là một đường trong $G\setminus\{w\}$ nối $u$ và $v$ . Suy ra $G\setminus\{w\}$ liên thông, do đó $G$ là $2-$ liên thông.

Bây giờ giả sử $G$ là $2-$ liên thông và tồn tại hai đỉnh phân biệt $u$ và $v$ mà không có hai đường đi rời nhau. Vì $\mid G\mid >3$ nên tồn tại ít nhất hai đường đi nối $u$ và $v$ . Gọi $P$ và $Q$ là hai đường đi nối $u$ và $v$ mà có tập đỉnh chung $S$ có ít phần tử nhất có thể. Lấy $w\in S\setminus \{u,v\}$ và $P_1$ , $P_2$ là phần của $P$ từ $u$ đến $w$ , $w$ đến $v$ . Tương tự ta định nghĩa $Q_1$ và $Q_2$ .

Vì $G$ là $2-$ liên thông, ta có thể lấy một đường đi $R$ ngắn nhất từ một đỉnh $x$ thuộc $(P_1\cup Q_1)\setminus \{w\}$ đến một đỉnh $y$ thuộc $(P_2\cup Q_2)\setminus \{w\}$ mà không qua $w$ . Giả sử mà không làm mất tính tổng quát rằng $x\in P_1$ và $y\in Q_2$ . Gọi $T$ là đường đi nối $u$ với $v$ được hình thành bởi phần $P_1$ nối $u$ với $x$ , và phần $Q_2$ nối $y$ với $v$ , cùng với $R$ . Do cách chọn $R$ , hai đường đi $T$ và $Q_1\cup P_2$ cùng nối $u$ với $v$ nhưng có tập các đỉnh chung là tập con của $S\setminus \{w\}$ , vô lý. $\Box$

Cho một đồ thị $G$ . Đường đi $P$ (không nhất thiết trong $G$ ) được gọi là $G-$ đường nếu $\mid P\mid >1$ và $P\cap G$ chỉ chứa hai đầu mút của $P$ . Kết quả sau cho ta biết cấu trúc của các đồ thị $2-$ liên thông.

Định lý 3. Một đồ thị là $2-$ liên thông khi và chỉ khi nó có thể được dựng từ một chu trình bằng cách bổ sung liên tiếp các $H-$ đường vào các đồ thị $H$ đã được dựng.

Tài liệu tham khảo

[1] https://nttuan.org/2009/08/13/graph01/

[2] https://nttuan.org/2023/09/01/graph02/

[3] https://nttuan.org/2024/06/04/graph03/

Finite Unions of Proper Subspaces Over an Infinite Field

A vector space over an infinite field cannot be the union of finitely many proper subspaces.

Proof. Assume for the sake of contradiction that $V$ is a vector space over an infinite field $\mathbb{F}$ and $V = \bigcup_{i=1}^n W_i$ , where $n$ is the smallest positive integer satisfying this property and the $W_i$ are proper subspaces of $V$ .
Since $V$ cannot be a proper subspace of itself, $n$ must be greater than or equal to $2$ . Since $n$ is minimal, $W_n$ is not contained in the union of the remaining subspaces. Thus there exists a vector $u \in W_n$ such that $u \notin W_i$ for all $i < n$ . On the other hand, since $W_n$ is a proper subspace of $V$ , there exists a vector $v \notin W_n$ .
Consider the infinite set of vectors of the form $v + c u$ with $c \in \mathbb{F}$ . Since $V$ is the union of $n$ subspaces and the field $\mathbb{F}$ has infinitely many elements, by the pigeonhole principle there exists a subspace $W_k$ containing at least two distinct vectors from the considered set. Suppose $v + c_1 u \in W_k$ and $v + c_2 u \in W_k$ with $c_1, c_2 \in \mathbb{F}$ and $c_1 \neq c_2$ . Then the difference of these two vectors is $(c_1 - c_2) u \in W_k$ . Since $c_1 \neq c_2$ , the scalar $c_1 - c_2$ is non-zero, hence we have $u \in W_k$ . If $k = n$ , then from $v + c_1 u \in W_n$ and $u \in W_n$ we deduce that $v \in W_n$ , which contradicts the choice of $v$ . If $k < n$ , then $u \in W_k$ , which contradicts the choice of $u$ . All cases lead to a contradiction. Therefore, a vector space over an infinite field cannot be the union of finitely many proper subspaces. $\Box$

Continued fraction expansion of irrational numbers

In this section we use continued fractions for expansion of irrational numbers.

Theorem 1. Let $\displaystyle (x_n)_{n\geq 0}$ be a sequence of intergers with $\displaystyle x_i>0$ for every $\displaystyle i>0$ . Then the sequence $\displaystyle (p_n/q_n)_{n\geq 0}$ is a convergent sequence, and the its limit is an irrational number. We denote this limit by $\displaystyle [x_0;x_1,x_2,\ldots]$ .

Proof. From [1] we have $\displaystyle q_1\geq q_0=1>0$ and for all $\displaystyle n>1$ , $\displaystyle q_n=x_nq_{n-1}+q_{n-2},$ hence by induction on $\displaystyle n$ , $\displaystyle q_{n+1}>q_n$ for every $\displaystyle n\geq 1$ . Therefore $\displaystyle\lim_{n\to \infty}q_n=\infty$ .

By the Proposition 4 in [1], for all $\displaystyle n\geq 0$ ,

$\displaystyle \frac{p_n}{q_n}-\frac{p_{n+1}}{q_{n+1}}=\frac{(-1)^{n-1}}{q_nq_{n+1}},\quad\quad (1)$

hence $\displaystyle \frac{p_n}{q_n}-\frac{p_{n+2}}{q_{n+2}}=\frac{(-1)^{n-1}(q_{n+2}-q_n)}{q_nq_{n+1}q_{n+2}},\quad \forall n\geq 0.$ Therefore

$\displaystyle \frac{p_1}{q_1}>\frac{p_3}{q_3}>\frac{p_5}{q_5}>\ldots>\frac{p_0}{q_0}$

and

$\displaystyle \frac{p_0}{q_0}<\frac{p_2}{q_2}<\frac{p_4}{q_4}<\ldots<\frac{p_1}{q_1},$

hence $\displaystyle (p_{2n}/q_{2n})_{n\geq 0}$ and $\displaystyle (p_{2n+1}/q_{2n+1})_{n\geq 0}$ are convergent sequences. By (1) and $\displaystyle q_n\to\infty$ we have

$\displaystyle\lim_{n\to\infty}\frac{p_{2n}}{q_{2n}}=\lim_{n\to\infty}\frac{p_{2n+1}}{q_{2n+1}},$ so $\displaystyle (p_n/q_n)_{n\geq 0}$ is a convergent sequence.

Now we prove $\displaystyle \displaystyle \alpha:=\lim_{n\to\infty}\frac{p_n}{q_n}$ is an irrational number. We have

$\displaystyle \frac{p_{2m}}{q_{2m}}<\alpha<\frac{p_{2n+1}}{q_{2n+1}},\quad\forall m,n\geq 0.$

Thus, by (1),

$\displaystyle\left|\alpha-\frac{p_{2n}}{q_{2n}}\right|\leq \frac{1}{q_{2n}q_{2n+1}}<\frac{1}{q_{2n}^2},\quad\forall n\geq 1.$

By the Proposition 2 in [1], $\displaystyle p_{2n}$ and $\displaystyle q_{2n}$ are coprime integers for every $\displaystyle n\geq 1$ , hence there are infinite rational numbers $\displaystyle r/s$ , with $\displaystyle s>0$ and $\displaystyle (r,s)=1$ , such that

$\displaystyle \left|\alpha-\frac{r}{s}\right| <\frac{1}{s^2}.\quad\quad (2)$

Assume that $\displaystyle \alpha$ is rational and write $\displaystyle \alpha=p/q$ , where $\displaystyle p$ and $\displaystyle q>0$ are coprime integers. For all positive integers $\displaystyle s$ , at most two integers $\displaystyle r$ satisfy the equation (2), hence there are coprime integers $\displaystyle r_0$ and $\displaystyle s_0>q$ such that

$\displaystyle\left|\frac{p}{q}-\frac{r_0}{s_0}\right| <\frac{1}{s_0^2}.$

From the inequality we have $\displaystyle \mid ps_0-qr_0\mid <1$ , hence $\displaystyle ps_0=qr_0$ , a contradiction. Therefore $\displaystyle \alpha$ is an irrational number. $\Box$

Theorem 2. Let $\displaystyle \alpha$ be an irrational number. Then there is a unique sequence of integers $\displaystyle (a_n)_{n\geq 0}$ such that

(1) $\displaystyle a_i>0$ for every $\displaystyle i>0$ .

(2) $\displaystyle \alpha =[a_0;a_1,a_2,\ldots]$ .

Proof. In this proof, $\displaystyle [x]$ is the integer part of $\displaystyle x$ . Because $\displaystyle \alpha$ is an irrational number, we have $\displaystyle [\alpha]<\alpha<[\alpha]+1$ , hence there is a real number $\displaystyle u_1>1$ such that

$\displaystyle \alpha=[\alpha]+\frac{1}{u_1}.$

Because $\displaystyle \alpha$ is an irrational and $\displaystyle [\alpha]$ is an integer, $\displaystyle u_1$ is an irrational number. Hence there is an irrational number $\displaystyle u_2>1$ such that

$\displaystyle u_1=[u_1]+\frac{1}{u_2},$

and so on. Therefore we have real numbers $\displaystyle u_0:=\alpha$ , $u_1>1$ , $\displaystyle u_2>1$ , $\displaystyle \ldots$ such that $\displaystyle u_i$ is irrationals for every $\displaystyle i>0$ and

$\displaystyle u_k=[u_k]+\frac{1}{u_{k+1}},\quad\forall k\geq 0.$

We claim that $\displaystyle \alpha=[[u_0];[u_1],[u_2],\ldots]$ . Fix a $\displaystyle k>2$ . We have

$\displaystyle \alpha=[[u_0];[u_1],\ldots, [u_k],u_{k+1}].$

Hence, by Proposition 4 in [1],

$\displaystyle \left|\alpha-\frac{p_k}{q_k}\right|=\frac{1}{q_k(u_{k+1}q_{k}+q_{k-1})}<\frac{1}{q_k^2},$

so $\displaystyle \lim_{n\to\infty}\frac{p_n}{q_n}=\alpha$ . Now assume that

$\displaystyle \alpha =[a_0;a_1,a_2,\ldots]=[b_0;b_1,b_2,\ldots],$

where $\displaystyle (a_n)_{n\geq 0}$ and $\displaystyle (b_n)_{n\geq 0}$ are two sequences of integers such that $\displaystyle a_i>0$ and $\displaystyle b_i>0$ for every $\displaystyle i>0$ .

Because

$\displaystyle [a_0;a_1,a_2,\ldots,a_{n}]=a_0+\frac{1}{[a_1;a_2,\ldots,a_n]},\quad\forall n\geq 0,$

we have

$\displaystyle [a_0;a_1,a_2,\ldots]=a_0+\frac{1}{[a_1;a_2,\ldots]}.$

Hence $\displaystyle a_0=b_0=[\alpha]$ and $\displaystyle [a_1;a_2,a_3,\ldots] = [b_1;b_2,b_3,\ldots]$ . Similarly, $\displaystyle a_1=b_1$ and

$\displaystyle [a_2;a_3,a_4,\ldots] = [b_2;b_3,b_4,\ldots],$

and so on. Therefore $\displaystyle a_i=b_i$ for every $i$ . $\Box$

The equality in the theorem is called an expansion of $\displaystyle \alpha$ into a infinite continued fraction. In that expansion we will call $\displaystyle [a_0;a_1,a_2,\ldots,a_i]$ is the $\displaystyle i-$ th convergent of the continued fraction, or $\displaystyle i-$ th convergent of $\displaystyle \alpha$ . The theorem says that for every irrational number has an expansion into a infinite continued fraction, and this expansion is unique.

Example 1. $\displaystyle \sqrt{2}=[1;2,2,\ldots]$ .

Example 2. The golden ratio $\displaystyle\varphi:=\frac{1+\sqrt{5}}{2}=[1;1,1,\ldots]$ .

Example 3. $\displaystyle e=[2;1,2,1,1,4,1,1,6,1,1,8,\ldots]$ .

A sequence $\displaystyle (a_n)_{n\geq 0}$ is called eventually periodic if $\displaystyle a_{n+T}=a_n$ for some positive integer $\displaystyle T$ and sufficiently large $\displaystyle n$ . A real number is called quadratic irrational number, if there is a polynomial $\displaystyle P(x)$ is of degree two with rational coefficients such that $\displaystyle P(x)$ is an irreducible polynomial (see [3]) over the rational numbers and $\displaystyle \alpha$ is a root of $\displaystyle P(x)$ .

Theorem 3. Let $\displaystyle \alpha$ be an irrational number and $\displaystyle \alpha =[a_0;a_1,a_2,\ldots]$ is the expansion of $\displaystyle\alpha$ into a infinite continued fraction. Then $\displaystyle (a_n)_{n\geq 1}$ is eventually periodic if and only if $\displaystyle \alpha$ is a quadratic irrational.

References

[1] https://nttuan.org/2008/10/12/continued-fractions-the-basics/

[2] https://nttuan.org/2008/11/14/continued-fraction-expansion-of-rational-numbers/

[3] https://nttuan.org/2009/01/11/poly02/

Least upper bound property

Một tập $\displaystyle A \subset\mathbb{R}$ được gọi là bị chặn trên nếu tồn tại $\displaystyle b \in \mathbb{R}$ sao cho $\displaystyle a \leq b$ với mọi $\displaystyle a \in A$ . Số $\displaystyle b$ được gọi là một cận trên của $\displaystyle A$ . Tương tự, tập $\displaystyle A$ bị chặn dưới nếu tồn tại một cận dưới $\displaystyle l \in \mathbb{R}$ thỏa mãn $\displaystyle l \leq a$ với mọi $\displaystyle a \in A.$ Tập $\displaystyle A$ được gọi là bị chặn nếu nó bị chặn trên và bị chặn dưới.

Bài tập 1. Tìm một tập hợp $\displaystyle A$ các số thực sao cho:

(1) $\displaystyle A$ bị chặn trên.

(2) $\displaystyle A$ bị chặn dưới.

(3) $\displaystyle A$ không bị chặn trên và không bị chặn dưới. $\Box$

Định nghĩa 1. Một số thực $\displaystyle s$ được gọi là cận trên đúng của $\displaystyle A \subset \mathbb{R}$ nếu nó thỏa mãn đồng thời hai điều kiện:

(1) $\displaystyle s$ là một cận trên của $\displaystyle A$ .

(2) nếu $\displaystyle b$ là một cận trên của $\displaystyle A$ thì $\displaystyle s \leq b.$

Cận trên đúng cũng thường được gọi là supremum của tập $\displaystyle A$ , ký hiệu $\displaystyle \sup A$ . Cận dưới đúng hay infimum của $\displaystyle A$ được định nghĩa theo cách tương tự và được ký hiệu bởi $\displaystyle \inf A$ . Mặc dù một tập có thể có vô hạn cận trên, nhưng nó chỉ có tối đa một cận trên đúng.

Ví dụ 1. Cho tập hợp $\displaystyle A=\left\{\frac{1}{n}: n \in \mathbb{N}^*\right\}=\left\{1, \frac{1}{2}, \frac{1}{3}, \ldots\right\}.$

Tập $A$ bị chặn trên và dưới. Ta thấy $\sup A=1$ và $\inf A=0$ . $\Box$

Một bài học quan trọng rút ra từ ví dụ trên là $\displaystyle \sup A$ và $\displaystyle \inf A$ có thể thuộc hoặc không thuộc tập $\displaystyle A$ . Đây là điểm khác nhau cốt yếu giữa phần tử lớn nhất và cận trên đúng (hoặc phần tử nhỏ nhất và cận dưới đúng) của một tập số thực.

Định nghĩa 2. Một số thực $\displaystyle a_{0}$ được gọi là phần tử lớn nhất của tập $\displaystyle A$ , ký hiệu $\displaystyle \max A$ , nếu $\displaystyle a_{0}$ là một phần tử của $\displaystyle A$ và $\displaystyle a_{0} \geq a$ với mọi $\displaystyle a \in A$ . Tương tự, số $\displaystyle a_{1}$ là phần tử nhỏ nhất của $\displaystyle A$ , ký hiệu $\displaystyle \min A$ , nếu $\displaystyle a_{1} \in A$ và $\displaystyle a_{1} \leq a$ với mọi $\displaystyle a \in A.$

Ví dụ 2. Hai tập $\displaystyle [0;2]$ và $\displaystyle (0;2)$ bị chặn, có cùng cận trên đúng $\displaystyle 2$ , nhưng chỉ $\displaystyle [0;2]$ có phần tử lớn nhất. Như vậy, cận trên đúng có thể tồn tại và không phải là phần tử lớn nhất, nhưng khi phần tử lớn nhất tồn tại, nó cũng là cận trên đúng. $\Box$

Mặc dù ta có thể thấy rằng không phải mọi tập hợp khác rỗng bị chặn trên nào đều có phần tử lớn nhất, nhưng tiên đề về tính đầy đủ khẳng định rằng mọi tập hợp như vậy đều có một cận trên đúng. Ta sẽ không chứng minh điều này. Tiên đề trong toán học là một giả định được chấp nhận, được sử dụng mà không cần chứng minh.

Tiên đề về tính đầy đủ. Mọi tập các số thực khác rỗng và bị chặn trên đều có cận trên đúng.

Từ tiên đề trên ta có thể chứng minh mọi tập số thực khác rỗng và bị chặn dưới đều có cận dưới đúng. Tiên đề không đúng với tập các số hữu tỷ.

Ví dụ 3. Tập $\{r\in\mathbb{Q}\mid r^2<2\}$ bị chặn trên và khác rỗng nhưng không có cận trên đúng thuộc $\mathbb{Q}$ . $\Box$

Hai định lý sau cho một định nghĩa tương đương của cận trên đúng và cận dưới đúng.

Continue reading →

Continued fraction expansion of rational numbers

In this section we use continued fractions ([2]) for expansion of rational numbers. If $\displaystyle x_0$ , $\displaystyle x_1$ , $\displaystyle \ldots$ , are integer nunbers with $\displaystyle x_i>0$ for every $\displaystyle i>0$ then $\displaystyle [x_0;x_1,x_2,\ldots,x_n]\in\mathbb{Q},\quad\forall n\geq 0.$

Conversly, we have the theorem

Theorem 1. Let $\displaystyle r$ and $\displaystyle s$ be coprime integers with $\displaystyle s>0$ . Then there are non negative integer $\displaystyle n$ and integers $\displaystyle a_0$ , $\displaystyle a_1$ , $\displaystyle \ldots$ , $\displaystyle a_n$ such that

(1) $\displaystyle a_i>0$ for every $\displaystyle i=1,2,\ldots,n$ .

(2) $\displaystyle r/s=[a_0;a_1,a_2,\ldots,a_n]$ .

Proof. Let us proceed by induction on $\displaystyle s$ . The case $\displaystyle s=1$ is trivial. Now suppose that the assertion is true for all positive integers up to $\displaystyle s-1$ ( $\displaystyle s>1$ ). Because $\displaystyle (r,s)=1$ and $\displaystyle s>1$ , we have $\displaystyle s\nmid r$ . Hence by the Division Algorithm ([1]), there are integers $\displaystyle a$ and $\displaystyle b$ such that

$\displaystyle r=sa+b,\quad 1\leq b<s.\quad\quad (1)$

By the hypothesis of the induction, there are integers $\displaystyle m>0$ , $\displaystyle a_1$ , $\displaystyle a_2>0$ , $\displaystyle \ldots$ , $\displaystyle a_m>0$ such that

$\displaystyle \frac{s}{b}=[a_1;a_2,a_3,\ldots,a_m].\quad\quad (2)$

Because $\displaystyle s>b$ , we have $\displaystyle a_1>0$ . From (1) and (2) we have

$\displaystyle \frac{r}{s}=a+\frac{1}{s/b}=a+\frac{1}{[a_1;a_2,a_3,\ldots,a_m]}=[a;a_1,a_2,\ldots,a_m],$ completing the induction step. $\Box$

The equality in the theorem is called an expansion of $\displaystyle r/s$ into a finite continued fraction. In that expansion we will call $\displaystyle [a_0;a_1,a_2,\ldots,a_i]$ is the $i-$ th convergent of the continued fraction, or $i-$ th convergent of $\displaystyle r/s$ .

Example 1. Find an expansion of $\displaystyle 43/5$ into a finite continued fraction.

Solution. By the Division Algorithm, we have

$\displaystyle 43=5\cdot 8+3\quad\quad\frac{43}{5}=8+\frac{3}{5}=8+\frac{1}{5/3},$ and

$\displaystyle 5= 3\cdot 1 +2\quad\quad\frac{5}{3}=1+\frac{2}{3}=1+\frac{1}{3/2},$ and $\displaystyle \frac{3}{2}=1+\frac{1}{2}$ . Therefore $\displaystyle 43/5=[8;1,1,2]$ . $\Box$

The theorem says that for every rational number has an expansion into a finite continued fraction. But this expansion is not unique.

Example 2. $\displaystyle 13/5=[2;1,1,2]=[2;1,1,1,1]$ . $\Box$

Theorem 2. Let $\displaystyle \alpha$ be an integer number. Then $\displaystyle \alpha$ has exactly two expansions into a finite continued fraction.

Proof. By the theorem 1, we can write

$\displaystyle \alpha=[a_0;a_1,a_2,\ldots,a_n],$

where $a_0$ , $a_1$ , $\ldots$ , $a_n$ are integers such that $a_i>0$ for every $i=1,2,\ldots,n$ . If $\displaystyle n=0$ then $\displaystyle \alpha=a_0$ and $\displaystyle \alpha=[\alpha]$ is an expansion of $\displaystyle \alpha$ . If $\displaystyle n=1$ then $\displaystyle \alpha=a_0+\frac{1}{a_1}$ , hence $\displaystyle \frac{1}{a_1}$ is an integer, so $\displaystyle a_1=1$ . Therefore $\displaystyle \alpha=[\alpha-1;1]$ is an expansion of $\displaystyle \alpha$ .

Now assume that $\displaystyle n\geq 2$ . We have

$\displaystyle \alpha-a_0=\frac{1}{[a_1;a_2,\ldots,a_n]}$

is an integer number and $\displaystyle [a_1;a_2,\ldots,a_n]>0$ , hence $\displaystyle [a_1;a_2,\ldots,a_n]\leq 1$ . This claim is false because $\displaystyle n\geq 2$ and $\displaystyle a_i\geq 1$ for every $\displaystyle i=1,2,\ldots,n$ . $\Box$

Theorem 3. Let $\displaystyle \alpha$ be a rational number but not an integer. Then $\displaystyle \alpha$ has exactly two expansions into a finite continued fraction.

Proof. Assume that $\displaystyle \alpha=\alpha=r/s$ , where $\displaystyle r$ and $\displaystyle s>1$ are coprime integers. We prove by induction on $\displaystyle s$ that $\displaystyle \alpha$ has exactly two expansions into a finite continued fraction

$\displaystyle \alpha=[a_0;a_1,\ldots,a_n]=[a_0;a_1,\ldots,a_n-1,1],$

where $\displaystyle a_n>1$ . If $\displaystyle s=2$ , because $\displaystyle (r,s)=1$ there is an integer $\displaystyle k$ such that $\displaystyle r=2k+1$ . By the theorem 1, we can write

$\displaystyle \alpha=k+\frac{1}{2}=[a_0;a_1,a_2,\ldots,a_n],$

where $a_0$ , $a_1$ , $\ldots$ , $a_n$ are integers such that $a_i>0$ for every $i=1,2,\ldots,n$ . We have $n>0$ and $a_0=k$ , hence $\displaystyle 2=[a_1;a_2,\ldots,a_n]$ . By the theorem 2, we have $2$ has exactly two expansions into a finite continued fraction, those are $2=[2]$ and $2=[1;1]$ , therefore $\alpha$ has exactly two expansions $\displaystyle \alpha=[k;2]=[k;1,1],$ hence the claim is true for $\displaystyle s=2$ . Now suppose that the claim is true for $\displaystyle 2$ , $\displaystyle 3$ , $\displaystyle \ldots$ , $\displaystyle s-1$ ( $\displaystyle s>2$ ). By the theorem 1, we can write

$\displaystyle \alpha=[a_0;a_1,a_2,\ldots,a_n],$

where $a_0$ , $a_1$ , $\ldots$ , $a_n$ are integers such that $a_i>0$ for every $i=1,2,\ldots,n$ . We have $n>0$ and $a_0=[\alpha]$ (integer part of $\alpha$ ), hence $\displaystyle \frac{1}{\alpha-[\alpha]}=[a_1;a_2,\ldots,a_n].$ By the Division Algorithm, there is an integer $\displaystyle a$ such that $\displaystyle r=s[\alpha]+a$ and $1\leq a<s$ , then

$\displaystyle \frac{s}{a}=[a_1;a_2,\ldots,a_n].$

If $a=1$ then $a_1>1$ and by the theorem 2, we have $s/a$ has exactly two expansions are $s/a=[a_1]$ and $\displaystyle s/a=[a_1-1;1]$ . If $\displaystyle a>1$ then by the hypothesis of the induction (note that $\displaystyle s$ and $\displaystyle a$ are coprime integers), $\displaystyle s/a$ has exactly two expansions are