Note này được dựa trên Concrete Mathematics, 2.4

1. Một vài tính chất cơ bản của ~\sum~ nhiều biến

• ~\sum_{P(j,k)} a_{j,k} = \sum_{j} \sum_k a_{j,k}[P(i,j)] = \sum_k \sum_j a_{jk}[P(j,k)]~ với ~P(j,k)~ là một mệnh đề chứa biến ~j, k~
• ~\sum_{j \in J, k \in K} a_jb_k = (\sum_{j \in J} a_j)(\sum_{k \in K} b_k)~. Lưu ý, ~J~ không được phụ thuộc vào ~k~, ~K~ không được phụ thuộc vào ~j~
• ~\sum_{j \in J} \sum_{k \in K(j)} a_{j,k} = \sum_{k \in K'}\sum_{j \in K'(j)} a_{j,k}~ khi ~[j \in J][k \in K(j)] = [k \in K'][j \in J'(k)]~. Ở bài này, ta sẽ làm quen với một số hằng đẳng thức Iverson có thể được sử dụng liên quan đến tính chất này.

Ví dụ, do ~[1 \leq j \leq n][j \leq k \leq n] = [1 \leq j \leq k \leq n] = [1 \leq k \leq n][1 \leq j \leq k]~ mà

~\sum_{j=1}^n \sum_{k=j}^n a_{j,k} = \sum_{j} \sum_k [1 \leq j \leq n][j \leq k \leq n]a_{j,k} = \sum_j \sum_k [1 \leq k \leq n][1 \leq j \leq k] a_{j,k} = \sum_k \sum_j [1 \leq k \leq n][1 \leq j \leq k] a_{j,k} = \sum_{k=1}^n \sum_{j=1}^k a_{j,k}~

~\Rightarrow \boxed{\sum_{j=1}^n \sum_{k=j}^n a_{j,k} = \sum_{k=1}^n \sum_{j=1}^k a_{j,k}}~

2. Tính tổng bằng cách sử dụng hằng đẳng thức Iverson

Ví dụ 1: Tính tổng ~\sum_{1 \leq j \leq k \leq n} a_ja_k~

Xét ma trận sau ~\begin{bmatrix} a_1a_1 & a_1a_2 & ... & a_1a_n \\ a_2a_1 & a_2a_2 & ... & a_2a_n \\ ... & ... & ... & ... \\ a_na_1 & a_na_2 & ... & a_na_n \\ \end{bmatrix}~

Ta thấy tổng cần tính là tổng các số nằm ở phía trên đường chéo ~a_1a_1, a_2a_2, ..., a_na_n~ của ma trận này (bao gồm cả đường chéo). Do tính chất giao hoán của phép nhân, ma trận này có tính đối xứng và vì thế ta nghĩ đến việc tính ~\sum_{1 \leq j \leq k \leq n} a_ja_k~ bằng cách tính tổng tất cả các phần tử của ma trận rồi cộng trừ nhân chia thích hợp.

Ta có:

~\sum_{1 \leq j \leq k \leq n} a_ja_k = \sum_{1 \leq k \leq j \leq n} a_ka_j~ (đổi biến)

~\sum_{1 \leq j \leq k \leq n} a_ja_k = \sum_{1 \leq k \leq j \leq n} a_ja_k~ (sử dụng tính chất giao hoán)

Ta thấy vế phải là tổng các số nằm ở phía dưới đường chéo của ma trận (bao gồm cả đường chéo).

Ta thấy nếu lấy hai tổng các số nằm phía trên và tổng các số nằm phía dưới cộng lại thì ta sẽ được tổng tất cả các số trong ma trận và tổng của đường chéo. Ta có thể biểu diễn quan sát này bằng một hằng đẳng thức Iverson như sau:

~[1 \leq j \leq k \leq n] + [1 \leq k \leq j \leq n] = [1 \leq j, k \leq n] + [1 \leq j = k \leq n]~

Áp dụng hằng đẳng thức này, ta có:

~\sum_{1 \leq j \leq k \leq n} a_ja_k + \sum_{1 \leq k \leq j \leq n} a_ja_k = \sum_{1 \leq j, k \leq n} a_ja_k + \sum_{1 \leq j = k \leq n} a_ja_k~

~\Rightarrow 2\sum_{1 \leq j \leq k \leq n} a_ja_k = (\sum_{1 \leq j \leq n} a_j)(\sum_{1 \leq k \leq n} a_k) + \sum_{1 \leq j \leq n} a_j^2~

~\Rightarrow 2\sum_{1 \leq j \leq k \leq n} a_ja_k = (\sum_{1 \leq j \leq n} a_j)^2 + \sum_{1 \leq j \leq n} a_j^2~

~\Rightarrow \boxed{\sum_{1 \leq j \leq k \leq n} a_ja_k = \frac{(\sum_{1 \leq j \leq n} a_j)^2 + \sum_{1 \leq j \leq n} a_j^2}{2}}~

Ví dụ 2:

Tính ~S = \sum_{1 \leq j < k \leq n} (a_j - a_k)(b_j - b_k)~

Nhận xét: ~(a_j - a_k)(b_j - b_k) = (-1)(a_k - a_j)(-1)(b_k - b_j) = (a_k - a_j)(b_k - b_j)~, như vậy mỗi số hạng có tính đối xứng. Do đó ta sẽ làm tương tự ví dụ 1 nhưng có thay đổi một chút vì điều kiện ~j < k~

Ta có: ~S = \sum_{1 \leq j < k \leq n} (a_j - a_k)(b_j - b_k) = \sum_{1 \leq k < j \leq n} (a_k - a_j)(b_k - b_j) = \sum_{1 \leq k < j \leq n} (a_j - a_k)(b_j - b_k)~

Do đó, ~2S = \sum_{1 \leq j < k \leq n} (a_j - a_k)(b_j - b_k) + \sum_{1 \leq k < j \leq n} (a_j - a_k)(b_j - b_k)~

Sử dụng hằng đẳng thức Iverson ~[1 \leq j < k \leq n] + [1 \leq k < j \leq n] = [1 \leq j,k \leq n] - [1 \leq j=k \leq n]~ (hãy nghĩ xem tại sao nó đúng), ta có:

~2S = \sum_{1 \leq j,k \leq n} (a_j - a_k)(b_j - b_k) + \sum_{1 \leq k=j \leq n} (a_j - a_k)(b_j - b_k)~

~2S = \sum_{1 \leq j,k \leq n} (a_jb_j - a_kb_j - a_jb_k + a_kb_k) + \sum_{1 \leq j \leq n} (a_j - a_j)(b_j - b_j)~

~2S = \sum_{1 \leq j,k \leq n} a_jb_j - \sum_{1 \leq j,k \leq n} a_kb_j - \sum_{1 \leq j,k \leq n} a_jb_k + \sum_{1 \leq j,k \leq n} a_kb_k~

~2S = 2\sum_{k=1}^n \sum_{j=1}^n a_jb_j - 2(\sum_{j=1}^n a_j)(\sum_{j=1}^n b_j)~

~2S = 2n\sum_{j=1}^n a_jb_j - 2(\sum_{j=1}^n a_j)(\sum_{j=1}^n b_j)~

~\Rightarrow S = \boxed{\sum_{1 \leq j < k \leq n} (a_j - a_k)(b_j - b_k) = n\sum_{j=1}^n a_jb_j - (\sum_{j=1}^n a_j)(\sum_{j=1}^n b_j)}~

Từ đẳng thức trên, ta có: ~(\sum_{j=1}^n a_j)(\sum_{j=1}^n b_j) = n\sum_{j=1}^n a_jb_j - \sum_{1 \leq j < k \leq n} (a_j - a_k)(b_j - b_k)~

Đây chính là tiền đề để ta chứng minh bất đẳng thức Chebyshev với dãy đơn điệu:

~(\sum_{j=1}^n a_j)(\sum_{j=1}^n b_j) \leq n\sum_{j=1}^n a_jb_j~ khi cả dãy ~a~ và ~b~ đều không giảm hoặc đều không tăng. Khi đó với ~j < k~, ~(a_j - a_k)(b_j - b_k) \geq 0 \Rightarrow - \sum_{1 \leq j < k \leq n} (a_j - a_k)(b_j - b_k) \leq 0~

~(\sum_{j=1}^n a_j)(\sum_{j=1}^n b_j) \geq n\sum_{j=1}^n a_jb_j~ khi một dãy không giảm, một dãy không tăng. Khi đó với ~j > k~, ~(a_j - a_k)(b_j - b_k) \leq 0 \Rightarrow - \sum_{1 \leq j < k \leq n} (a_j - a_k)(b_j - b_k) \geq 0~

và bất đẳng thức Chebyshev với hàm đơn điệu

~(\int_a^b f(x) dx)(\int_a^b g(x) dx) \geq (b-a)\int_a^b f(x)g(x)dx~ với ~f(x), g(x)~ là hai hàm không giảm.

3. Tính tổng bằng cách "đếm"

Giả sử ta có hàm ~f: J \rightarrow K~. Khi đó:

~\sum_{j \in J} a_{f(j)} = \sum_{k \in K} a_{k}|f^{-1}(k)|~

với ~f^{-1}(k) = \{j \in J | f(j) = k\}~ (lưu ý đây là một tập hợp)

Dễ dàng chứng minh được công thức trên bằng ~\sum~ nhiều biến như sau:

~\sum_{j \in J} a_{f(j)} = \sum_{j \in J, k \in K, k = f(j)} a_k = \sum_{j \in J, k \in K} a_k[f(j) = k] = \sum_{k \in K} a_k \sum_{j \in J} [f(j) = k]~

Do ~\sum_{j \in J} [f(j) = k] = |f^{-1}(k)|~ nên ta kết luận được ~\sum_{j \in J} a_{f(j)} = \sum_{k \in K} a_{k}|f^{-1}(k)|~

Một ứng dụng đơn giản của công thức trên là dùng để tính tổng một dãy số nguyên mà có khoảng giá trị bị giới hạn.

Ví dụ: Cho dãy số nguyên ~a_n~ thỏa mãn ~1 \leq a_n \leq 5~. Tính ~\sum_{j=0}^n a_j~

Đặt hàm ~f: [0, n] \rightarrow [1, 5], n \mapsto a_n~ (hàm ~f~ giống hệt dãy ~a~). Đặt dãy ~b_n = n~.

Khi đó ~\sum_{j=0}^n a_j = \sum_{j \in [0,n]} f(j) = \sum_{j \in [0,n]} b_{f(j)} = \sum_{k \in [1,5]} b_k|f^{-1}(k)| = \sum_{k \in [1,5]} k|f^{-1}(k)|~

với ~|f^{-1}(k)|~ chính là số lần số ~k~ xuất hiện trong dãy ~a~.

Tùy vào bài toán mà việc đếm số lần xuất hiện trong dãy ~a~ của từng giá trị có thể sẽ dễ dàng hơn, nhờ đó việc sử dụng công thức dạng ~\sum_{k \in [1,5]} k|f^{-1}(k)|~ sẽ dễ dàng hơn dùng công thức dạng ~\sum_{j=0}^n a_j~

4. Phương pháp triệt tiêu một biến

Ví dụ: Tính tổng ~S = \sum_{1 \leq j < k \leq n} \frac{1}{k - j}~

Ta sẽ thử biến đổi ~S~ theo cách thông thường

~S = \sum_{1 \leq k \leq n} \sum_{1 \leq j < k} \frac{1}{k - j}~

~S = \sum_{1 \leq k \leq n} \sum_{1 \leq (k-j) < k} \frac{1}{k - (k-j)}~ (thay ~j~ bằng ~k-j~ để triệt tiêu ~k~)

~S = \sum_{1 \leq k \leq n} \sum_{0 < j \leq k-1} \frac{1}{j}~

~S = \sum_{1 \leq k \leq n} H_{k-1}~

~S = \sum_{0 \leq k-1 \leq n-1} H_{k-1} = \sum_{0 \leq k \leq n-1} H_k~

Giờ thì ta đã hiểu được ý nghĩa của ~S~ là tổng của ~k~ số hạng đầu tiên trong dãy điều hòa, nhưng mà chúng ta chưa có công thức tổng quát cho dãy này.

Ta thấy ở cách làm trước, phần thay ~j~ bằng ~k-j~ được thực hiện ở bước 2, bây giờ ta sẽ thử thực hiện một điều tương tự nhưng ở bước đầu tiên.

~S = \sum_{1 \leq k-j < k \leq n} \frac{1}{j}~

Ta thấy:

• Chỉ còn một biến ~j~. Để triệt tiêu ~k~, ta sẽ để ~\sum_j~ ở bên ngoài, ~\sum_k~ ở bên trong. Làm như vậy thì ~\sum_k~ sẽ biến thành một phép nhân với thừa số ~\frac{1}{j}~ và một thừa số là độ dài khoảng giá trị của ~k~ (mà cái này phụ thuộc vào ~j~ nên ta sẽ triệt tiêu được ~k~)
• Do ~k - j < k~ nên ~j \geq 1~. Ngoài ra, do ~\begin{cases} k \leq n \\ k-j \geq 1 \end{cases}~ nên ~j \leq n-1~
• Khi ~j~ chạy từ 1 đến ~n-1~, ~k~ sẽ chạy được từ ~j+1~ đến ~n~.

Ta giờ có thể viết lại ~S~ như sau:

~S = \sum_{j=1}^{n-1} \sum_{k=j+1}^n \frac{1}{j}~

~S = \sum_{j=1}^{n-1} \frac{n-j}{j} = \sum_{j =1}^{n-1} (\frac{n}{j} - 1)~

~S = n(\sum_{j =1}^{n-1} \frac{1}{j}) - (n-1)~

~S = nH_{n-1} - (n-1)~

Trong sách, ~S = nH_n - n~. Liệu hai công thức này có giống nhau không. Xét hiệu, ta có:

~(nH_n - n) - (nH_{n-1} - (n-1)) = n(H_n - H_{n-1}) - (n - (n-1)) = n(\frac{1}{n}) - 1 = 1 - 1 = 0~

Do đó, hai công thức ~\boxed{S = nH_{n-1} - (n-1)}~ và ~\boxed{S = nH_n - n}~ đều đúng.

Ngoài ra, nhờ việc tính thử không thành công ở đầu, ta tình cờ có được một hằng đẳng thức về dãy số điều hòa

~\boxed{\sum_{k=0}^{n-1} H_k = nH_n - n}~