Định trị một đại lượng bằng hai cách [1]

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

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

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

của tập

. Ta có thể chọn một tập kích thước

bằng cách chọn

phần tử từ [m]

và

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 của [n] , các cột tương ứng với các tập con kích thước . 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

của

, 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

kích thước

trong phần giao của

và

. 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

:
$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 của ( $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 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 nằm liên tục trên một cung của .

Cách một: với mỗi $A \in \mathcal{A}$ , có tất cả đường tròn chứ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ó nhiều nhất là 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ị 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ử . 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.