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$

Perfect rulers

Giả sử ta có một cái thước kẻ dài $\displaystyle 6$ , trên đó đã đánh dấu các điểm $\displaystyle 0$ , $\displaystyle 1$ , $\displaystyle 2$ , $\displaystyle 3$ , $\displaystyle 4$ , $\displaystyle 5$ , $\displaystyle 6$ . Sử dụng chiếc thước này ta có thể tạo mọi đoạn có độ dài thuộc $\displaystyle [6]$ , nhưng ta không cần đánh dấu trên thước nhiều điểm như thế để đạt được điều này. Ta có thể đánh dấu $\displaystyle 0$ , $\displaystyle 1$ , $\displaystyle 4$ , $6$ là đủ (đoạn độ dài $2$ được đo giữa hai điểm $4$ và $6$ , đoạn độ dài $3$ được đo giữa $1$ và $4$ , đoạn độ dài $4$ được đo giữa $0$ và $4$ , đoạn độ dài $5$ được đo giữa $1$ và $6$ ). Vì $C_4^2=6$ nên hoàn cảnh này là hoàn hảo.

Bài toán. Cho một số nguyên $n$ lớn hơn $4$ . Chứng minh rằng không tồn tại $n$ số tự nhiên phân biệt $a_1$ , $a_2$ , $\ldots$ , $a_n$ sao cho mọi số nguyên dương không vượt quá $C_n^2$ đều có dạng $a_i-a_j$ .

Lời giải. Giả sử ngược lại, tồn tại $n$ số tự nhiên phân biệt $a_1$ , $a_2$ , $\ldots$ , $a_n$ sao cho mọi số nguyên dương không vượt quá $C_n^2$ đều có dạng $a_i-a_j$ .

Xét đa thức $\displaystyle A(z) = \sum_i z^{a_i}$ . Theo tính chất của các số $a_1$ , $a_2$ , $\ldots$ , $a_n$ , ta có

$\displaystyle A(z) \cdot A\left(\frac{1}{z}\right)=\sum_{k=-C_n^2}^{C_n^2} z^k+n-1,\quad \forall z\in\mathbb{C}\setminus \{0\}.$

Continue reading →

A nonnegative trigonometric polynomial

Bài toán. Cho số tự nhiên $n$ . Chứng minh rằng với mỗi số thực $x$ , ta có

$\displaystyle\frac{1}{2}+\frac{\cos x}{2}+\frac{\cos 2x}{3}+\cdots+\frac{\cos nx}{n+1}\geq 0.$

Lời giải. Dễ thấy khi $\displaystyle n<3$ thì khẳng định là đúng. Bây giờ ta xét $\displaystyle n\geq 3.$ Vế trái là hàm số chẵn, tuần hoàn với chu kỳ $\displaystyle 2\pi$ , và bất đẳng thức đúng với $\displaystyle x=0$ . Vì thế ta chỉ cần chứng minh bất đẳng thức khi $\displaystyle 0<x\leq \pi.$ Sử dụng số phức ta chứng minh được kết quả sau:

Bổ đề. $\displaystyle \frac{1}{2}+\sum_{k=1}^n\cos kx=\frac{\sin (2n+1)\frac{x}{2}}{2\sin \frac{x}{2}}$ , và $\displaystyle \sum_{k=0}^n\frac{\sin (2k+1)\frac{x}{2}}{2\sin\frac{x}{2}}=\frac{\sin^2(n+1)\frac{x}{2}}{2\sin^2 \frac{x}{2}}.$

Gọi vế trái của bất đẳng thức là $\displaystyle f_n(x).$ Dùng biến đổi Abel hai lần và bổ đề, ta có $\displaystyle 2\sin^2(x/2)f_n(x)=\sum_{k=0}^{n-2}\frac{2\sin^2(k+1)(x/2)}{(k+1)(k+2)(k+3)}+\frac{\sin^2n(x/2)}{n(n+1)}$

$\displaystyle +\frac{\sin (2n+1)(x/2)\sin (x/2)}{n+1}.\quad (1)$

Nếu $\displaystyle (2n+1)\frac{x}{2}\leq \pi$ thì dễ có điều cần chứng minh, bây giờ ta xét trường hợp còn lại, khi đó $\displaystyle n+1>\frac{2\pi+x}{2x}.\quad (2).$

Từ $\displaystyle (1)$ và $\displaystyle n\geq 3$ , bằng cách dùng hai số hạng đầu trong tổng, ta có bất đẳng thức

$\displaystyle 2\sin^2(x/2)f_n(x)\geq \frac{\sin^2(x/2)}{3}+\frac{\sin^2x}{12}-\frac{\sin (x/2)}{n+1}.$

Vì thế, bài toán sẽ được giải nếu ta chứng minh được $\displaystyle n+1\geq \frac{6}{\sin \frac{x}{2}(3+\cos x)}:=g(x).\quad (3)$

Bây giờ ta xét hai trường hợp:

Trường hợp 1: $\displaystyle 0<x\leq \pi/3.$

Hàm số $\displaystyle y=\sin t/t$ nghịch biến trên $\displaystyle (0;\pi/6]$ nên $\displaystyle \sin\frac{x}{2}\geq \frac{3x}{2\pi},$ suy ra $\displaystyle g(x)\leq \frac{4\pi}{x(3+\cos x)},$ mà $\displaystyle \cos t\geq 1-\frac{t^2}{2}$ với mọi $\displaystyle t$ không âm nên $\displaystyle g(x)\leq \frac{8\pi}{x(8-x^2)}.\quad (4)$

Vì $\displaystyle 0<x\leq \pi/3$ nên $\displaystyle x^2+2\pi x<8,$ suy ra $\displaystyle \frac{8\pi}{x(8-x^2)}<\frac{2\pi+x}{2x}.$ Kết hợp với $\displaystyle (2)$ ta có $\displaystyle (3)$ đúng.

Trường hợp 2: $\pi/3<x\leq \pi.$

Bằng cách chuyển về biến $\displaystyle t=\sin x/2$ ta chứng minh được $\displaystyle g(x)<4\leq n+1,$ và có $\displaystyle (3)$ lại đúng.

An inequality with n variables

Bài toán. Cho số nguyên $n>2$ và $n$ số thực $a_1,a_2,\ldots,a_n$ có tổng bằng không. Chứng minh rằng

$\displaystyle \sum_{i=1}^na_i^2\leq \frac{n^2}{16}\sum_{i=1}^n(a_i-a_{i+1})^2.\quad (*)$

Lời giải. Vì $\displaystyle \sum a_i=0$ nên

$\displaystyle n\sum a_i^2=n\sum a_i^2-(\sum a_i)^2=\sum_{i<j}(a_i-a_j)^2.$

Với mỗi $\displaystyle i$ , đặt $\displaystyle d_i=a_i-a_{i+1}$ . Ta có

$\displaystyle 2n\sum_{i=1}^na_i^2 = \sum_{i\not=j}(a_i-a_j)^2$ $\displaystyle =\sum_{k=1}^{n-1}\sum_{i=1}^n(a_i-a_{i+k})^2= \sum_{k=1}^{n-1}\sum_{i=1}^n\left(d_i+d_{i+1}+\cdots+d_{i+k-1}\right)^2.$

Từ đây, để ý $\displaystyle \sum_{i=1}^n d_i=0$ và dùng bất đẳng thức Cauchy ta có

$\displaystyle 2n\sum_{i=1}^n a_i^2\leq \sum_{i=1}^n(1^2+2^2+\cdots+2^2+1^2)d_i^2.$

Trong đó $\displaystyle T_n=1^2+2^2+\cdots+2^2+1^2$ là tổng của $\displaystyle n-1$ số. Đến đây, chia hai trường hợp $\displaystyle n$ chẵn và $\displaystyle n$ lẻ ta dễ tính được $\displaystyle T_n$ và từ đó có $\displaystyle (*)$ . $\Box$