The Motzkin-Straus Theorem

To fully comprehend this topic, a basic understanding of multivariable calculus is required. A highly recommended reference is [1], specifically Theorem 2.4.15.

Let $\displaystyle G$ be a simple, undirected graph with vertices labeled as $\displaystyle 1, 2, \dots, n$ . Let $\displaystyle S$ be the set of all non-negative real vectors whose components sum to $\displaystyle 1$ :

$\displaystyle S = \left\{ x = (x_1, x_2, \dots, x_n) \in \mathbb{R}^n \;\middle|\; x_i \ge 0 \text{ for all } i=1,\dots,n, \text{ and } \sum_{i=1}^{n} x_i = 1 \right\}.$

For any vector $\displaystyle x \in S$ , we define the objective function $\displaystyle f(x)$ as the sum of the products of the weights associated with adjacent vertices in $\displaystyle G$ :

$\displaystyle f(x) = \sum_{(i,j) \in E} x_i x_j. \qquad (1)$

Here, each edge $\displaystyle (i,j) = (j,i) \in E$ is counted exactly once. The Motzkin-Straus theorem investigates the maximum value of this function over the set $\displaystyle S$ , denoted as:

$\displaystyle f(G) = \max_{x \in S} f(x) = \max_{x \in S} \sum_{(i,j) \in E} x_i x_j.$

Remark on Existence: The function $\displaystyle f(x)$ defined in (1) is a polynomial, which implies it is continuous everywhere on $\displaystyle \mathbb{R}^n$ . Furthermore, the domain $\displaystyle S$ is a closed and bounded set (a compact set) in $\displaystyle \mathbb{R}^n$ . According to the Extreme Value Theorem, any continuous real-valued function attains both a global maximum and a global minimum on a closed and bounded domain. Therefore, the maximum value $\displaystyle f(G)$ is strictly guaranteed to exist.

Theorem (Motzkin-Straus, 1965). Let $\displaystyle k$ be the clique number (the order of the largest complete subgraph) of $\displaystyle G$ . Then

$\displaystyle f(G)=\frac{1}{2}\left(1-\frac{1}{k}\right). \qquad (2)$

Proof. Suppose $\displaystyle x = (x_1, x_2, \dots, x_n)$ is a point in $\displaystyle S$ that maximizes the function

$\displaystyle f(x) = \sum_{(i,j)\in G} x_i x_j.$

Let $\displaystyle V_x = \{i \mid x_i > 0\}$ be the set of vertices with positive weights. Suppose $\displaystyle V_x$ does not induce a complete subgraph (clique). Then, there exist at least two vertices $\displaystyle u, v \in V_x$ that are not adjacent in $\displaystyle G$ .

Let $\displaystyle S_u = \sum_{j \in N(u)} x_j$ and $\displaystyle S_v = \sum_{j \in N(v)} x_j$ be the sum of the weights of the neighbors of $\displaystyle u$ and $\displaystyle v$ in $\displaystyle G$ , respectively. Without loss of generality, assume that $\displaystyle S_u \le S_v$ .

We construct a new weight distribution $\displaystyle x'$ by shifting the entire weight of $\displaystyle u$ to $\displaystyle v$ :

$\displaystyle x'_u = 0$
$\displaystyle x'_v = x_u + x_v$
$\displaystyle x'_i = x_i$ for all $\displaystyle i \neq u, v$ .

It is clear that $\displaystyle x' \in S$ because the total weight remains $\displaystyle 1$ and all weights remain non-negative. The change in the objective function is given by

$\displaystyle f(x') - f(x) = x_u (S_v - S_u).$

Since $\displaystyle x_u > 0$ and $\displaystyle S_v \ge S_u$ , we have $\displaystyle f(x') \ge f(x)$ . However, because $\displaystyle x$ is already a global maximizer, it must hold that $\displaystyle f(x') = f(x)$ .

The new point $\displaystyle x'$ still achieves the maximum value, but the number of vertices with positive weights has decreased by 1 (since $\displaystyle x'_u = 0$ ). We repeat this weight-shifting process for any remaining pair of non-adjacent vertices with positive weights. This process must terminate after a finite number of steps. Upon termination, all vertices with positive weights must be mutually adjacent, meaning they form a complete subgraph $\displaystyle C$ .

Let $\displaystyle m$ be the number of vertices in $\displaystyle C$ . Since $\displaystyle k$ is the clique number of $\displaystyle G$ , we must have $\displaystyle m \le k$ . On the complete subgraph $\displaystyle C$ , all vertices are pairwise adjacent, so

$\displaystyle f(x) = \sum_{(i,j) \in C} x_i x_j = \frac{1}{2} \left( \left( \sum_{i \in C} x_i \right)^2 - \sum_{i \in C} x_i^2 \right).$

Since the sum of the weights on $\displaystyle C$ is $\displaystyle \sum_{i \in C} x_i = 1$ , we obtain

$\displaystyle f(x) = \frac{1}{2} \left( 1 - \sum_{i \in C} x_i^2 \right).$

By the Cauchy-Schwarz inequality, we have

$\displaystyle \sum_{i \in C} x_i^2 \ge \frac{1}{m} \left( \sum_{i \in C} x_i \right)^2 = \frac{1}{m}.$

This implies $\displaystyle f(x) \le \frac{1}{2} \left( 1 - \frac{1}{m} \right).$

Since the function $\displaystyle g(m) = \frac{1}{2}\left(1 - \frac{1}{m}\right)$ is strictly increasing with respect to $\displaystyle m$ and $\displaystyle m \le k$ , we get:

$\displaystyle f(x) \le \frac{1}{2} \left( 1 - \frac{1}{k} \right). \qquad (3)$

Now, choose a maximum complete subgraph of $\displaystyle G$ with order $\displaystyle k$ . Assume the vertices of this subgraph are $\displaystyle 1, 2, \dots, k$ . By distributing the total weight equally among these $\displaystyle k$ vertices and setting the weights of all other vertices to $\displaystyle 0$ , i.e.,

$\displaystyle x_1 = x_2 = \dots = x_k = \frac{1}{k} \quad \text{and} \quad x_{k+1} = \dots = x_{n} = 0,$

we can compute the value of the objective function at this specific point as:

$\displaystyle f(x) = \binom{k}{2} \cdot \frac{1}{k^2} = \frac{k(k-1)}{2} \cdot \frac{1}{k^2} = \frac{1}{2} \left( 1 - \frac{1}{k} \right). \qquad (4)$

Combining (3) and (4), we conclude that the maximum value of the objective function on the set $\displaystyle S$ is precisely $\displaystyle f(G) = \frac{1}{2}\left(1 - \frac{1}{k}\right).$

This completes the proof. ∎

Corollary (Turán’s Theorem). Let $\displaystyle G$ be a graph with $\displaystyle n$ vertices and edge set $\displaystyle E$ . If $\displaystyle G$ contains no complete subgraph of order $\displaystyle k+1$ (meaning the clique number of $\displaystyle G$ does not exceed $\displaystyle k$ ), then the number of edges in $\displaystyle G$ satisfies

$\displaystyle |E| \le \frac{n^2}{2} \left( 1 - \frac{1}{k} \right).$

Proof. Consider the uniform weight distribution $\displaystyle x = \left(\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n}\right)$ . Clearly, $\displaystyle x \in S$ since all coordinates are non-negative and their sum equals 1.

Evaluating the objective function $\displaystyle f(x)$ at this point, each edge $\displaystyle (i,j) \in G$ contributes exactly $\displaystyle \frac{1}{n} \cdot \frac{1}{n} = \frac{1}{n^2}$ . Since the graph $\displaystyle G$ has $\displaystyle |E|$ edges, we have:

$\displaystyle f(x) = \sum_{(i,j) \in G} x_i x_j = \sum_{(i,j) \in G} \frac{1}{n^2} = \frac{|E|}{n^2}.$

On the other hand, by the Motzkin-Straus Theorem, the value of $\displaystyle f(x)$ at any point in $\displaystyle S$ cannot exceed the global maximum $\displaystyle f(G)$ . Let $\displaystyle m$ be the clique number of $\displaystyle G$ . By hypothesis, $\displaystyle m \le k$ . Therefore:

$\displaystyle f(x) \le f(G) = \frac{1}{2} \left( 1 - \frac{1}{m} \right) \le \frac{1}{2} \left( 1 - \frac{1}{k} \right).$

Combining these two results, we obtain $\displaystyle |E| \le \frac{n^2}{2} \left( 1 - \frac{1}{k} \right).$

The inequality is thus proven. ∎

References
[1] Jerry Shurman, Calculus and Analysis in Euclidean Space (pages 23-56).

IMO Shortlist 2024: Algebra

Trong bài này tôi sẽ giới thiệu các bài toán đại số trong cuốn IMO Shortlist 2024, các bài toán từ IMO SL năm trước các bạn có thể tìm ở https://nttuan.org/category/contests/imo-shortlist/ .

Phần hình học của bộ 2024 tôi đã đăng ở đây https://nttuan.org/2025/08/07/isl2024g/

A1. https://artofproblemsolving.com/community/c6h3358923p31205921

Tìm tất cả các số thực $\alpha$ sao cho với mỗi số nguyên dương $n$ , số

$[\alpha]+[2\alpha]+\cdots+[n\alpha]$

chia hết cho $n$ . (IMO2024/1)

A2. https://artofproblemsolving.com/community/c6h3610446p35340919

Cho $n$ là một số nguyên dương. Tìm giá trị nhỏ nhất có thể của

$S = 2^0 x_0^2 + 2^1 x_1^2 + \dots + 2^n x_n^2,$

trong đó $x_0, x_1, \dots, x_n$ là các số nguyên không âm sao cho $x_0 + x_1 + \dots + x_n = n$ .

A3. https://artofproblemsolving.com/community/c6h3610463p35340954

Hãy xác định xem với mọi dãy số thực dương $(a_n)$ ,

$\displaystyle\frac{3^{a_1}+3^{a_2}+\cdots+3^{a_n}}{(2^{a_1}+2^{a_2}+\cdots+2^{a_n})^2} < \frac{1}{2024}$

có đúng với ít nhất một số nguyên dương $n$ hay không.

A4. https://artofproblemsolving.com/community/c6h3610435p35340902

Tìm tất cả các tập con $\mathcal{S}$ của $\{2^{0},2^{1},2^{2},\ldots\}$ sao cho tồn tại một hàm $f\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ với

$\mathcal{S}=\{f(a+b)-f(a)-f(b)\mid a,b\in\mathbb{Z}_{>0}\}.$

A5. https://artofproblemsolving.com/community/c6h3610458p35340939

Tìm tất cả các dãy số tuần hoàn $a_1,a_2,\dots$ gồm các số thực sao cho với mỗi số nguyên dương $n$ ,

$a_{n+2}+a_{n}^2=a_n+a_{n+1}^2$

và $|a_{n+1}-a_n|\leqslant 1.$

A6. https://artofproblemsolving.com/community/c6h3610454p35340929

Cho $a_0, a_1, a_2, \ldots$ là một dãy tăng ngặt các số nguyên dương sao cho với mỗi $n \ge 1$ , ta có

$\displaystyle a_n \in \left\{ \frac{a_{n-1} + a_{n+1}}{2}, \sqrt{a_{n-1} \cdot a_{n+1}} \right\}.$

Cho $b_1, b_2, \ldots$ là một dãy vô hạn các chữ cái được xác định bởi

$b_n = A$ nếu $a_n = \frac{1}{2}(a_{n-1} + a_{n+1})$ , $=G$ trong trường hợp còn lại. Chứng minh rằng tồn tại các số nguyên dương $n_0$ và $d$ sao cho với mọi $n \ge n_0$ ta có $b_{n+d} = b_n$ .

A7. https://artofproblemsolving.com/community/c6h3359771p31218720

Một hàm số $f:\mathbb{Q}\to\mathbb{Q}$ được gọi là đẹp nếu với mỗi số hữu tỷ $x$ và $y$ , $f(x+f(y))=f(x)+y$ hoặc $f(f(x)+y)=x+f(y)$ . Chứng minh rằng tồn tại số nguyên $c$ sao cho với mọi hàm số đẹp $f$ , có không quá $c$ số hữu tỷ có dạng $f(r)+f(-r)$ , với số hữu tỷ $r$ nào đó. Tìm giá trị nhỏ nhất của các số $c$ có tính chất này. (IMO2024/6)

A8. https://artofproblemsolving.com/community/c6h3610460p35340944

Cho $p \ne q$ là các số nguyên dương nguyên tố cùng nhau. Xác định tất cả các dãy vô hạn $a_1$ , $a_2$ , $\dots$ các số nguyên dương sao cho với mỗi số nguyên dương $n$ ,

$\max(a_n, a_{n+1}, \dots, a_{n+p}) - \min(a_n, a_{n+1}, \dots, a_{n+p}) = p$

và $\max(a_n, a_{n+1}, \dots, a_{n+q}) - \min(a_n, a_{n+1}, \dots, a_{n+q}) = q$ .

Formal power series

Định nghĩa 1. Một chuỗi lũy thừa hình thức là một biểu diễn có dạng

$a_0+a_1x+a_2x^2+a_3x^3+\ldots,$

hay gọn hơn $\displaystyle\sum_{k=0}^{\infty}a_kx^k.$ Trong đó $(a_n)_{n\geq 0}$ là một dãy các số phức. Các $a_i$ được gọi là các hệ số của chuỗi lũy thừa hình thức, $a_0$ được gọi là hệ số tự do của chuỗi lũy thừa hình thức.

Từ “hình thức” trong định nghĩa trên có nghĩa là ta không bận tâm đến việc cho $x$ các giá trị đặc biệt, ta cũng không quan tâm đến tính hội tụ hay phân kỳ của chuỗi. Tập tất cả các chuỗi lũy thừa hình thức với hệ số thuộc một tập hợp $A$ được ký hiệu bởi $A[[x]]$ . Với một chuỗi lũy thừa hình thức $a(x)$ , ta ký hiệu hệ số của $x^n$ trong chuỗi này bởi $[x^n]a(x)$ .

Nếu $a_i=0$ với mọi $i>m$ thì để cho gọn, chuỗi $\sum_{n=0}^{\infty}a_nx^n$ sẽ được viết là

$a_0+a_1x+\ldots+a_mx^m.$

Chuỗi lũy thừa hình thức với tất cả các hệ số bằng $0$ được gọi là chuỗi không, ký hiệu là $0$ . Tổng và tích của hai chuỗi lũy thừa hình thức $\displaystyle\sum_{n=0}^{\infty}a_nx^n$ và $\displaystyle\sum_{n=0}^{\infty}b_nx^n$ được định nghĩa bởi

$\displaystyle\sum_{n=0}^{\infty}a_nx^n+\sum_{n=0}^{\infty}b_nx^n=\sum_{n=0}^{\infty}(a_n+b_n)x^n$

và

$\displaystyle\left(\sum_{n=0}^{\infty}a_nx^n\right)\left(\sum_{n=0}^{\infty}b_nx^n\right)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^na_kb_{n-k}\right)x^n.$

Với hai phép toán này thì $\mathbb{C}[[x]]$ là một vành giao hoán có đơn vị là chuỗi đơn vị $1+0x^1+0x^2+0x^3+\ldots,$ ký hiệu là $1$ .

Tương tự như với các số phức, ta có kết quả sau:

Định lý 1. Nếu $a$ và $b$ là các phần tử khác không của $\mathbb{C}[[x]]$ , thì chuỗi tích $ab$ cũng khác chuỗi không.

Chứng minh. Gọi $m$ là số tự nhiên nhỏ nhất sao cho $[x^m]a\not=0$ , và $n$ là số tự nhiên nhỏ nhất sao cho $[x^n]b\not=0$ . Khi đó

$[x^{m+n}](ab)=([x^m]a)([x^n]b)\not=0,$

suy ra $ab$ khác chuỗi không. $\Box$

Khác với phép nhân trong tập các số phức, không phải mọi chuỗi khác không đều có nghịch đảo. Chẳng hạn, khi $a(x)=0+x+0x^2+0x^3+\ldots,$ (chuỗi này thường được viết là $a(x)=x$ ) thì $a(x)\not=0$ nhưng không có chuỗi $b(x)$ để $a(x)b(x)=1$ .

Định lý 2. Chuỗi $a(x)$ có nghịch đảo khi và chỉ khi $[x^0]a(x)\not=0$ .

Chứng minh. Giả sử chuỗi $a(x)$ có nghịch đảo, và $b(x)$ là nghịch đảo của nó. Khi đó

$1=[x^0](ab)=([x^0]a)([x^0]b),$

suy ra $[x^0]a(x)\not=0$ .

Bây giờ giả sử $\displaystyle a(x)=\sum_{n=0}^{\infty}a_nx^n$ là một chuỗi lũy thừa hình thức có $a_0=[x^0]a(x)\not=0$ . Chuỗi lũy thừa hình thức $\displaystyle b(x)=\sum_{n=0}^{\infty}b_nx^n$ là nghịch đảo của $a(x)$ khi và chỉ khi $a_0b_0=1$ và

$\displaystyle\sum _{k=0}^na_kb_{n-k}=0,\quad\forall n\geq 1.$

Từ hệ này ta có thể xác định $b(x)$ bởi $b_0=1/a_0$ và

$\displaystyle b_n=-\frac{1}{a_0}\sum _{k=1}^na_kb_{n-k},\quad\forall n\geq 1.$ $\Box$

Khi $a$ là một chuỗi có nghịch đảo thì ta ký hiệu chuỗi nghịch đảo của nó bởi $a^{-1}$ . Tích của chuỗi $b$ và chuỗi $a^{-1}$ thường được viết là $\frac{b}{a}$ .

Ví dụ. Chuỗi lũy thừa hình thức $1-x$ có nghịch đảo là chuỗi

$\displaystyle \frac{1}{1-x}=1+x+x^2+x^3+\ldots$

Định nghĩa 2. Dãy các chuỗi lũy thừa hình thức với hệ số phức $\{S_n(x)\}_{n\geq 1}$ được gọi là hội tụ đến chuỗi lũy thừa hình thức với hệ số phức $S(x)$ , ký hiệu $\displaystyle\lim_{n\to\infty} S_n(x)=S(x)$ , nếu với mỗi $n\geq 0$ có số nguyên dương $N$ sao cho $[x^n]S_i(x)=[x^n]S(x)$ mỗi khi $i\geq N$ . Trong trường hợp này ta nói $\{S_n(x)\}_{n\geq 1}$ là một dãy hội tụ.

Khi $\displaystyle A(x)=\sum_{n\geq 0}a_nx^n$ là một phần tử khác không của $\mathbb{C}[[x]]$ , ta gọi bậc của $A(x)$ , ký hiệu $\deg A(x)$ , là số $n$ nhỏ nhất sao cho $a_n\not=0$ . Dễ thấy nếu $B(x)$ và $C(x)$ là các phần tử khác không của $\mathbb{C}[[x]]$ thì $B(x)C(x)$ cũng là một phần tử khác không của $\mathbb{C}[[x]]$ , và

$\deg B(x)C(x)=\deg B(x)+\deg C(x).$

Ta quy ước $\deg 0=\infty$ . Sử dụng bậc của một chuỗi lũy thừa hình thức ta có một định nghĩa khác của tính hội tụ của dãy các chuỗi lũy thừa hình thức.

Continue reading →

VMO 2025/1

VMO 2025/1. Xét đa thức $P(x)=x^4-x^3+x$ .
(1) Chứng minh rằng với mỗi số thực dương $a$ , đa thức $P(x)-a$ có duy nhất một nghiệm thực dương.
(2) Xét dãy số $(a_n)_{n\geq 1}$ xác định bởi $a_1=1/3$ và với mỗi số nguyên dương $n$ , $a_{n+1}$ là nghiệm dương của đa thức $P(x)-a_n$ . Chứng minh rằng dãy số này có giới hạn hữu hạn và tìm giới hạn đó.

Lời giải. Xét một số thực dương $a$ và hàm số $f:\mathbb{R}\to\mathbb{R}$ xác định bởi $f(x)=P(x)-a,\quad\forall x\in\mathbb{R}.$ Hàm số $f$ là một hàm số liên tục trên $(0;+\infty)$ và

$\displaystyle \lim_{x\to 0^+} f(x)=-a<0,\quad\lim_{x\to+\infty}f(x)=+\infty,$

từ đây theo định lý giá trị trung gian, phương trình $f(x)=0$ có ít nhất một nghiệm thực dương. Mặt khác, hàm số $f$ đồng biến trên $(0;+\infty)$ vì

$\displaystyle f^{\prime}(x)=4x^3-3x^2+1=(2x-1)^2\left(x+\frac{1}{4}\right)+\frac{3}{4}>0$

với mọi số thực dương $x$ , suy ra phương trình $f(x)=0$ có đúng một nghiệm thực dương. Do đó phương trình $P(x)-a=0$ có đúng một nghiệm thực dương. Nghiệm này là nghiệm đơn của đa thức $P(x)-a$ nên ta có ý thứ nhất.

Bây giờ ta đến với ý thứ hai. Từ giả thiết ta có

$a_n-1=(a_{n+1}-1)(a_{n+1}^3+1),\quad\forall n\geq 1,$

sử dụng phương pháp quy nạp ta chứng minh được tất cả các số hạng của dãy $(a_n)_{n\geq 1}$ đều thuộc khoảng $(0;1)$ . Suy ra

$a_{n+1}-a_n=a_{n+1}^3(1-a_{n+1})>0,\quad\forall n\geq 1,$

do đó $(a_n)_{n\geq 1}$ là một dãy số tăng. Dãy số này cũng bị chặn trên bởi $1$ nên nó có giới hạn hữu hạn. Gọi $L$ là giới hạn của dãy số $(a_n)_{n\geq 1}$ . Vì $(a_n)_{n\geq 1}$ tăng và các số hạng đều thuộc khoảng $(0;1)$ , nên $0<L\leq 1$ .

Từ $P(a_{n+1})=a_n$ với mọi số nguyên dương $n$ , ta có $L^4-L^3+L=L,$ suy ra $\lim a_n=L=1$ . $\Box$

Absolute convergence

Cho $\displaystyle (u_n)_{n\geq 1}$ là một dãy các số thực. Chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ được gọi là hội tụ tuyệt đối nếu chuỗi $\displaystyle\sum_{n=1}^{+\infty}\mid u_n\mid$ hội tụ. Chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ được gọi là hội tụ có điều kiện nếu nó hội tụ nhưng không hội tụ tuyệt đối. Trong bài trước (xem [1]) ta đã biết chuỗi điều hòa thay phiên là một chuỗi hội tụ có điều kiện. Theo tiêu chuẩn Cauchy, mọi chuỗi hội tụ tuyệt đối đều là chuỗi hội tụ.

Khi làm việc với các chuỗi hội tụ, ta thường muốn việc nhóm vài số hạng liên tiếp hay sắp xếp lại các số hạng sẽ không ảnh hưởng đến sự hội tụ hoặc tổng của chuỗi. Không khó khăn lắm để thấy rằng việc nhóm các số hạng liên tiếp tạo ra một chuỗi hội tụ có tổng bằng tổng của chuỗi ban đầu. Ta có kết quả quan trọng sau liên quan đến sắp xếp các số hạng của chuỗi.

Định lý 1. Cho $\displaystyle (u_n)_{n\geq 1}$ là một dãy các số thực sao cho chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ hội tụ tuyệt đối. Khi đó với mọi song ánh $\displaystyle\sigma :\mathbb{N}^*\to\mathbb{N}^*$ , chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_{\sigma (n)}$ hội tụ và tổng của nó bằng tổng của chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ .

Chứng minh. Gọi $\displaystyle S$ là tổng của chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ , và $\displaystyle\epsilon$ là một số thực dương bất kỳ. Khi đó tồn tại số nguyên dương $\displaystyle m$ đủ lớn sao cho $\displaystyle \mid S_m-S\mid<\epsilon/2$ và

$\displaystyle\sum_{k=m+1}^{+\infty}\mid u_k\mid <\epsilon/2,$

trong đó $\displaystyle (S_n)_{n\geq 1}$ là dãy các tổng riêng của chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ .

Xét một song ánh $\displaystyle\sigma :\mathbb{N}^*\to\mathbb{N}^*$ . Gọi $\displaystyle (T_n)_{n\geq 1}$ là dãy các tổng riêng của chuỗi $\displaystyle\sum_{n=1}^{+\infty} u_{\sigma (n)}$ , và $\displaystyle N$ là một số nguyên dương sao cho các số $\displaystyle 1$ , $\displaystyle 2$ , $\displaystyle \ldots$ , $\displaystyle m$ đều thuộc tập hợp $\displaystyle\{\sigma (1),\sigma (2),\ldots,\sigma (N)\}.$ Với số nguyên $\displaystyle n>N$ , ta có

$\displaystyle \mid T_n-S\mid\leq \mid T_n-S_m\mid +\mid S_m-S\mid$

$\displaystyle\leq \sum_{k=m+1}^{+\infty}\mid u_k\mid +\mid S_m-S\mid<\epsilon/2+\epsilon/2=\epsilon.$

Suy ra $\displaystyle T_n\to S$ và ta có điều phải chứng minh. $\Box$

Bây giờ giả sử $\displaystyle (u_n)_{n\geq 1}$ là một dãy các số thực sao cho chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ hội tụ có điều kiện. Ta thấy có vô hạn số hạng của dãy là số dương, và có vô hạn số hạng của dãy là số âm. Gọi $\displaystyle (d_i)_{i\geq 1}$ và $(a_i)_{i\geq 1}$ lần lượt là dãy con tất cả các số hạng không âm và dãy con tất cả các số hạng âm của dãy $\displaystyle (u_n)_{n\geq 1}$ . Hai chuỗi $\displaystyle\sum_{n=1}^{+\infty}d_n$ và $\displaystyle\sum_{n=1}^{+\infty}a_n$ đều phân kỳ. Cố định một số thực $\displaystyle \alpha$ . Lấy ra khỏi $\displaystyle (d_i)$ một vài số hạng đầu có tổng lớn hơn $\displaystyle\alpha$ , sau đó lấy ra khỏi $\displaystyle (a_i)$ một vài số hạng đầu để tổng các số được chọn (gồm cả những số được chọn từ $\displaystyle (d_i)$ ) nhỏ hơn $\displaystyle \alpha$ . Tiếp theo, trong dãy $\displaystyle (d_i)$ còn lại, lấy vài số hạng đầu để tổng các số được lấy (gồm cả những số được chọn từ các bước trước) lớn hơn $\displaystyle\alpha$ , sau đó trong dãy $\displaystyle (a_i)$ còn lại, lấy một vài số hạng đầu để tổng các số được lấy (gồm cả những số được chọn từ các bước trước) nhỏ hơn $\displaystyle \alpha$ . Cứ tiếp tục như vậy ta có một chuỗi có tổng bằng $\displaystyle\alpha$ . Ta đã mô tả chứng minh của kết quả sau, chi tiết có trong [2].

Định lý 2 (Định lý chuỗi Riemann). Cho $\displaystyle (u_n)_{n\geq 1}$ là một dãy các số thực sao cho chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ hội tụ có điều kiện. Khi đó với mỗi số thực $\displaystyle\alpha$ , có song ánh $\displaystyle \sigma :\mathbb{N}^*\to\mathbb{N}^*$ sao cho chuỗi $\displaystyle \sum_{n=1}^{+\infty}u_{\sigma (n)}$ hội tụ và tổng của nó bằng $\displaystyle \alpha$ .