IMO Shortlist 2008

Đại số

Bài 1. Tìm tất cả các hàm số $f:(0,\infty)\mapsto(0,\infty)$ (tức là $f$ là một hàm từ tập các số thực dương) thỏa mãn

$\displaystyle\frac{(f(w))^{2}+(f(x))^{2}}{f(y^{2})+f(z^{2})}=\frac{w^{2}+x^{2}}{y^{2}+z^{2}}$

với mọi số thực dương $w, x, y, z$ thỏa mãn $wx=yz$ .

Bài 2. (a) Chứng minh rằng $\frac{x^{2}}{(x-1)^{2}}+\frac{y^{2}}{(y-1)^{2}}+\frac{z^{2}}{(z-1)^{2}}\ge1$ với mọi số thực $x, y, z$ khác 1 và thỏa mãn $xyz=1$ .
(b) Chứng minh rằng đẳng thức trên xảy ra với vô số bộ ba số hữu tỉ $x, y, z$ khác 1 và thỏa mãn $xyz=1$ .

Bài 3. Cho $S\subseteq\mathbb{R}$ là một tập hợp các số thực. Ta nói rằng một cặp hàm số $(f, g)$ từ $S$ vào $S$ là một “Cặp đôi Tây Ban Nha” (Spanish Couple) trên $S$ , nếu chúng thỏa mãn các điều kiện sau:
(i) Cả hai hàm số đều tăng ngặt, tức là $f(x)<f(y)$ và $g(x)<g(y)$ với mọi $x, y\in S$ mà $x<y$ ;
(ii) Bất đẳng thức $f(g(g(x)))<g(f(x))$ đúng với mọi $x\in S$ .
Hãy xác định xem có tồn tại một Cặp đôi Tây Ban Nha trên tập $S=\mathbb{N}$ các số nguyên dương hay không; và trên tập $S={a-\frac{1}{b}:a,b\in\mathbb{N}}$ .

Bài 4. Với một số nguyên $m$ , gọi $t(m)$ là số duy nhất thuộc ${1,2,3}$ sao cho $m+t(m)$ là bội của 3. Một hàm số $f:\mathbb{Z}\rightarrow\mathbb{Z}$ thỏa mãn $f(-1)=0$ , $f(0)=1$ , $f(1)=-1$ và $f(2^{n}+m)=f(2^{n}-t(m))-f(m)$ với mọi số nguyên $m, n\ge0$ sao cho $2^{n}>m$ . Chứng minh rằng $f(3p)\ge0$ đúng với mọi số nguyên $p\ge0$ .

Bài 5. Cho $a, b, c, d$ là các số thực dương thỏa mãn $abcd=1$ và $a+b+c+d>\frac{a}{b}+\frac{b}{c}+\frac{c}{d}+\frac{d}{a}$ . Chứng minh rằng $a+b+c+d<\frac{b}{a}+\frac{c}{b}+\frac{d}{c}+\frac{a}{d}$ .

Bài 6. Cho hàm số $f:\mathbb{R}\rightarrow\mathbb{N}$ thỏa mãn $f(x+\frac{1}{f(y)})=f(y+\frac{1}{f(x)})$ với mọi $x,y\in\mathbb{R}$ . Chứng minh rằng tồn tại một số nguyên dương không phải là giá trị của $f$ .

Bài 7. Chứng minh rằng với bốn số thực dương $a, b, c, d$ bất kỳ, bất đẳng thức

$\displaystyle\frac{(a-b)(a-c)}{a+b+c}+\frac{(b-c)(b-d)}{b+c+d}+\frac{(c-d)(c-a)}{c+d+a}+\frac{(d-a)(d-b)}{d+a+b}\ge0$

luôn đúng. Xác định tất cả các trường hợp xảy ra dấu đẳng thức.

Tổ hợp

Bài 1. Trong mặt phẳng, ta xét các hình chữ nhật có các cạnh song song với các trục tọa độ và có độ dài dương. Mỗi hình chữ nhật như vậy được gọi là một hộp. Hai hộp giao nhau nếu chúng có một điểm chung ở phần trong hoặc trên biên. Tìm số $n$ lớn nhất sao cho tồn tại $n$ hộp $B_{1}$ ,…, $B_{n}$ thỏa mãn $B_{i}$ và $B_{j}$ giao nhau khi và chỉ khi $i\not\equiv j\pm1 \pmod n$ .

Bài 2. Cho $n\in\mathbb{N}$ và $A_{n}$ là tập hợp tất cả các hoán vị $(a_{1},...,a_{n})$ của tập ${1,2,...,n}$ sao cho $k\mid 2(a_{1}+\cdot\cdot\cdot+a_{k})$ với mọi $1\le k\le n$ . Tìm số phần tử của tập $A_{n}$ .

Bài 3. Trong mặt phẳng tọa độ, xét tập $S$ gồm tất cả các điểm có tọa độ nguyên. Với một số nguyên dương $k$ , hai điểm phân biệt $A, B\in S$ được gọi là $k$ -bạn bè nếu tồn tại một điểm $C\in S$ sao cho diện tích tam giác $ABC$ bằng $k$ . Một tập $T\subset S$ được gọi là $k$ -clique nếu cứ hai điểm bất kỳ trong $T$ đều là $k$ -bạn bè. Tìm số nguyên dương nhỏ nhất sao cho tồn tại một $k$ -clique có nhiều hơn 200 phần tử.

Bài 4. Cho $n$ và $k$ là các số nguyên dương với $k\ge n$ và $k-n$ là một số chẵn. Có $2n$ bóng đèn được đánh số từ 1 đến $2n$ , mỗi bóng có thể ở trạng thái bật hoặc tắt. Ban đầu tất cả các bóng đèn đều tắt. Ta xét các dãy bước thực hiện: tại mỗi bước, một trong các bóng đèn được chuyển trạng thái (từ bật sang tắt hoặc từ tắt sang bật). Gọi $N$ là số lượng các dãy như vậy gồm $k$ bước và dẫn đến trạng thái mà các bóng đèn từ 1 đến $n$ đều bật, còn các bóng đèn từ $n+1$ đến $2n$ đều tắt. Gọi $M$ là số lượng các dãy gồm $k$ bước dẫn đến trạng thái mà các bóng đèn từ 1 đến $n$ đều bật, các bóng đèn từ $n+1$ đến $2n$ đều tắt, nhưng không có bóng đèn nào từ $n+1$ đến $2n$ từng được bật lên. Xác định tỉ số $\frac{N}{M}$ .

Bài 5. Cho $S={x_{1},x_{2},...,x_{k+l}}$ là một tập hợp gồm $k+l$ số thực nằm trong đoạn $[0, 1]$ ; $k$ và $l$ là các số nguyên dương. Một tập con $A\subset S$ gồm $k$ phần tử được gọi là “đẹp” nếu

$\displaystyle \left|\frac{1}{k}\sum_{x_{i}\in A}x_{i}-\frac{1}{l}\sum_{x_{j}\in S\backslash A}x_{j}\right|\le\frac{k+l}{2kl}.$

Chứng minh rằng số lượng các tập con đẹp ít nhất là $\frac{2}{k+l}\binom{k+l}{k}$ .

Bài 6. Với $n\ge2$ , cho $S_{1},S_{2},...,S_{2^{n}}$ là $2^{n}$ tập con của $A={1,2,3,...,2^{n+1}}$ thỏa mãn tính chất sau. Không tồn tại các chỉ số $a$ và $b$ với $a<b$ và các phần tử $x,y,z\in A$ với $x<y<z$ sao cho $y,z\in S_{a}$ và $x,z\in S_{b}$ . Chứng minh rằng ít nhất một trong các tập $S_{1},S_{2},...,S_{2^{n}}$ chứa không quá $4n$ phần tử.

Continue reading →

The sum of the reciprocals of the primes

Với mỗi số nguyên dương $n$ , ký hiệu $p_n$ là số nguyên tố thứ $n$ trong dãy tăng tất cả các số nguyên tố. Như vậy $p_1=2$ , $p_2=3$ , $p_3=5$ ,…

Trong bài này chúng tôi sẽ giới thiệu một chứng minh của kết quả sau:

Định lý. Chuỗi $\displaystyle \frac{1}{p_1}+\frac{1}{p_2}+\frac{1}{p_3}+\ldots$ là một chuỗi phân kỳ.

Chứng minh. Giả sử ngược lại, khi đó với mỗi số nguyên dương $k$ , chuỗi $\displaystyle\sum_{m=k}^{+\infty}\frac{1}{p_m}$ là một chuỗi hội tụ, gọi $S_k$ là tổng của nó. Vì $\lim S_k=0$ nên tồn tại số nguyên $k$ sao cho $\displaystyle S_{k+1}<\frac{1}{2}$ . Đặt $Q=p_1p_2\ldots p_k$ và xét các số $1+nQ\, (n=1,2,\ldots)$ . Mỗi số trong dãy này đều không có ước nguyên tố thuộc $\{p_1, p_2, \ldots, p_k\}$ , do đó với mỗi số nguyên dương $r$ , tồn tại số nguyên dương $K$ đủ lớn để

$\displaystyle\sum_{n=1}^r\frac{1}{1+nQ}\leq\sum_{t=1}^{K}S_{k+1}^t<1.$

Điều này không thể xảy ra do chuỗi $\displaystyle \sum_{n=1}^{+\infty}\frac{1}{1+nQ}$ là một chuỗi phân kỳ. $\Box$

Tham khảo

[1] https://nttuan.org/2018/12/30/series/

[2] https://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes

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/

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

$\displaystyle \frac{s}{a}=[a_1;b_2,\ldots,b_n]=[a_1;b_2,\ldots,b_n-1,1],$

where $\displaystyle b_n>1$ . Therefore $\displaystyle \alpha$ has exactly two expansions, and the claim is true for $\displaystyle s$ . $\Box$

References

[1] https://nttuan.org/2020/01/14/divisibility/

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

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}}.$