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

Khi ta gặp tổng dạng ~\sum_{k=0}^n a_k~, ta có thể đặt ~S_n = \sum_{k=0}^n a_k~ và viết lại ~S_n~ dưới dạng hệ thức truy hồi như sau:

~S_0 = a_0~

~S_n = S_{n-1} + a_n~

Để tinh ~S_n~, ta có thể giải hệ thức truy hồi bằng các phương pháp đã biết (ví dụ như repertoire method)

Ví dụ: ~a_0 = \alpha, a_n = \beta + \gamma n~

Khi đó, tổng có thể được viết dưới dạng hệ thức truy hồi như sau

~R_0 = \alpha~

~R_n = R_{n-1} + \beta + \gamma n~

Tính thử ~R_0, R_1, R_2, ...~, ta thấy ~R_n = A(n)\alpha + B(n)\beta + C(n)\gamma~

Ta sẽ dùng repertoire method để giải hệ thức truy hồi này.

Khi ~R_n = 1~, ta có ~\alpha = 1, \beta = 0, \gamma = 0~.

Thay các giá trị này và ~R_n = 1~ vào ~R_n = A(n)\alpha + B(n)\beta + C(n)\gamma~, ta được ~A(n) = 1~

Khi ~R_n = n~, ta có ~\begin{cases} \alpha = 0 \\ n = (n-1) + \beta + \gamma n \end{cases} \Rightarrow \begin{cases} \alpha = 0 \\ \beta + \gamma n = 1 + 0n \end{cases} \Rightarrow \begin{cases} \alpha = 0 \\ \beta = 1 \\ \gamma = 0 \end{cases}~.

Thay các giá trị này và ~R(n) = n~ vào ~R_n = A(n)\alpha + B(n)\beta + C(n)\gamma~, ta được ~B(n) = n~

Khi ~R_n = n^2~, ta có ~\begin{cases} \alpha = 0 \\ n^2 = (n-1)^2 + \beta + \gamma n \end{cases} \Rightarrow \begin{cases} \alpha = 0 \\ 2n - 1 = \gamma n + \beta \end{cases} \Rightarrow \begin{cases} \alpha = 0 \\ \gamma = 2 \\ \beta = -1 \end{cases}~.

Thay các giá trị này và ~R(n) = n^2~ vào ~R_n = A(n)\alpha + B(n)\beta + C(n)\gamma~, ta được ~2C(n) - B(n) = n^2~

Giải hệ ~\begin{cases} A(n) = 1 \\ B(n) = n \\ 2C(n) - B(n) = n^2 \end{cases}~, ta được ~\begin{cases} A(n) = 1 \\ B(n) = n \\ C(n) = \frac{n^2 + n}{2} \end{cases}~

Ngược lại, nếu ta có một hệ thức truy hồi, ta có thể giải hệ thức truy hồi bằng cách tính tổng.

Ví dụ: Bài toán Tháp Hà Nội

~T_0 = 0~

~T_n = 2T_{n-1} + 1~

Chia hai vế cho ~2^n~, ta có

~\frac{T_0}{2^0} = 0~

~\frac{T_n}{2^n} = \frac{T_{n-1}}{2^{n-1}} + 2^{-n}~

Đặt ~S_n = \frac{T_n}{2^n}~, ta có:

~S_0 = 0~

~S_n = S_{n-1} + 2^{-n}~

dễ thấy ~S_n = \sum_{k=1}^n 2^{-k}~

Do ~(2^{-k})_{k=1}^\infty~ là một cấp số nhân, ta có thể dùng công thức để tính ra được ~S_n \sum_{k=1}^n 2^{-k} = 1 - 2^{-n} \Rightarrow T_n = 2^nS_n = 2^n - 1~

Ở ví dụ trên, ta nhân hai vế cho ~2^{-n}~. Liệu có cách nào để tổng quát hóa hằng số này hay không?

Câu trả lời là có. Xét hệ thức truy hồi ~T_n~ có dạng sau:

~a_n T_n = b_n T_{n-1} + c_n~

Giả sử ta cần giải hệ thức này bằng cách nhân hai vế với ~s_n~, khi đó

~s_n a_n T_n = s_n b_n T_{n-1} + s_n c_n~

Để có thể đặt ~S_n = s_n a_n T_n~ và quy về dạng ~S_n = S_{n-1} + s_n c_n~, ta cần có ~s_n b_n = s_{n-1} a_{n-1} \Rightarrow s_n = \frac{s_{n-1}a_{n-1}}{b_n} \Rightarrow \boxed{s_n = \frac{a_{n-1}a_{n-2}...a_1}{b_nb_{n-1}...b_2}}~

Lưu ý: Ta chỉ có thể áp dụng phương pháp khi ~s_n \ne 0~, hay ~\begin{cases} a_n \ne 0 \\ b_n \ne 0 \end{cases}~

Ví dụ: Số lần hoán đổi vị trí hai số kì vọng khi sắp xếp một mảng bằng thuật toán Quicksort

~C_0 = 0~

~C_n = n + 1 + \frac{2}{n} \sum_{k=0}^{n-1} C_k~

Ta cần tìm cách loại bỏ ~\frac{2}{n}~ và ~\sum_{k=0}^{n-1} C_k~

Ta có:

~C_n = n + 1 + \frac{2}{n} \sum_{k=0}^{n-1} C_k~

~\Rightarrow n C_n = n^2 + n + 2\sum_{k=0}^{n-1} C_k : (1)~

Công thức trên đúng với mọi ~n > 0~. Áp dụng công thức trên với ~n - 1 > 0~, ta có:

~(n-1)C_{n-1} = (n-1)^2 + (n-1) + 2\sum_{k=0}^{n-2} C_k : (2)~

Lấy ~(1) - (2)~, ta có:

~nC_n - (n-1)C_{n-1} = (n^2 - (n-1)^2) + (n - (n-1)) + 2(\sum_{k=0}^{n-1} C_k - \sum_{k=0}^{n-2} C_k)~

~\Rightarrow nC_n = (n+1)C_{n-1} + 2n : (3)~

Đặt ~a_n = n, b_n = n+1, c_n = 2n~, khi đó ta thấy có thể nhân hai vế với ~s_n~ để ra một hệ thức đẹp. Áp dụng công thức, ta có:

~s_n = \frac{a_{n-1}a_{n-2}...a_1}{b_nb_{n-1}...b_2} = \frac{(n-1)(n-2)...(1)}{(n+1)(n)...(3)} = \frac{2}{n(n+1)}~

Nhân hai vế của ~(3)~ với ~s_n~, ta có:

~\frac{2}{n+1}C_n = \frac{2}{n}C_{n-1} + \frac{4}{n+1}~

Đặt ~S_n = \frac{2}{n+1}C_n~, ta có ~S_n = S_{n-1} + \frac{4}{n+1}~

Dễ thấy ~S_n = \sum_{i=1}^n \frac{4}{n+1} \Rightarrow C_n = \frac{n+1}{2} \sum_{k=1}^n \frac{4}{k+1} = 2(n+1)\sum_{k=1}^n \frac{1}{k+1}~

Liệu có công thức nào cho ~\sum_{k=1}^n \frac{1}{k+1}~ hay không? Câu trả lời là không, nhưng vì biểu thức dạng này hay xuất hiện nên người ta đặt

~H_n = 1 + \frac{1}{2} + ... + \frac{1}{n} = \sum_{k=1}^n \frac{1}{k}~

Chữ ~H~ là viết tắt của từ harmonic, có nghĩa là "điều hòa". Dãy ~1, \frac{1}{2}, \frac{1}{3}, ...~ được gọi là dãy điều hòa.

Bây giờ, ta có thể viết lại ~C_n = 2(n+1)\sum_{1 \leq k \leq n} \frac{1}{k+1} = 2(n+1)\sum_{2 \leq k + 1 \leq n+1} \frac{1}{k+1} = 2(n+1)(H_{n} - 1 + \frac{1}{n+1}) = 2(n+1)H_n - 2(n+1) + 2 = \boxed{2(n+1)H_n - 2n}~

Bonus: Ta có thể dùng tích phân để chứng minh được ~H_n \in O(\log n)~, và đây cũng là lí do vì sao thuật toán Quicksort có độ phức tạp trung bình ~O(n \log n)~