Mình viết Appendix này mục đích để hỗ trợ cho loạt bài về các giải thuật ngẫu nhiên (randomized algorithms). Tính tổng và tích với mình luôn là bài toán đau đầu khi mới bắt đầu cho đến khi mình đọc Chương 1.2.3 của Knuth [1]. Do đó, bài này mình tổng hợp ngắn gọn Chương 1.2.3 của Knuth theo cách hiểu của bản thân. Mình khuyến khích bạn đọc đọc bản gốc tiếng anh của Knuth.

Ví dụ 1(từ Randomized Quick-Sort). Tính tổng:

$A(n) = \sum_{i=1}^n \sum_{j = i+1}^n \frac{1}{j-i+1} \qquad (1)$

Biết rằng:

$\sum_{i=1}^n \frac{1}{i} = H(n) \qquad (2)$

trong đó $H(n)$ là số đồng điều thứ $n$.

Lời giải. Có lẽ nếu bạn nào đã từng gặp tổng này thì có thể sẽ biết được các bước tính $A(n)$ như sau:

$\begin{array}{lcl} A(n) & = & \sum_{i=1}^n \sum_{k = 2}^{n-i+1} \frac{1}{k} \\ & = & \sum_{k=2}^n \sum_{i = 1}^{n-k+1} \frac{1}{k} \\ & = & \sum_{k=2}^n\frac{n-k+1}{k} \\ & = & (n+1)\sum_{k=2}^n\frac{1}{k} - \sum_{k=2}^n 1 \\ & = & (n+1)(H(n)-1) - (n-1) \\ & = & (n+1)H(n)- 2n \end{array} \qquad (3) $

Để thu được phương trình đầu tiên, ta đổi biến bằng cách đặt $k = j - i +1$. Do đó, điều kiện $j = i+1 \rightarrow n$ trở thành $k = 2 \rightarrow n-i+1$. Các phương trình ở dòng thứ 3,4,5 và 6 thì ta chỉ việc sử dụng các phép tách và nhóm cơ bản. Khó nhất là làm sao để thu được phương trình thứ 2; đổi chỗ biến chạy $i$ và $k$ từ trong ra ngoài. Tất nhiên việc kiểm chứng không phải là khó lắm vì chỉ cần viết ra. Cái khó là hiểu được trên cơ sở nào mà ta có thể đổi chỗ như vậy để ta có thể áp dụng vào các tình huống tương tự. Bài này chúng ta sẽ đi tìm hiểu cơ sở đó.

Một số tổng cơ bản

Phần này mình nhắc lại một số tổng cơ bản và cách chứng minh. Các tổng $B_p(n)$ dưới đây khá cổ điển nên mình không nhắc lại chứng minh nữa mà khuyến khích bạn đọc xem tại các liên kết đính kèm:

$\begin{array}{lcl} B_1(n) & = & \sum_{i=1}^n i = \frac{n(n+1)}{2} = O(n^2)\\ B_2(n) & = & \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = O(n^3)\\ B_3(n) & = & \sum_{i=1}^n i^3 = \left[\frac{n(n+1)}{2}\right]^2 = O(n^4)\\ & \ldots & \\ B_p(n) & = & \sum_{i=1}^n i^p = O(n^{p+1}) \end{array} \qquad (4) $

Tổng $B_1(n)$ gọi là tổng tam giác; tổng $B_2(n)$ gọi là tổng kim tự tháp; tổng $B_3(n)$ được gọi là tổng tam giác bình phương; tổng $B_p(n)$ được gọi là tổng Faulhaber do công thức tổng quát của nó, theo Wikipedia, được tìm ra bởi Faulhaber năm 1631.

Tổng $B_1(n)$ còn có thể được khái quát hóa cho trường hợp cấp số cộng (arithmetic progression). Một cấp số cộng $a_1,a_2,\ldots, a_n$ với công sai $d$ sẽ có tổng:

$AP_d(n) = a_1 + a_2 + \ldots a_n = \frac{n(a_1+a_n)}{2} \qquad (5)$

Dễ thấy nếu chọn $a_1 = 1$ và công sai $d = 1$ thì $AP_1(n)$ chính là tổng $B_1(n)$.

Chúng ta cũng đã biết tổng của một cấp số nhân (geometric progression) với công bội $r$ cũng có thể tính được dưới đạng đóng (closed form):

$GP_r(a,n) = a + ar^1 + ar^2 + \ldots + ar^n = a\frac{r^n-1}{r-1} \qquad (6)$

Tổng $GP_r(a,n)$ còn có thể được mở rộng hơn nữa để tìm tổng của tích của một cấp số cộng và một cấp số nhân (arithmetico-geometric sequence):

$\begin{array}{lcl} PGP_{d,r}(a,n) & = & a + (a+d)r^1 + (a+2d)r^2 + \ldots + (a+nd)r^n)\\ & = & \frac{a - (a+nd)r^{n+1}}{r-1} + \frac{rd(1-r^n)}{(1-r)^2} \end{array} \qquad (7) $

Nếu bạn đọc đã từng đọc bài về Heap nhị phân, trong phần phân tích xây dựng Heap từ một mảng ở cuối bài viết, mình có sử dụng tổng (có cả cách chứng minh) $PGP_{1,2}(0,n)$. Chứng minh công thức $(7)$ tương tự như cách chứng minh của mình với tổng $PGP_{1,2}(0,n)$ và coi như bài tập cho bạn đọc.

Mặc dù không có dạng đóng, số đồng điều thứ $n$ cũng có thể coi là một tổng cơ bản và đáng nhớ vì tổng này hay xuất hiện trong các phân tích thuật toán. Về mặt tiệm cận, $H(n) \sim \ln(n)$.

Do giới hạn chiều dài của bài viết, mình xin dừng liệt kê các tổng "cơ bản" ở đây. Bạn đọc có thể tham khảo thêm các tổng cơ bản khác và phương pháp chứng minh trong các sách [2],[3], [4].

Các hằng đẳng thức

Tổng (có thể không phải tất cả) các số hạng thuộc dãy $a_0, a_1,a_2, \ldots, a_n$ thường được viết dưới dạng ngắn gọn sử dụng kí hiệu $\Sigma$ như sau :

$\sum_{R(i)}a_i \qquad (8)$

trong đó $R(i)$ là một quan hệ của biến chạy $i$. Ví dụ $a_0 + a_2 + \ldots a_{2\lfloor n/2 \rfloor}$ là tổng các hạng có chỉ số chẵn có thể viết ngắn gọn thành dạng $(8)$ với quan hệ của biến chạy $i$ là $R(i) : i$ là các số chẵn . Dạng ngắn gọn đó không chỉ dễ nhìn hơn mà còn cho phép chúng ta phát triển các hằng đẳng thức đáng nhớ để thao tác với nó.

Hằng đẳng thức I-Luật phân phối:

$\left(\sum_{R(i)}a_i \right)\left(\sum_{S(j)}b_j \right) = \sum_{R(i)}\sum_{S(j)} a_ib_j\qquad (9)$

Trong đó $R(i)$ và $S(j)$ lần lượt là quan hệ của biến chạy $i$ và $j$ và hai quan hệ này độc lập với nhau. Ở đây mình nhấn mạnh từ độc lập.

Thông thường, trong các bài toán, ta sẽ phải tính tổng bên về phải và sử dụng $(9)$ đưa về vế trái để tính. Ví dụ tính tổng:

$ C(n) = \sum_{i=1}^n\sum_{j=1}^n ij^2 \qquad (10)$

Tổng $C(n)$ nhìn có vẻ phức tạp nhưng thực rất đơn giản. Áp dụng $(9)$, ta có thể đưa tổng $C_n$ về dạng:

$\begin{array} {l} C(n) & = \sum_{i=1}^n i \sum_{j=1}^n j^2 \\ & = \frac{n(n+1)}{2}\frac{n(n+1)(2n+1)}{6} = O(n^5) \end{array}$

trong đó, phương trình cuối cùng ta thu được là nhờ tổng $B_1(n)$ và $B_2(n)$.

Hằng đẳng thức II-Luật đổi biến:

$\sum_{R(i)}a_i = \sum_{R(j)}a_j = \sum_{R(f(i))}a_{f(i)} \qquad (11)$

Ở đây, $f(.)$ là một hàm tùy ý trên miền các số nguyên.

Phép đổi biến đầu tiên của $(11)$ chỉ đơn giản là đổi tên của biến. Ví dụ $\sum_{i=1}^n i$ và $\sum_{j=1}^n j$ đều là tổng $B_1(n)$ mặc dù ta dùng hai biến có "tên" khác nhau. Phép đổi biến thứ (2) thường hữu dụng hơn cả và cũng khó hiểu hơn một chút. Để hiểu hơn phép này, bạn đọc nên dừng đọc tiếp và xem lại phép đổi biến $k = j-i+1$ trong Ví dụ 1 để thu được phương trình đầu tiên trong $(3)$.

$\sum_{j = i+1}^n \frac{1}{j-i+1} = \sum_{k = 2}^{n-i+1} \frac{1}{k}$

Chi tiết phép đổi biến trong $(3)$ viết theo ngôn ngữ của hằng đẳng thức $(11)$ là như sau: Ta đặt $f(j) = j + i -1$. Ở đây $R(j) : i + 1 \leq j \leq n$ và $a_j = \frac{1}{j-i+1}$. Do đó:

$a_{f(j)} = \frac{1}{f(j)-i+1} = \frac{1}{(j+i-1)-i+1} = \frac{1}{j}$

và

$R(f(j)) : i+ 1 \leq j+i-1 \leq n$

Quan hệ này tương đương với $R(f(j)) : 2 \leq j \leq n$. Áp dụng $(11)$ ta sẽ thu được phép đổi biến ban đầu. Nếu bạn nào đã quen với tích phân thì có thể thấy phép đổi biến này giống như phép đổi biến của tích phân.

Hằng đẳng thức III-Luật đổi thứ tự độc lập:

Nếu $R(i)$ và $S(j)$ là hai quan hệ độc lập, ta có:

$\sum_{R(i)} \sum_{S(j)} a_{ij} = \sum_{S(j)} \sum_{R(i)} a_{ij} \qquad (12)$

Hằng đẳng thức IV-Luật đổi thứ tự phụ thuộc:

Nếu $R(i)$ là một quan hệ của $i$ và $S(i,j)$ là một quan hệ của $j$ phụ thuộc vào $i$, ta có:

$\sum_{R(i)} \sum_{S(i,j)} a_{ij} = \sum_{S'(j)} \sum_{R'(i,j)} a_{ij} \qquad (13)$

Trong đó: (i) $S'(j)$ là quan hệ của $j$ sao cho: tồn tại một số nguyên $i$ thỏa mãn cả hai quan hệ $R(i)$ và $S(i,j)$ và (ii) $R'(i,j)$ là quan hệ của $i$ sao cho cả $R(i)$ và $S(i,j)$ đều thỏa mãn. Phần in đậm chính là sự khác nhau cơ bản giữa $S'(j)$ và $R'(i,j)$.

Để hiểu hơn về hằng đẳng thức này, ta sẽ kiểm tra nó với $(3)$. Trong $(3)$, ta thực hiện đổi thứ tự như sau:

$\sum_{i=1}^n \sum_{j=2}^{n-i+1} \frac{1}{j} = \sum_{j=2}^n \sum_{i=1}^{n-j+1}\frac{1}{j} \qquad (14)$

Ở đây $R(i): 1 \leq i \leq n$ và $S(i,j) : 2 \leq j \leq n-i+1$.

Ta sẽ tìm $S'(j)$ trước. $S'(j)$ sẽ là quan hệ của $j$ sao cho tồn tại $i$ để $1 \leq i \leq n$ và $2 \leq j \leq n-i+1$. Trước hết ta thấy nếu $j$ < $2$ thì không tồn tại $i$ để bất đẳng thức $2 \leq j \leq n-i+1$ đúng. Với lí do tương tự thì $j \leq n$. Nếu ta cố định giá trị $j$ bất kì trong đoạn $[2,n]$ thì từ hai bất đẳng thức $1 \leq i \leq n$ và $j \leq n-i+1$, ta suy ra $1 \leq i \leq n+1-j$. Vì $j \leq n$, đoạn $[1,n+1-j]$ luôn không rỗng, do đó luôn tồn tại $i$ thỏa mãn $1 \leq i \leq n+1-j$. Như vậy, $S'(j) : 2 \leq j \leq n$.

Tìm $R'(i,j)$ thường sẽ dễ hơn. Theo định nghĩa: $R'(i,j)$ là quan hệ của $i$ sao cho $1 \leq i \leq n$ và $2 \leq j \leq n-i+1$. Ta suy ra $1 \leq i \leq n-j+1$. Do đó, $R'(i,j): 1 \leq i \leq n-j+1$. Áp dụng $(13)$ ta sẽ suy ra $(14)$.

Hằng đẳng thức V-Thao tác trên miền giá trị:

Nếu $R(i)$ và $S(j)$ là hai quan hệ độc lập, ta có:

$\sum_{R(i)}a_{i} + \sum_{S(i)} a_{i} = \sum_{R(i) \mbox{ or } S(i)}a_i + \sum_{R(i) \mbox{ and } S(i)} a_{i} \qquad (15)$

Ví dụ:

$\sum_{1}^m a_{i} + \sum_{i = m-1}^n a_{i} = \sum_{i=1}^na_i + \sum_{i=m-1}^m a_i = \sum_{i=1}^na_i + a_{m-1} + a_{m}$

Ví dụ áp dụng

Ví dụ 2: Chứng minh:

$\sum_{i=0}^n \sum_{j = 0}^i a_ia_j = \frac{1}{2}\left( \left(\sum_{i=0}^n a_i\right)^2 + \left(\sum_{i=0}^n a^2_i\right)\right) \qquad (16)$

Lời giải: Đặt

$S_1 = \sum_{i=0}^n \sum_{j = 0}^i a_ia_j$

Áp dụng phép thay đổi thứ tự phụ thuộc ta được:

$\begin{array} {l}S_1 & = \sum_{j=0}^n \sum_{i=j}^n a_{i}a_j \\ & = \sum_{i=0}^n \sum_{j=i}^n a_{i}a_j \end{array}$

Ở phương trình thứ hai, ta áp dụng phép đổi biến để đổi "tên" $i$ và $j$. Đặt:

$S_2 = \sum_{i=0}^n \sum_{ j= i}^n a_ia_j$

Ta có:

$\begin{array} {l}2S_1 & = S_1 + S_2 \\ & = \sum_{i=0}^n \left( \sum_{j = 0}^i a_ia_j + \sum_{j = i}^n a_ia_j \right) \\ &= \sum_{i=0}^n \left( \sum_{j = 0}^n a_ia_j + a_ia_i \right)\\ &= \sum_{i=0}^n \sum_{j = 0}^n a_ia_j + \sum_{i=0}^n a^2_i \\ &= \left(\sum_{i=0}^n a_i\right)\left(\sum_{j=0}^n a_j\right) + \sum_{i=0}^n a^2_i \\ &= \left(\sum_{i=0}^n a_i\right)^2 + \sum_{i=0}^n a^2_i \end{array}$

Từ đó ta suy ra dpcm.

Tham khảo

[1] . E. Knuth. The Art of Computer Programming, Volume 1 (3rd Ed.): Fundamental Algorithms. Chapter 1.2.3. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA. 1997.
[2] P. Flajolet and R. Sedgewick. Analytic combinatorics. Cambridge University Press, 2009.
[3] P. Marko, H. S. Wilf, and D. Zeilberger. A= B. AK Peters Ltd. Wellesley. MA 30 1996.
[4] R. P. Stanley. Enumerative Combinatorics. Wadsworth Publ. Co., Belmont, CA, USA. 1986.