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

1. Kí pháp Iverson

Để thuận tiện cho việc kết hợp tính đúng sai của mệnh đề với các biểu thức toán học khác, Iverson đã đề xuất kí hiệu sau:

~[\text{mệnh đề}] = \begin{cases} 0 \text{ nếu mệnh đề sai} \\ 1 \text{ nếu mệnh đề đúng} \end{cases}~

Lưu ý số ~0~ ở trong định nghĩa trên là số siêu ~0~. Khi thực hiện nhiều phép toán với số siêu ~0~ (ngoại trừ phép cộng, trừ), ta coi kết quả bằng ~0~.

Với kí hiệu này, ta có thể viết lại một số biểu thức chứa ~\sum~ như sau:

• ~\sum_{k=1}^n a_k = \sum_{1 \leq k \leq n} a_k = \sum_k [1 \leq k \leq n]a_k~
• ~\sum_{p \text{ nguyên tố}, p \leq N} \frac{1}{p} = \sum_p \frac{[p \text{ nguyên tố}][p \leq N]}{p}~. Lưu ý số hạng khi ~p = 0~ là ~\frac{0}{0}~ và ta coi kết quả bằng ~0~ do tử là số siêu ~0~.

Một số hằng đẳng thức đáng nhớ với kí pháp Iverson

• ~[p \text{ và } q] = [p][q]~. Nói cách khác, phép ~\text{AND}~ chính là phép nhân hai bit.
• ~[k \in K] + [k \in K'] = [k \in K \cap K'] + [k \in K \cup K']~.

Khi áp dụng hằng đẳng thức này với biểu thức chứa ~\sum~, đẳng thức này nghĩa là nếu ta cộng các phần tử của ~K~ một lần rồi cộng các phần tử của ~K'~ một lần thì điều này cũng giống việc cộng các phần tử của ~K~ hoặc ~K'~ một lần, rồi cộng các phần tử chung của hai phần tử này thêm một lần nữa.

Một cách nữa để thấy tính đúng đắn của hằng đẳng thức này là bằng cách vẽ biểu đồ Venn.

2. Pertubation Method

Khi tính tổng ~S_{n+1} = \sum_{k=1}^{n+1} a_k~ thì ta có thể áp dụng hằng đẳng thức thứ hai với ~(K, K') = (\{1\}, \{2, 3, 4, ..., n+1\})~ và với ~(K, K') = (\{1, 2, ..., n\}, \{n+1\})~ (nói cách khác, tách số hạng đầu và số hạng cuối ra khỏi tổng) để viết ~S_{n+1}~ theo hai cách để từ đó suy ra được công thức tổng quát của ~S~. Phương pháp này được gọi là pertubation method.

Ví dụ 1:

Tính ~S_n = \sum_{k=0}^n ax^k~

Ta có:

~S_{n+1} = \sum_{0 \leq k \leq n+1} ax^k = ax^0 + \sum_{1 \leq k \leq n+1} ax^k = a + \sum_{1 \leq k+1 \leq n+1} ax^{k+1} = a + x\sum_{0 \leq k \leq n}a^k = a + xS_n~

Lại có:

~S_{n+1} = S_n + ax^{n+1}~

Do đó, ~a + xS_n = S_n + ax^{n+1} \Rightarrow \boxed{S_n = \frac{a(x^{n+1} - 1)}{x - 1}}~

Ví dụ 2:

Tính ~S_n = \sum_{k=0}^n kx^k~

Ta có:

~S_{n+1} = 0 + \sum_{1 \leq k \leq n+1} kx^k = \sum_{1 \leq k+1 \leq n+1} (k+1)x^{k+1} = x(\sum_{1 \leq k+1 \leq n+1} (k+1)x^k) = x(\sum_{0 \leq k \leq n} kx^k + \sum_{0 \leq k \leq n} x^k) = x(S_n + \frac{x^{n+1} - 1}{x - 1})~

Lại có:

~S_{n+1} = S_n + (n+1)x^{n+1}~

Do đó ~x(S_n + \frac{x^{n+1} - 1}{x - 1}) = S_n + (n+1)x^{n+1} \Rightarrow (x-1)S_n = (n+1)x^{n+1} - x\frac{x^{n+1} - 1}{x - 1} \Rightarrow \boxed{S_n = \frac{(n+1)x^{n+1}}{x-1} - x\frac{x^{n+1} - 1}{(x-1)^2}}~

Bonus:

Một cách khác để tính ~S_n = \sum_{k=0}^n kx^k~ là bằng cách sử dụng đạo hàm.

Xét ~f(x) = \sum_{k=0}^n x^k = \frac{x^{n+1} - 1}{x - 1}~

~\Rightarrow f'(x) = \sum_{k=0}^n kx^{k-1} = \frac{nx^{n+1} - (n+1)n^k + 1}{(n-1)^2}~

~\Rightarrow xf'(x) = \boxed{\sum_{k=0}^n kx^k = \frac{nx^{n+2} - (n+1)x^{n+1} + x}{(x-1)^2}}~ (dễ dàng chứng minh được hai công thức bằng nhau bằng cách tính hiệu và so sánh với ~0~)

Ở một note trong tương lai, ta sẽ thấy được sự liên quan giữa việc tính tổng và đạo hàm, tích phân.