Định trị một đại lượng bằng hai cách [1]
Ngô Quang Hưng | 31 tháng 03, 2006 | 
Bản để in
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\}](/blog/latexrender/pictures/f7d04fd3caea4a343277ab774ce1641d.gif "[n] = \{1, \dots, n\}")
Ví dụ 1: xét đẳng thức
Vế trái rõ là đếm tổng số các tập con của
![[n]](/blog/latexrender/pictures/de504dafb2a07922de5e25813d0aaafd.gif "[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 
, 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 
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):
Vế phải là tổng số các tập con kích thước
của tập ![[m+n]](/blog/latexrender/pictures/b39af570f65f46a219ce52b7bb2b5414.gif "[m+n]")
. Ta có thể chọn một tập kích thước bằng cách chọn phần tử từ ![[m]](/blog/latexrender/pictures/efc831aabf9ade051f781ccb54c2dcdb.gif "[m]")
và 
phần tử từ ![[m+n]-[m]](/blog/latexrender/pictures/8e53abc3b5e1458dbbe2c550a8ba34b0.gif "[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 
, định nghĩa ma trận 
như sau. Các hàng của được đánh số bằng các tập con kích thước của , các cột tương ứng với các tập con kích thước 
. Và,
Ta sẽ chứng minh rằng
là matrận positive semi-definite, và là positive definite nếu 
. (Dĩ nhiên, 
luôn positive semi-definite vì 
, nhưng ta chứng minh bằng cách hơi khác.) Trước hết, với 
là các tập con kích thước của , ta có
Với vector
bất kỳ (trong không gian thực 
chiều), ta có
Đế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
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 :
Đến đây thì ta xong vì
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
là một bộ các tập con kích thước
) thỏa mãn điều kiện rằng hai thành viên bất kỳ của
Chứng minh. Gọi 
là tập tất cả các cách xếp các số 
trên một đường tròn (cyclic order). Có tất cả 
cách. Ta sẽ định trị đại lượng 
sau đây bằng hai cách: tổng số các cặp 
trong đó 
, 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
, có tất cả 
đường tròn chứa liên tục trên một cung. Do đó, 
- Cách hai: với mỗi đường tròn , có nhiều nhất là thành viên của là cung của đường tròn, do từng cặp trong chúng phải giao nhau. Vì thế,
Ta suy ra kết quả từ hai cách định trị như trên. Đẳng thức có thể đạt được bằng cách chọn 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.
