Một trong những ý tưởng sâu sắc nhất tôi học được trong Toán học là “định trị một đại lượng bằng hai cách“. Ta có thể dùng ý tưởng này để
- chứng minh rất nhiều các đẳng thức toán học
- tìm công thức (gọn) tính một biểu thức toán học
- chứng minh rất nhiều các bất đẳng thức toán học
Trong loạt bài này tôi ghi lại một số ví dụ minh họa ý tưởng này. Trong các ví dụ sau đây, ta dùng ký hiệu
[n] = \{1, \dots, n\}
Ví dụ 1: xét đẳng thức
\sum_{i=0}^n \binom{n}{i} = 2^n
Vế trái rõ là đếm tổng số các tập con của
[n]
(đếm theo
i
là kích thước tập con). Mỗi tập con tương ứng 1-1 với một vector trong
\mathbb{F}_2^n
, các phần tử của tập con tương ứng với thành phần bằng
1
trong vector. Có tổng cộng
2^n
vectors như vậy.
Ví dụ 2: đẳng thức sau đây thường được gọi là đẳng thức Vandermonde (Vandermonde’s convolution formula), là trường hợp đặc biệt của đẳng thức Chu-Vandermonde trong lý thuyết chuỗi siêu hình học (hypergeometric series):
\sum_{i=0}^k \binom{n}{k-i} \binom{m}{i} = \binom{m+n}{k}
Vế phải là tổng số các tập con kích thước
k
của tập
[m+n]
. Ta có thể chọn một tập kích thước
k
bằng cách chọn
i
phần tử từ
[m]
và
k-i
phần tử từ
[m+n]-[m]
. Đó là đại lượng mà vế trái tính.
Ví dụ 3: với các số nguyên dương
i \leq j \leq n
, định nghĩa ma trận
W_{ij}
như sau. Các hàng của
W_{ij}
được đánh số bằng các tập con kích thước
i
của
[n]
, các cột tương ứng với các tập con kích thước
j
. Và,
(W_{ij})_{X,Y} = \begin{cases} 1 & X \subseteq Y \\ 0 & X \not\subseteq Y \end{cases}
Ta sẽ chứng minh rằng
A = W_{ij}^TW_{ij}
là matrận positive semi-definite, và là positive definite nếu
i=j
. (Dĩ nhiên,
B^TB
luôn positive semi-definite vì
v^TB^TBv = |Bv|^2
, nhưng ta chứng minh bằng cách hơi khác.) Trước hết, với
X,Y
là các tập con kích thước
j
của
[n]
, ta có
a_{X,Y} = \binom{|X \cap Y|}{i}
Với vector
v \neq 0
bất kỳ (trong không gian thực
\binom{n}{j}
chiều), ta có
v^TAv = \sum_X \sum_Y \binom{|X \cap Y|}{i} v_Xv_Y
Đến đây, ta sẽ dùng ý tưởng “định trị một đại lượng theo hai cách”. Trong tổng trên, số lần xuất hiện của mỗi cặp
v_Xv_Y
bằng với tổng số tập con
I
kích thước
i
trong phần giao của
X
và
Y
. Như vậy, ta có thể viết lại cái tổng trên bằng cách nhóm các số hạng theo
I
:
v^TAv = \sum_{I : |I| = i} \sum_{X \supseteq I} \sum_{Y \supseteq I} v_Xv_Y
Đến đây thì ta xong vì
v^TAv = \sum_{I : |I| = i} \left( \sum_{X \supseteq I} v_X \right)^2 \geq 0
Ví dụ trên xuất hiện trong các chứng minh dùng đại số tuyến tính của định lý Ray-Chaudhuri–Wilson trong lý thuyết thiết kế (Design Theory).
Ví dụ 4: khi nhắc đến ý tưởng “định trị bằng hai cách”, không thể nào không nhắc đến định lý Erdos-Ko-Rado lừng danh và chứng minh của Katona. Định lý Erdos-Ko-Rado phát biểu như sau:
Gọi
\mathcal{A}là một bộ các tập con kích thước
kcủa
[n](
n \geq 2k) thỏa mãn điều kiện rằng hai thành viên bất kỳ của
\mathcal{A}đều giao nhau. Ta có,
|\mathcal{A}| \leq \binom{n-1}{k-1}
Chứng minh. Gọi
\mathcal{C}
là tập tất cả các cách xếp các số
1, \dots, n
trên một đường tròn (cyclic order). Có tất cả
(n-1)!
cách. Ta sẽ định trị đại lượng
s
sau đây bằng hai cách: tổng số các cặp
(A, C)
trong đó
A \in \mathcal{A}, C \in \mathcal{C}
, và các phần tử của
A
nằm liên tục trên một cung của
C
.
- Cách một: với mỗi
A \in \mathcal{A}, có tất cả
k!(n-k)!
đường tròn
C
chứa
A
liên tục trên một cung. Do đó,
s = |\mathcal{A}| k! (n-k)! - Cách hai: với mỗi đường tròn
C
, có nhiều nhất là
k
thành viên của
\mathcal{A}là cung của đường tròn, do từng cặp trong chúng phải giao nhau. Vì thế,
s \leq (n-1)!k
Ta suy ra kết quả
|\mathcal{A}| \leq \binom{n-1}{k-1}
từ hai cách định trị
s
như trên. Đẳng thức có thể đạt được bằng cách chọn
\mathcal{A}
là bộ tất cả các tập con chứa phần tử
1
. Ví dụ này cho thấy ta có thể dùng ý tưởng “định trị hai cách” để chứng minh bất đẳng thức.