Note này được dựa trên Concrete Mathematics, 3.3, và bài viết về bài toán Josephus trên CP-Algorithms .

Xét bài toán Josephus dạng tổng quát.

Cho ~n~ người đứng thành một vòng tròn, mỗi người được đánh số từ 1 đến ~n~. Bắt đầu từ vị trí số 1, mỗi người sẽ đếm lần lượt 1, 2, ..., ~k~, người đếm ~k~ sẽ bị loại khỏi vòng tròn, và mọi người tiếp tục đếm lại từ ~1~ cho đến khi chỉ còn lại một người. Hỏi người đánh số nào là người ở lại vòng tròn cuối cùng.

Một ý tưởng để giải quyết bài toán này là khi mỗi người đếm mà không bị loại, ta gán số thứ tự mới bằng số thứ tự lớn nhất hiện tại cộng ~1~. Ví dụ minh họa một vài lượt đếm với ~n = 10~, ~k = 3~

• Người ~1~ đếm ~1~ và không bị loại, ta gán số thứ tự mới ~11~ (kí hiệu ~1 \rightarrow 11~)
• Người ~2~ đếm ~2~ và không bị loại, ta gán số thứ tự mới ~12~ (kí hiệu ~2 \rightarrow 12~)
• Người ~3~ đếm ~3~ và bị loại, ta không gán số thứ tự mới (kí hiệu ~3 \rightarrow \emptyset~)
• ~4 \rightarrow 13~
• ~5 \rightarrow 14~
• ~6 \rightarrow \emptyset~
• ...

Ta thấy người bị loại sẽ có số thứ tự lần lượt là ~k~, ~2k~, .... Do cuối cùng cả ~n~ người bị loại, người bị loại cuối cùng sẽ có số thứ tự ~nk~.

Để các công thức tính toán sau này, ta sẽ đánh số lại mọi người theo thứ tự từ ~nk~ về ~1~. Ví dụ, khi ~n = 10~, ~k = 3~ thì ban đầu ~n~ người sẽ có số thứ tự lần lượt là ~30, 29, 28, ..., 21~. Một vài lượt chơi ban đầu như sau:

• ~30 \rightarrow 20~
• ~29 \rightarrow 19~
• ~28 \rightarrow \emptyset~
• ~27 \rightarrow 18~
• ~26 \rightarrow 17~
• ~25 \rightarrow \emptyset~

Người ở lại vòng tròn cuối cùng sẽ có số thứ tự cuối cùng là ~1~. Giờ ta chỉ cần tìm lại số thứ tự ban đầu của người này là giải quyết được bài toán.

Giả sử ~x~ là số thứ tự của một người nào đó trong vòng tròn. Khi tìm số thứ tự trước đó của người ~x~, kí hiệu là ~x'~, ta sẽ cần xử lí hai trường hợp:

• Nếu ~x \geq nk - n + 1~ thì ~x~ là số thứ tự ban đầu, vì thế sẽ không có số thứ tự trước đó.
• Trường hợp ~x < nk - n + 1~, ta có thể chia các số từ ~nk~ đến ~1~ thành những nhóm ~k~ số liên tiếp nhau (gọi tắt là nhóm ~k~, minh họa bằng cách đóng khung chữ nhật), và chia các số từ ~nk - n~ đến ~1~ thành những nhóm ~k-1~ số liên tiếp nhau (gọi tắt là nhóm ~k-1~, minh họa bằng cách khoanh tròn).

Đánh số các nhóm theo thứ tự từ ~0~. Trong nội bộ mỗi nhóm, ta cũng đánh số thứ tự từ ~0~.

Với mọi ~x < nk - n + 1~, nếu ~x~ là số thứ ~i~ nhóm ~k-1~ thứ ~j~ thì ~x'~ là số thứ ~i~ của nhóm ~k~ thứ ~j~ (dễ thấy điều này ở một số số ~x~ ngay sau số ~nk - n + 1~, cỏn các số sau nữa thì ta có thể chứng minh bằng quy nạp được). Vậy ta chỉ cần tìm ~i~ và ~j~ là ra ~x'~.

Ta tính được:

~x~ thuộc nhóm ~k-1~ thứ ~\lfloor \frac{nk - n - x}{k-1} \rfloor~

Số thứ tự của ~x~ trong nhóm ~k-1~ là ~nk - n - x - (k-1)\lfloor \frac{nk - n - x}{k-1} \rfloor~

~x'~ sẽ là số thứ ~nk - n - x - (k-1)\lfloor \frac{nk - n - x}{k-1} \rfloor~ của nhóm ~k~ thứ ~\lfloor \frac{nk - n - x}{k-1} \rfloor~, vậy

~x' = nk - k\lfloor \frac{nk - n - x}{k-1} \rfloor - (nk - n - x - (k-1)\lfloor \frac{nk - n - x}{k-1} \rfloor)~

~x' = n + x - \lfloor \frac{n(k - 1) - x}{k-1} \rfloor~

~x' = n + x - \lfloor n - \frac{x}{k-1} \rfloor~

Vận dụng tính chất ~\lfloor x + y \rfloor = x + \lfloor y \rfloor~ khi ~x \in \mathbb{Z}~ để đưa ~n~ ra ngoài hàm làm tròn xuống, ta có:

~x' = x - \lfloor -\frac{x}{k-1} \rfloor~

Vận dụng tiếp tính chất ~\lfloor -x \rfloor = -\lceil x \rceil~, ta có:

~x' = x + \lceil \frac{x}{k-1} \rceil~

~x' = \lceil \frac{x(k-1)}{k-1} + \frac{x}{k-1} \rceil~

~\boxed{x' = \lceil \frac{k}{k-1} x \rceil}~

Từ hai trường hợp trên, ta ra được thuật toán sau để tìm số thứ tự của người ở lại vòng tròn cuối cùng

Đọc n, k
Gán x = 1
While x < nk - k + 1:
    x = ceil(k/(k-1) * x)

# x là số thứ tự ban đầu nếu ta đánh số ngược, ta cần tìm số thứ tự ban đầu khi đánh số thuận
Gán x = nk + 1 - x
In ra x

Thuật toán trên có độ phức tạp ~O(\log_{\frac{k}{k-1}}(nk))~. Với ~k = 10^5, n = 10^{18}~, thuật toán này sẽ chỉ tốn khoảng ~6 \times 10^7~ phép tính và hoàn toàn có thể chạy dưới ~1~ giây, trong khi thuật toán duyệt thông thường sẽ mất đến ~O(nk)~ phép tính (hay khoảng ~10^{17}~ phép tính)

Vậy là ta đã giải quyết được bài toán trong trường hợp ~n~ lớn, ~k~ khá lớn. Vậy nếu như ta phải giải bài toán trong trường hợp ~k~ lớn, ~n~ khá lớn thì ta làm thế nào?

Gọi ~J_{n,k}~ là người ở lại vòng tròn cuối cùng nếu ta đánh số các người chơi từ ~0~ đến ~n-1~. Ta mô phỏng lại trò chơi bằng máy tính với một số giá trị ~n, k~ nhỏ rồi lập bảng. Ta sẽ thấy được quy luật

~J_{n, k} = (J_{n-1, k} + k) \text{ mod } n~

Từ công thức này, ta sẽ tính được ~J_{n,k}~ với độ phức tạp ~O(n)~, không phụ thuộc vào ~k~

Rất tiếc là ở thời điểm hiện tại, các nhà khoa học máy tính vẫn chưa tìm ra được cách giải quyết "dưới 1 giây" của bài toán này trong trường hợp cả ~n~ và ~k~ đều rất lớn.

Dựa trên Concrete Mathematics, 3.2

1. Đếm số giá trị nguyên trong một tập liên tục

Ở trong đề thi Đại học, ta thường gặp các câu hỏi tính số giá trị nguyên của ~m~ sao cho một phương trình nào đó có nghiệm. Khi giải các câu hỏi dạng này, ta thường ra được kết quả là ~m~ thuộc một tập liên tục (đoạn, khoảng, nửa đoạn) đó với các đầu mút là số nguyên hay số thực. Vậy, ta làm thế nào để đếm được số giá trị nguyên với rủi ro bị sai sót là thấp nhất có thể.

Giả sử ~m \in (a, b]~. Khi đó ~a < m \leq b~.

Theo các bất đẳng thức ta đã học ở bài trước, bất đẳng thức này tương đương với ~\lfloor a \rfloor < m \leq \lfloor b \rfloor~.

Do ~\lfloor \alpha \rfloor~ là số nguyên nên bất đẳng thức này tương đương với ~\lfloor a \rfloor + 1 \leq m \leq \lfloor b \rfloor~

Số số nguyên ~m~ thỏa mãn bất đẳng thức này là ~\lfloor b \rfloor - (\lfloor a \rfloor + 1) + 1 = \lfloor b \rfloor - \lfloor a \rfloor~

Làm tương tự như trên, ta sẽ có những công thức sau để đếm số số nguyên trong một tập liên tục:

• ~[a,b]~: Số giá trị nguyên là ~\lfloor b \rfloor - \lceil a \rceil + 1~
• ~[a,b)~: Số giá trị nguyên là ~\lceil b \rceil - \lceil a \rceil~
• ~(a,b]~: Số giá trị nguyên là ~\lfloor b \rfloor - \lfloor a \rfloor~
• ~(a,b)~: Số giá trị nguyên là ~\lceil b \rceil - \lfloor a \rfloor - 1~

Lưu ý là công thức chỉ đúng khi ~a \leq b~, và khi ta dùng công thức cho ~(a,b)~ thì ~a < b~. Trong trường hợp không thể áp dụng được công thức, ta coi số số nguyên bằng ~0~.

2. Tổng chứa hàm làm tròn

Trong casino có một trò chơi như sau:

• Nhà cái bốc ngẫu nhiên một số nguyên từ 1 đến 1000. Gọi số này là ~n~.
• Nếu ~n~ chia hết cho ~\lfloor \sqrt[3]{n} \rfloor~ thì nhà cái sẽ phải trả thưởng ~5~ nghìn đồng cho người chơi, còn nếu không thì người chơi sẽ phải trả nhà cái ~1~ nghìn đồng

Hãy tính xem người chơi có thể kì vọng có lãi nếu chơi trò chơi này rất nhiều lần hay không?

Gọi số số nguyên ~n~ thỏa mãn ~1 \leq n \leq 1000~ và ~n~ chia hết cho ~\lfloor \sqrt[3]{n} \rfloor~ là ~W~. Ta sẽ tính lợi nhuận kì vọng ~E~ của người chơi theo ~W~.

Ta có tổng cộng ~1000~ trường hợp của ~n~.

Có ~W~ trường hợp nhà cái sẽ phải trả thưởng ~5~ nghìn đồng.

Có ~1000-W~ trường hợp người chơi mất ~1~ nghìn đồng, tức được ~-1~ nghìn đồng.

Vậy lợi nhuận kì vọng của người chơi là ~E = \frac{5W - (1000 - W)}{1000} = \frac{6W - 1000}{1000}~

Người chơi có lãi khi ~E > 0 \Leftrightarrow 6W - 1000 > 0 \Leftrightarrow W > \frac{1000}{6} \Leftrightarrow W \geq 167~

Bây giờ ta sẽ tính ~W~. Sử dụng kí pháp Iverson, ta có:

~W = \sum_{n} [1 \leq n \leq 1000][n \text{ chia hết cho } \lfloor \sqrt[3]{n} \rfloor]~

Do ~n \text{ chia hết cho } \lfloor \sqrt[3]{n} \rfloor \Leftrightarrow \exists m \in \mathbb{Z}: n = m\lfloor \sqrt[3]{n} \rfloor~ nên

~W = \sum_{n, m} [1 \leq n \leq 1000][n = m\lfloor \sqrt[3]{n} \rfloor]~

~W = \sum_{n, m, k} [1 \leq n \leq 1000][k = \lfloor \sqrt[3]{n} \rfloor][n = mk]~

~W = \sum_{n, m, k} [1 \leq n \leq 1000][k \leq \sqrt[3]{n} < k+1][n = mk]~

~W = \sum_{n, m, k} [1 \leq n < 1001][k^3 \leq n < (k+1)^3][n = mk]~

~W = \sum_{n, m, k} [\max(1,k^3) \leq n < \min(1001, (k+1)^3)][n = mk]~

Giờ ta sẽ loại bỏ một biến. Để tránh vòng luẩn quẩn (sau khi biến đổi ta có lại biểu thức ban đầu), ta sẽ loại bỏ biến ~n~. Khi đó:

~W = \sum_{m, k} [\max(1,k^3) \leq mk < \min(1001, (k+1)^3)]~

Để đi tiếp, ta tìm cách tách các trường hợp của ~\max, \min~

Xét ~\max(1, k^3)~. Ta thấy ~1 \leq k^3 \Leftrightarrow 1 \leq k~. Vì thế nếu ~k = 0~, ~\max(1, k^3) = 1~, nếu ~k \geq 1~, ~\max(1, k^3) = k^3~

Xét ~\min(1001, (k+1)^3)~. Ta thấy ~1001 \leq (k+1)^3 \Leftrightarrow \sqrt[3]{1001} \leq k+1 \Leftrightarrow \lceil \sqrt[3]{1001} \rceil \leq k+1 \Leftrightarrow 11 \leq k+1 \Leftrightarrow k \geq 10~. Do đó nếu ~k \geq 10~ thì ~\min(1001, (k+1)^3) = 1001~, còn nếu ~k < 10~ thì ~\min(1001, (k+1)^3) = (k+1)^3~

Vậy ta xét ~k~ trong các trường hợp ~k = 0~, ~1 \leq k < 10~, và ~k \geq 10~

~W = \sum_m [1 \leq 0 < 1] + \sum_{m, k} [1 \leq k < 10][k^3 \leq mk < (k+1)^3] + \sum_{m, k} [k \geq 10][k^3 \leq mk < 1001]~

~W = 0 + \sum_{m, k} [1 \leq k < 10][k^2 \leq m < \lceil \frac{(k+1)^3}{k} \rceil] + \sum_{m, k} [k \geq 10][k^2 \leq m < \frac{1001}{k}]~

~W = \sum_{k} [1 \leq k < 10] \sum_m [m \in [k^2,\frac{(k+1)^3}{k})] + \sum_{k} [k \geq 10] \sum_m [m \in [k^2, \frac{1001}{k})]~

Giờ ta có thể áp dụng công thức đếm số số nguyên trong một tập liên tục để tính ~\sum_m [m \in [k^2,\frac{(k+1)^3}{k})]~ và ~\sum_m [m \in [k^2, \frac{1001}{k})]~, tuy nhiên trước đó ta phải kiểm tra điều kiện áp dụng công thức.

Dễ thấy ~k^2 \leq \frac{(k+1)^3}{k}~ khi ~1 \leq k < 10~, nên ta luôn có thể áp dụng được công thức cho tổng đầu tiên.

Với tổng thứ hai, ~k^2 \leq \frac{1001}{k} \Leftrightarrow k^3 \leq 1001 \Leftrightarrow k \leq \lfloor \sqrt[3]{1001} \rfloor \Leftrightarrow k \leq 10~. Kết hợp với ~k \geq 10~, ta thấy ta chỉ áp dụng được công thức khi ~k = 10~

Vậy

~W = \sum_{1 \leq k < 10} (\lceil \frac{(k+1)^3}{k} \rceil - \lceil k^2 \rceil) + \lceil \frac{1001}{10} \rceil - \lceil 10^2 \rceil~

~W = \sum_{1 \leq k < 10} (\lceil \frac{(k+1)^3}{k} - k^2 \rceil) + 101 - 100~

~W = \sum_{1 \leq k < 10} (\lceil 3k + 3 + \frac{1}{k} \rceil) + 1~

~W = \sum_{1 \leq k < 10} (3k + 3 + \lceil \frac{1}{k} \rceil) + 1~

Dễ thấy ~\forall k > 0: \lceil \frac{1}{k} \rceil = 1~ nên

~W = \sum_{1 \leq k < 10} (3k + 4) + 1~

~W = \frac{(7 + 31) \cdot 9}{2} + 1~ (dãy ~(3k+1)_{k=1}^9~ là dãy cấp số cộng có công thức tổng bằng (số đầu cộng số cuối) nhân số số hạng rồi chia đôi)

~\boxed{W = 172}~

Do ~W = 172 > 167~ nên người chơi sẽ có lãi khi chơi trò chơi này.

Bây giờ giả sử nhà cái bốc một số nguyên từ ~1~ đến ~N~ (ví dụ ~N = 10^9~). Liệu nhà cái và người chơi có tính trước được số trường hợp nhà cái phải trả thưởng cho người chơi để từ đó tính được nhà cái hay người chơi sẽ có lợi hay không?

Để giải đáp câu hỏi này, ta cần tổng quát hóa công thức trên bằng cách thay ~1000~ thành một số nguyên dương ~N~ bất kì. Khi đó,

~W = \sum_{m, k} [\max(1,k^3) \leq mk < \min(N+1, (k+1)^3)]~ (vì ở các bước trước ta không động đến hằng số ~1000~)

Xét ~\max(1,k^3)~. Ta thấy nếu ~k = 0~ thì ~\max(1, k^3) = 1~, nếu ~k \geq 1~ thì ~\max(1,k^3) = k^3~

Xét ~\min(N+1, (k+1)^3)~.

~N+1 < (k+1)^3 \Leftrightarrow \sqrt[3]{N+1} < k+1 \Leftrightarrow \lfloor \sqrt[3]{N+1} \rfloor - 1 < k~.

Vậy nếu ~k > \lfloor \sqrt[3]{N+1} \rfloor - 1~ thì ~\min(N+1, (k+1)^3) = N+1~, còn nếu ~k \leq \lfloor \sqrt[3]{N+1} \rfloor - 1~ thì ~\min(N+1, (k+1)^3) = (k+1)^3~.

Để đỡ lằng nhằng, ta giả sử ~\lfloor \sqrt[3]{N+1} \rfloor - 1 \geq 1 \Leftrightarrow \sqrt[3]{N+1} \geq 2 \Leftrightarrow N+1 \geq 8 \Leftrightarrow N \geq 7~. Nếu ~N < 7~, ta tính tay thay vì sử dụng công thức tổng quát.

Khi đó

~W = \sum_{m} [1 \leq 0 < 1] + \sum_{m,k} [1 \leq k \leq \lfloor \sqrt[3]{N+1} \rfloor - 1][k^3 \leq mk < (k+1)^3] + \sum_{m,k} [k \geq \lfloor \sqrt[3]{N+1} \rfloor][k^3 \leq km < N+1]~

~W = \sum_{k} [1 \leq k \leq \lfloor \sqrt[3]{N+1} \rfloor - 1] \sum_m [m \in [k^2, \frac{(k+1)^3}{2})] + \sum_{k} [k \geq \lfloor \sqrt[3]{N+1} \rfloor] \sum_m [m \in [k^2, \frac{N+1}{k})]~

Kiểm tra điều kiện sử dụng công thức đếm số số nguyên trong một tập liên tục. Ta thấy ta luôn có thể sử dụng được công thức cho tổng đầu tiên. Với tổng thứ hai:

~k^2 \leq \frac{N+1}{k} \Leftrightarrow k^3 \leq N+1 \Leftrightarrow k \leq \sqrt[3]{N+1}~

nên ta chỉ sử dụng được công thức khi ~k=\lfloor \sqrt[3]{N+1} \rfloor~

Để ngắn gọn, đặt ~K = \lfloor \sqrt[3]{N+1} \rfloor~

Khi đó

~W = \sum_{k=1}^{K-1} (\lceil \frac{(k+1)^3}{2} \rceil - \lceil k^2 \rceil) + \lceil \frac{N+1}{K} \rceil - \lceil K^2 \rceil~

~W = \sum_{k=1}^{K-1} (3k+4) + \lceil \frac{N+1}{K} \rceil - K^2~

~\boxed{W = \frac{(8 + 3K)(K-1)}{2} + \lceil \frac{N+1}{K} \rceil - K^2}~

Với công thức tổng quát này, ta có thể tính được ~W~ trong ~O(1)~ hoặc ~O(\log N)~ thay vì ~O(N)~.

Dựa trên Concrete Mathematics, 3.1

1. Làm tròn lên, làm tròn xuống

Ta định nghĩa các kí hiệu sau:

~\lfloor x \rfloor~ - số nguyên lớn nhất không vượt quá ~x~. Kí hiệu này đọc là "phần nguyên của ~x~" hoặc "~x~ làm tròn xuống"

Ví dụ: ~\lfloor 1.2 \rfloor = 1, \lfloor -0.8 \rfloor = -1~.

Lưu ý rằng với số âm thì các ngôn ngữ lập trình khác nhau có thể định nghĩa "làm tròn xuống khác nhau", ta sẽ thống nhất sử dụng định nghĩa trên cho dễ biến đổi.

~\lceil x \rceil~ - số nguyên nhỏ nhất không nhỏ hơn ~x~. Kí hiệu này đọc là "~x~ làm tròn lên"

Ví dụ: ~\lceil 1.2 \rceil = 2, \lceil -0.8 \rceil = 0~

Để dễ nhìn tính chất của hai hàm làm tròn, ta vẽ đồ thị các hàm số ~y = \lfloor x \rfloor, y = \lceil x \rceil~ và ~y = x~ trên cùng một hệ trục tọa độ

Dễ thấy:

~x = \lfloor x \rfloor \Leftrightarrow x \in \mathbb{Z} \Leftrightarrow x = \lceil x \rceil~

~\lceil x \rceil - \lfloor x \rfloor = [x \in \mathbb{Z}]~

~x - 1 < \lfloor x \rfloor \leq x \leq \lceil x \rceil < x + 1~

Ta thấy khi lấy đối xứng đồ thị hàm số ~y = \lfloor x \rfloor~ thì ta được ~y = \lceil x \rceil~, vì thế nên:

~\lfloor -x \rfloor = - \lceil x \rceil~ và ~\lceil -x \rceil = - \lfloor x \rfloor~

Ngoài ra

~\lfloor x \rfloor = n \Leftrightarrow n \leq x < n+1 \Leftrightarrow x-1 < n \leq x-1~

~\lceil x \rceil = n \Leftrightarrow n-1 < x \leq n \Leftrightarrow x \leq n < x+1~

Ta có thể cộng một số nguyên ở trong hay ở ngoài hàm làm tròn lên lẫn làm tròn xuống

~\lfloor x + n \rfloor = \lfloor x \rfloor + n~ với ~n \in \mathbb{Z}~

~\lceil x + n \rceil = \lceil x \rceil + n~ với ~n \in \mathbb{Z}~

Lưu ý điều này không đúng với phép nhân (~\lfloor nx \rfloor \ne n \lfloor x \rfloor~ sai khi ~n = 2~ và ~x = \frac{1}{2}~)

Với ~n~ là số nguyên, ta cũng dễ dàng chứng minh được các phép biến đổi tương đương sau:

~x < n \Leftrightarrow \lfloor x \rfloor < n~

~n < x \Leftrightarrow n < \lceil x \rceil~

~x \leq n \Leftrightarrow \lfloor x \rfloor \leq n~

~n \leq x \Leftrightarrow n \leq \lceil x \rceil~

Người ta còn định nghĩa ~\{x\} = x - \lfloor x \rfloor~ (~\{x\}~ được đọc là "phần thập phân của ~x~"). Nếu một số thực ~x = n + \theta~ với ~n, \theta~ thỏa mãn ~n~ nguyên và ~0 \leq \theta < 1~ thì ta biết được ~n = \lfloor x \rfloor~ và ~\theta = \{x\}~

2. Bài tập ứng dụng

Ví dụ 1:

Sử dụng khái niệm phần thập phân và tính chất ~\lfloor x + n \rfloor = \lfloor x \rfloor + n~ với ~n \in \mathbb{Z}~, ta có thể chứng minh được tính chất sau:

~\lfloor x + y \rfloor~ chỉ có thể là ~\lfloor x \rfloor + \lfloor y \rfloor~ hoặc ~\lfloor x \rfloor + \lfloor y \rfloor + 1~

Ta có:

~\lfloor x + y \rfloor = \lfloor \lfloor x \rfloor + \{x\} + \lfloor y \rfloor + \{y\} \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + \lfloor \{x\} + \{y\} \rfloor~

Do ~0 \leq \{x\}, \{y\} < 1~ nên ~0 \leq \{x\} + \{y\} < 2~, và vì thế nên ~\lfloor \{x\} + \{y\} \rfloor~ chỉ có thể là ~0~ hoặc ~1~.

Nếu ~\lfloor \{x\} + \{y\} \rfloor = 0~, ~\lfloor x + y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor~

Nếu ~\lfloor \{x\} + \{y\} \rfloor = 1~, ~\lfloor x + y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + 1~

Ví dụ 2:

Tính ~\lfloor \lg 35 \rfloor~ (do độ phổ biến của logarithm cơ số 2 trong Tin học, ta kí hiệu ~\log_2~ bằng ~\lg~)

Ta có:

~2^5 \leq 35 < 2^6 \Rightarrow 5 \leq \lg 35 < 6 \Rightarrow \lfloor \lg 35 \rfloor = 5~

Ví dụ 3:

Cho hàm ~f~ liên tục và đồng biến thỏa mãn ~f(x) \in \mathbb{Z} \Rightarrow x \in \mathbb{Z}~.

Khi đó, ~\lfloor f(x) \rfloor = \lfloor f(\lfloor x \rfloor) \rfloor~.

Tương tự, ta cũng có ~\lceil f(x) \rceil = \lceil f(\lceil x \rceil) \rceil~

Chứng minh:

Đặt ~m = \lfloor f(\lfloor x \rfloor) \rfloor~.

Khi đó ~m \leq f(\lfloor x \rfloor) < m+1~ (phá dấu làm tròn xuống ở ngoài bằng định nghĩa)

Do ~x \geq \lfloor x \rfloor~ và ~f~ đồng biến, ta có ~f(x) \geq f(\lfloor x \rfloor) \Rightarrow f(x) \geq m~

Để chứng minh ~\lfloor f(x) \rfloor = m~, ta giờ chỉ cần chứng minh ~f(x) < m+1~. Ta sẽ chứng minh điều này bằng phản chứng.

Giả dụ ~f(x) \geq m+1~.

Khi đó do ~\begin{cases} f(\lfloor x \rfloor) < m+1 \leq f(x) \\ f \text{ liên tục} \end{cases}~, theo định lí giá trị trung gian, ta sẽ tìm được ~c~ thỏa mãn ~f(c) = m+1~ và ~\lfloor x \rfloor < c \leq x~

Theo giả thiết ~f(x) \in \mathbb{Z} \Rightarrow x \in \mathbb{Z}~, do ~f(c) = m+1 \in \mathbb{Z}~, ~c \in \mathbb{Z}~.

Như vậy, ta tìm được số nguyên ~c~ nằm giữa ~\lfloor x \rfloor~ và ~x~, nhưng lại không bằng ~\lfloor x \rfloor~. Điều này vô lí.

Do đó giả dụ ban đầu sai, nói cách khác, ~f(x) < m+1~ đúng.

Kết hợp ~\begin{cases} m \leq f(x) \\ f(x) < m+1 \end{cases}~, ta có ~\lfloor f(x) \rfloor = m \Rightarrow \lfloor f(x) \rfloor = \lfloor f(\lfloor x \rfloor) \rfloor~. Đây là điều phải chứng minh.

Hệ quả của ví dụ 3:

~\lfloor \sqrt{x} \rfloor = \lfloor \sqrt{\lfloor x \rfloor} \rfloor~

~\lfloor \frac{x + m}{n} \rfloor = \lfloor \frac{\lfloor x \rfloor + m}{n} \rfloor~ (~n~ dương)

Các công thức tương tự với hàm làm tròn lên cũng đúng

Ví dụ 4: Giải phương trình ẩn ~x~ sau: ~\lceil \sqrt{\lfloor x \rfloor} \rceil = \lceil \sqrt{x} \rceil~

Xét các trường hợp sau:

Trường hợp 1: ~\sqrt{x}~ nguyên, ~\sqrt{\lfloor x \rfloor}~ nguyên. Khi đó phương trình luôn đúng. Kết hợp điều kiện, ta được ~x = m^2~ với ~m \in \mathbb{Z}~

Trường hợp 2: ~\sqrt{x}~ nguyên, ~\sqrt{\lfloor x \rfloor}~ không nguyên. Trường hợp này không thể xảy ra. ~\sqrt{x}~ nguyên ~\Rightarrow x~ nguyên ~\Rightarrow \lfloor x \rfloor = x \Rightarrow \sqrt{\lfloor x \rfloor} = \sqrt{x}~ nguyên.

Trường hợp 3: ~\sqrt{x}~ không nguyên, ~\sqrt{\lfloor x \rfloor}~ nguyên. Khi đó, phương trình trở thành

~\sqrt{\lfloor x \rfloor} = \lfloor \sqrt{x} \rfloor + 1 \Leftrightarrow \sqrt{\lfloor x \rfloor} = \lfloor \sqrt{\lfloor x \rfloor} \rfloor + 1 > (\sqrt{\lfloor x \rfloor} - 1) + 1 \Leftrightarrow \sqrt{\lfloor x \rfloor} > \sqrt{\lfloor x \rfloor}~ (vô nghiệm)

Trường hợp 4: ~\sqrt{x}~ không nguyên, ~\sqrt{\lfloor x \rfloor}~ không nguyên. Khi đó, phương trình trở thành

~\lfloor \sqrt{\lfloor x \rfloor} \rfloor + 1 = \lfloor \sqrt{x} \rfloor + 1 \Leftrightarrow \lfloor \sqrt{\lfloor x \rfloor} \rfloor = \lfloor \sqrt{x} \rfloor~ (luôn đúng)

Kết hợp điều kiện, ta được ~\lfloor x \rfloor \ne m^2~ với ~m \in \mathbb{Z}~ (phần nguyên của ~x~ không là số chính phương)

Từ bốn trường hợp trên, ta kết luận tập nghiệm của phương trình ~\lceil \sqrt{\lfloor x \rfloor} \rceil = \lceil \sqrt{x} \rceil~ là

~S = \{m \in \mathbb{Z} | m^2\} \cup \{x \in \mathbb{R} | \forall m \in \mathbb{Z}: \lfloor x \rfloor \ne m^2 \}~

(số ~x~ là nghiệm của phương trình khi và chỉ khi ~x~ là số chính phương hoặc phần nguyên của ~x~ không là số chính phương)

Note được dựa trên Concrete Mathematics, 2.6

Ở lớp 11, 12 các bạn đã được học về các khái niệm "đạo hàm" và "tích phân". Các khái niệm này có những tính chất rất đẹp, giúp chúng ta đơn giản hóa việc tính toán giá trị lớn nhất, nhỏ nhất, diện tích, thể tích, ....

Tương tự, hai khái niệm "sai phân" và "tổng phân" cũng có những tính chất đẹp tương tự "đạo hàm, tích phân" và nhờ thế giúp ta tính tổng một cách đơn giản hơn.

1. Sai phân

Ta đã biết:

~f'(x) = \lim_{h \rightarrow 0} \frac{f(x+h) - f(x)}{h}~

Do khi tính tổng, ~h~ là số nguyên nên khi ~h \rightarrow 0~ thì ~h~ chỉ có thể là ~1~ hoặc ~-1~. Để đơn giản hóa, ta coi ~h=1~ để có định nghĩa sau

~\Delta(f(x)) = f(x+1) - f(x)~

~\Delta(f(x))~ đọc là "sai phân của ~f~ tại điểm ~x~"", hoặc gọn hơn là "sai phân của ~f(x)~"

Ta có tính chất sau của đạo hàm: ~(x^m)' = mx^{m-1}~

Ta sẽ thử tính sai phân của ~x^3~ xem sai phân liệu có thể có tính chất tương tự hay không.

~\Delta(x^3) = (x+1)^3 - x^3 = 3x^2 + 3x + 1~

Kết quả này không đẹp và dễ nhớ như ~(x^3)' = 3x^2~, vì vậy khi làm việc với sai phân, ta cần loại lũy thừa đặc biệt gọi là "lũy thừa giảm" (hay còn gọi là "giai thừa giảm")

~x^{\underline{m}} = x(x-1)(x-2)...(x-m+1)~

Ta thấy đây là tích của ~m~ thừa số giảm dần ~x~, ~x-1~, ..., ~x-m+1~. Kí hiệu ~x^{\underline{m}}~ đọc là "~x~ mũ ~m~ giảm"

Ta thử tính sai phân của ~x^{\underline{m}}~

~\Delta(x^{\underline{m}}) = (x+1)^{\underline{m}} - x^{\underline{m}} = (x+1)x(x-1)(x-2)...(x-m+2) - x(x-1)(x-2)...(x-m+1) = x(x-1)(x-2)...(x-m+2)[(x+1) - (x-m+1)]~

~\Delta(x^{\underline{m}}) = mx(x-1)(x-2)...(x-m+2) = mx^{\underline{m-1}}~

Vậy ta có công thức đẹp và dễ nhớ ~\boxed{\Delta(x^{\underline{m}}) = mx^{\underline{m-1}}}~

Ở trên chúng ta mới định nghĩa lũy thừa giảm với số mũ dương. Ta sẽ định nghĩa lũy thừa giảm cho số mũ không dương như sau để tính chất đóng hộp ở trên đúng.

~x^{\underline{0}} = 1~

~x^{\underline{-m}} = \frac{1}{(x+1)(x+2)(x+3)...(x+m)}~ (~m > 0~)

Sau khi định nghĩa được lũy thừa giảm cho mọi số nguyên, ta giờ có được công thức nhân hai lũy thừa giảm

~\boxed{x^{\underline{n+m}} = x^{\underline{n}}(x-n)^{\underline{m}}}~

Đồng thời, ta cũng có công thức sau (giống công thức khai triển nhị thức Newton)

~(x+y)^{\underline{n}} = \sum_{k=0}^n C_n^k x^{\underline{k}}y^{\underline{n-k}}~

Một tính chất đẹp nữa của đạo hàm là ~(e^x)' = e^x~. Liệu có một hàm ~f(x)~ nào thỏa mãn ~\Delta f(x) = f(x)~ hay không?

Ta có: ~\Delta f(x) = f(x) \Rightarrow f(x+1) - f(x) = f(x) \Rightarrow f(x+1) = 2f(x)~

Dễ thấy ~f(x) = 2^x~ là một hàm thỏa mãn ~f(x+1) = 2f(x)~, và vì thế ~\boxed{\Delta(2^x) = 2^x}~

Việc tính sai phân hàm mũ cũng khá đơn giản

~\Delta(c^x) = c^{x+1} - c^x \Rightarrow \boxed{\Delta(c^x) = (c-1)c^x}~

2. Tổng phân

Ta đã biết:

~\int_a^b f(x) dx = \lim_{n \rightarrow \infty} \sum_{i=1}^{n-1} (x_{i+1} - x_i)f(x_i)~

với ~x_i = a + \frac{i}{n+1}(b-a)~ (tức ~x_0, x_1, ..., x_n, x_{n+1}~ là các điểm trong đoạn ~[a,b]~ cách đều nhau)

(để dễ tưởng tượng và nhớ công thức này, lưu ý ~\sum_{i=1}^{n-1} (x_{i+1} - x_i)f(x_i)~ là tổng diện tích các hình chữ nhật dùng để ước lượng diện tích nằm dưới đồ thị hàm số ~f(x)~)

Ta lấy cảm hứng từ khái niệm tích phân để định nghĩa tổng phân như sau:

~\sum_a^b f(x) \delta x = f(a) + f(a+1) + ... f(b-1) = \sum_{k=a}^{b-1} f(k)~

Lưu ý tổng chỉ chạy từ ~a~ đến ~b-1~ để tổng phân có các tính chất giống tích phân sau:

• ~\sum_a^b f(x) \delta x + \sum_b^c f(x) \delta x = \sum_a^c f(x) \delta x~ (giống ~\int_a^b f(x)dx + \int_b^c f(x)dx = \int_a^c f(x)dx~)
• Nếu ~g(x) = \Delta(f(x))~ thì
  • ~\sum_a^b g(x) \delta x = f(x)]_a^b = f(b) - f(a)~ (giống nếu ~g(x) = f'(x)~ thì ~\int_a^b g(x) dx = f(x)]_a^b~)
  • Ta kí hiệu ~\sum g(x) \delta x = f(x) + C~ (giống nguyên hàm)

Chứng minh tính chất nếu ~g(x) = \Delta(f(x))~ thì ~\sum_a^b g(x) \delta x = f(x)]_a^b = f(b) - f(a)~

Ta có:

~\sum_a^b g(x) \delta x = \sum_{k=a}^{b-1} g(x) = \Delta(f(a)) + \Delta(f(a+1)) + \Delta(f(a+2)) + ... + \Delta(f(b-1))~

~\sum_a^b g(x) \delta x = (f(a+1) - f(a)) + (f(a+2) - f(a+1)) + (f(a+3) - f(a+2)) + ... + (f(b) - f(b-1))~

~\sum_a^b g(x) \delta x = f(b) - f(a)~

Từ các công thức tính sai phân ở trên, ta dễ dàng có được các công thức tính tổng phân sau:

• ~\sum x^{\underline{m}} \delta x = \frac{x^{\underline{m+1}}}{m+1} + C~ (đúng khi ~m \ne -1~)
• ~\sum c^x \delta x = \frac{c^x}{c-1} + C~ (đúng khi ~c \ne 1~). Khi ~c = 1~ thì ~\sum c^x \delta x = \sum 1 \delta x = x + C~

Bây giờ ta cần sửa công thức cho ~\sum x^{\underline{m}} \delta x~ khi ~m = -1~. Ở môn giải tích, ta biết

~\int x^{-1} dx = \ln |x| + C~

Tương tự, ta cũng có

~\sum x^{\underline{-1}} = H_x + C~ với ~H_x = \sum_{1 \leq k \leq x} \frac{1}{k}~

Điều này cho thấy ~H_x~ có nhiều tính chất giống với hàm ~\ln~. Người ta cũng đã chứng minh được ~|H_n - \ln n| < 1~ khi ~n~ đủ lớn.

3. Ứng dụng đơn giản của tổng phân

Xét bài toán tính ~\square_n = \sum_{0 \leq k \leq n} k^2~

Thoại nhìn thì có vẻ như bài toán trên không liên quan gì đến sai phân, tổng phân vì các tính chất ở trên chỉ dành cho lũy thừa giảm chứ không phải lũy thừa bình thường. Tuy nhiên, ta có thể chuyển ~k^2~ bằng tổng các lũy thừa giảm bằng công thức ~k^2 = k^{\underline{2}} + k^{\underline{1}}~

Ta có:

~\sum_{0 \leq k \leq n} k^2 = \sum_0^{n+1} k^2 \delta k = \sum_0^{n-1} (k^{\underline{2}} + k^{\underline{1}}) \delta k~

~\boxed{\sum_{0 \leq k \leq n} k^2 = [\frac{k^{\underline{3}}}{3} + \frac{k^{\underline{2}}}{2}]_0^{n+1}}~

Từ đây ta chỉ việc khai triển là ra một công thức cho ~\square_n~

Tương tự, ta có thể dùng công thức ~k^3 = k^{\underline{3}} + 3k^{\underline{2}} + k^{\underline{1}}~ để tính ~C_n = \sum_{0 \leq k \leq n} k^3~ như sau:

~C_n = \sum_0^{n+1} (k^{\underline{3}} + 3k^{\underline{2}} + k^{\underline{1}}) \delta k~

~C_n = [\frac{k^{\underline{4}}}{4} + k^{\underline{3}} + \frac{k^{\underline{2}}}{2}]_0^{n+1}~

Làm thế nào để ta tìm được các hệ số trong các công thức ~k^2 = k^{\underline{2}} + k^{\underline{1}}~ và ~k^3 = k^{\underline{3}} + 3k^{\underline{3}} + k^{\underline{1}}~. Câu trả lời là ta sử dụng số Sterling loại I (cái này cũng giống việc ta sử dụng số tổ hợp hay tam giác Pascal để tìm hệ số của các số hạng trong khai triển ~(a+b)^n~ vậy).

4. Sai phân của một tích, tổng phân từng phần

Xét sai phân của một tích hai hàm ~u~ và ~v~. Ta sẽ tìm cách tính ~\Delta(uv)~ từ ~u, v, \Delta(u), \Delta(v)~

~\Delta(uv) = u(x+1)v(x+1) - u(x)v(x) = u(x+1)v(x+1) + u(x+1)v(x) - u(x+1)v(x) - u(x)v(x)~

(việc cộng trừ ~u(x+1)v(x)~ đóng vai trò làm cầu nối giữa hai số hạng)

~\Delta(uv) = u(x+1)[v(x+1) - v(x)] + v(x)[u(x+1) - u(x)]~

~\Delta(uv) = u(x+1)\Delta(v) + v(x)\Delta(u)~

Để công thức này đẹp hơn, ta định nghĩa ~Eu(x) = u(x+1)~ (~E~ là viết tắt của từ "Extra" (thêm) trong tiếng Anh), ta có thể viết gọn công thức này lại như sau:

~\boxed{\Delta(uv) = Eu\Delta(v) + v\Delta(u)}~

Trong sách, công thức này là ~\boxed{\Delta(uv) = u\Delta(v) + Ev\Delta(u)}~. Mặc dù hai công thức này không đối xứng nhưng ta có thể chứng minh chúng bằng nhau.

Ở môn giải tích, công thức tính đạo hàm của một tích giúp ta có được công thức tính tích phân từng phần. Tương tự, ta cũng có công thức tính tổng phân từng phần như sau:

~\sum u\Delta(v) = uv - \sum Ev\Delta(u)~

Giống như công thức tính tích phân từng phần, ta thường sử dụng được công thức tính tổng phân từng phần nếu trong biểu thức cần tính, có một phần tính sai phân dễ và một phần tính tổng phân dễ.

Ví dụ 1: Tính ~\sum_{0 \leq k \leq n} k2^k~

Đầu tiên, ta tính ~\sum x2^x \delta x~

Đặt ~u(x) = x \Rightarrow \Delta(u) = 1~, ~\Delta(v) = 2^x \Rightarrow v = 2^x \Rightarrow Ev = 2^{x+1}~

Khi đó: ~\sum x2^x \delta x = x2^x - \sum 2^{x+1} \delta x = x2^x + 2^{x+1} + C~

vì thế mà ~\sum_{0 \leq k \leq n} k2^k = \sum_0^{n+1} x2^x \delta x = [x2^x + 2^{x+1}]_0^{n+1}~

Ví dụ 2: Tính ~\sum_0^n H_x \delta x~

Ta thấy ~H_x~ là một phần dễ tính sai phân, vì thế nên ta đặt

~u(x) = H_x \Rightarrow \Delta(u) = x^{\underline{-1}}~

~\Delta(v) = 1 \Rightarrow v = x^{\underline{1}} = x\Rightarrow Ev = (x+1)^{\underline{1}}~

Ta có: ~\sum H_x \delta x = xH_x - \sum (x+1)^{\underline{1}}x^{\underline{-1}} \delta x~

~\sum H_x \delta x = xH_x - \sum 1 \delta x~

~\sum H_x \delta x = xH_x - x + C~

Từ đó dễ dàng tính được ~\boxed{\sum_0^n H_x \delta x = nH_n - n}~

Ví dụ 3: Tính ~\sum_0^n xH_x \delta x~

Đặt:

~u(x) = H_x \Rightarrow \Delta(u) = x^{\underline{-1}}~

~\Delta(v) = x \Rightarrow v = \frac{x^{\underline{2}}}{2} \Rightarrow Ev = \frac{(x+1)^{\underline{2}}}{2}~

Ta có:

~\sum xH_x \delta x = \frac{x^{\underline{2}}}{2}H_x - \sum \frac{(x+1)^{\underline{2}}x^{\underline{-1}}}{2} \delta x~

~\sum xH_x \delta x = \frac{x^{\underline{2}}}{2}H_x - \frac{1}{2} \sum x \delta x~

~\sum xH_x \delta x = \frac{x^{\underline{2}}}{2}H_x - \frac{x^{\underline{2}}}{4} + C~

Từ đó dễ dàng tính được ~\boxed{\sum_0^n xH_x \delta x = \frac{n^{\underline{2}}}{2}H_n - \frac{n^{\underline{2}}}{4}}~

5. Tổng hợp kiến thức

~\Delta(x^{\underline{m}}) = mx^{\underline{m-1}} \Rightarrow \sum x^{\underline{m}} \delta x = \frac{x^{\underline{m+1}}}{m+1} + C~

(Đặc biệt: ~\Delta(H_x) = x^{\underline{-1}} \Rightarrow \sum x^{\underline{-1}} \delta x = H_x + C~)

~\Delta(c^x) = (c-1)c^x \Rightarrow \sum c^x \delta x = \frac{c^x}{c-1} + C~

(Đặc biệt: ~\Delta(2^x) = 2^x \Rightarrow \sum 2^x \delta x = 2^x + C~)

~\Delta(cf) = c\Delta(f) \Rightarrow \sum cf = c \sum f~ (~c~ là hằng số)

~\Delta(f + g) = \Delta(f) + \Delta(g) \Rightarrow \sum (f + g) = \sum f + \sum g~

~\Delta(fg) = f\Delta(g) + Eg\Delta(f) \Rightarrow \sum f\Delta(g) = fg - \sum Eg\Delta(f)~

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

Ta xét bài toán tính ~\square_n = \sum_{0 \leq k \leq n} k^2~

0. OEIS

Ta có thể tính các giá trị ~\square_n~ với ~n = 0, 1, 2, 3, 4, 5~, rồi sử dụng trang oeis.org để tra công thức.

1. Đoán công thức, chứng minh bằng quy nạp

Đây là phương pháp cơ bản trong sách giáo khoa, tuy nhiên vấn đề chính là các bạn cần biết cách đoán.

2. Pertubation method

Ta sẽ thử áp dụng pertubation method để tính ~\square_n~

Ta có:

~\square_{n+1} = \square_n + (n+1)^2~

~\square_{n+1} = 0 + \sum_{1 \leq k \leq n+1} k^2 = \sum_{1 \leq k+1 \leq n+1} (k+1)^2 = \sum_{0 \leq k \leq n} (k^2 + 2k + 1) = \square_n + 2\sum_{0 \leq k \leq n} k + \sum_{0 \leq k \leq n} 1 = \square_n + 2\sum_{0 \leq k \leq n} k + n+1~

Do đó, ~\square_n + (n+1)^2 = \square_n + 2\sum_{0 \leq k \leq n} k + n+1 \Rightarrow 2\sum_{0 \leq k \leq n} k = (n+1)^2 - (n+1)~

~\square_n~ biến mất nên phương án này thất bại.

Tuy nhiên, ta có thể để ý thấy là ta có thể thu được công thức cho ~\sum_{0 \leq k \leq n} k~ tử việc áp dụng pertubation method cho ~\square_n~. Vì thế, ta có ý tưởng áp dụng pertubation method cho ~C_n = \sum_{0 \leq k \leq n} k^3~ để ra được công thức của ~\square_n~

Ta có:

~C_{n+1} = C_n + (n+1)^3~

~C_{n+1} = 0 + \sum_{1 \leq k \leq n+1} k^3 = \sum_{1 \leq k+1 \leq n+1} (k+1)^3 = \sum_{0 \leq k \leq n} (k^3 + 3k^2 + 3k + 1) = C_n + 3\square_n + 3\frac{n(n+1)}{2} + (n+1)~

Do đó ~C_n + (n+1)^3 = C_n + 3\square_n + 3\frac{n(n+1)}{2} + (n+1) \Rightarrow \boxed{\square_n = \frac{(n+1)^3 - 3\frac{n(n+1)}{2} - (n+1)}{3} = \frac{n(n+1)(2n+1)}{6}}~

3. Repertoire method

Chúng ta sẽ thử tìm công thức tổng quát cho công thức truy hồi sau:

~R_0 = \alpha~

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

Đặt ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~

Giả sử ~R_n = 1~. Khi đó ~\begin{cases} \alpha = 1 \\ 1 = 1 + \beta + \gamma n + \delta n^2 \Rightarrow \beta + \gamma n + \delta n^2 = 0 + 0n + 0n^2 \end{cases} \Rightarrow \alpha = 1, \beta = 0, \gamma = 0, \delta = 0~.

Thế vào ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~, ta có ~\boxed{A(n) = 1}~

Giả sử ~R_n = n~. Khi đó ~\begin{cases} \alpha = 0 \\ n = (n-1) + \beta + \gamma n + \delta n^2 \end{cases} \Rightarrow \alpha = 0, \beta = 1, \gamma = 0, \delta = 0~.

Thế vào ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~, ta có ~\boxed{B(n) = n}~

Giả sử ~R_n = n^2~. Khi đó ~\begin{cases} \alpha = 0 \\ n^2 = (n-1)^2 + \beta + \gamma n + \delta n^2 \end{cases} \Rightarrow \alpha = 0, \beta = -1, \gamma = 2, \delta = 0~.

Thế vào ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~, ta có ~2C(n) - B(n) = n^2 \Rightarrow \boxed{C(n) = \frac{n^2 + n}{2}}~

Giả sử ~R_n = n^3~. Khi đó ~\begin{cases} \alpha = 0 \\ n^3 = (n-1)^3 + \beta + \gamma n + \delta n^2 \end{cases} \Rightarrow \alpha = 0, \beta = 1, \gamma = -3, \delta = 3~.

Thế vào ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~, ta có ~3D(n) - 3C(n) + B(n) = n^3 \Rightarrow \boxed{D(n) = \frac{n^3 + 3\frac{n^2 + n}{2} - n}{3} = \frac{n(n+1)(2n+1)}{6}}~

Ta có:

~\square_0 = 0~

~\square_n = \square_{n-1} + n^2~

nên ta áp dụng công thức khi ~\alpha = 0, \beta = 0, \gamma = 0, \delta = 1~. Tức ~\square_n = D(n) = \boxed{\frac{n(n+1)(2n+1)}{6}}~

4. Dùng sai số giữa ~\int~ và ~\sum~

Ta thấy ~\int~ và ~\sum~ là hai kí hiệu có điểm liên quan chặt chẽ với nhau. Trong khi ~\int~ có thể dùng để tính phần diện tích nằm dưới đường cong thì ~\sum~ có thể được dùng để tính xấp xỉ diện tích nằm dưới đường cong bằng cách tính tổng diện tích các hình chữ nhật.

Từ mối quan hệ giữa ~\int~ và ~\sum~ mà ta có ý tưởng tính ~E_n = \sum_{k=0}^n f(k) - \int_0^n f(x)dx~, biết đâu ta ra được công thức cho ~E_n~ và ~\int_0^n f(x)dx~ mà nhờ đó ra được công thức cho ~\sum_{k=0}^n f(k)~

Ví dụ:

~E_n = \sum_{k=0}^n k^2 - \int_0^n x^2 dx = \sum_{k=0}^n k^2 - (\int_0^1 x^2 dx + \int_1^2 x^2 dx + ... + \int_{n-1}^n x^2dx)~

~E_n = \sum_{k=1}^n (k^2 - \int_{k-1}^k x^2 dx)~

~E_n = \sum_{k=1}^n (k^2 - [\frac{x^3}{3}]_{k-1}^k)~

~E_n = \sum_{k=1}^n (k^2 - \frac{k^3 - (k-1)^3}{3}) = \sum_{k=1}^n(k - \frac{1}{3})~

Từ đây ta dễ dàng tính được ~E_n~. Việc tính ~\int_0^n x^2 dx~ cũng đơn giản, và từ hai biểu thức này và công thức ~E_n = \sum_{k=0}^n f(k) - \int_0^n f(x)dx~, ta tính được ~\square_n~

5. Biến tổng một biến thành tổng nhiều biến

Ta có:

~\square_n = \sum_{k=1}^n k^2 = \sum_{k=1}^n \underbrace{k+k+k+...+k}_{k \text{ lần}} = \sum_{k=1}^n \sum_{j=1}^k k~

Ta sẽ tìm cách mang ~\sum_j~ ra ngoài. Xét các cặp ~(k,j)~ được xét trong tổng. Các cặp này thỏa mãn điều kiện ~1 \leq j \leq k \leq n~.

~j~ có thể chạy từ ~1~ đến ~n~, và với mỗi ~j~, ~k~ có thể chạy từ ~j~ đến ~n~. Vì vậy:

~\square_n = \sum_{j=1}^n \sum_{k=j}^n k~

~\square_n = \sum_{j=1}^n \frac{(j + n)(n - j + 1)}{2}~ (dùng công thức tính tổng ~j + (j+1) + ... + n~)

~\square_n = \frac{1}{2} \sum_{j=1}^n (-j^2 + j + n^2 + n)~

~\square_n = -\frac{1}{2}\square_n + \frac{1}{2}(\frac{n(n+1)}{2} + n^3 + n^2)~

~\Rightarrow \frac{3}{2}\square_n = \frac{n(n+1)}{2} + n^3 + n^2~

Từ đây, ta dễ dàng tính được ~\square_n~

Ngoài các phương pháp trên, chúng ta còn hai phương pháp sử dụng sai phân (note sau), hoặc sử dụng hàm sinh.

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}~

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.

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)~

(低羅沒路嘟 Cá tháng Tư)

命嗔得界紹典各伴沒排曰衛總分，差分。帝享應役使用"chữ tượng hình" 帝發展"tư duy" 立程，命嗔法得曰排呢朋"chữ Nôm" 台位字國語。

於立11，12 各伴諸得學衛各概念道咸吧辟分。各概念呢固忍性質窒葉，執眾些丹澗化役性算假治懶一，𡮈一，面辟，世辟，。。。。

相自，台概念差分吧總分共固忍性質葉相自道咸，辟分吧侞世執些性總沒隔丹澗欣。

1。差分

些諸別：

~f'(x) = \lim_{h \rightarrow 0} \frac{f(x+h) - f(x)}{h}~

由欺性總，~h~ 羅數元年欺 ~h \rightarrow 0~ 時 ~h~ 止固世羅 ~1~ 或 ~-1~. 帝丹澗化，些𩲡 ~h=1~ 帝固定義差

~\Delta(f(x)) = f(x+1) - f(x)~

~\Delta(f(x))~ 讀羅差分𧵑 ~f~ 在點 ~x~，或論欣羅差分𧵑 ~f(x)~

些固性質差𧵑道咸: ~(x^m)' = mx^{m-1}~

些仕此性差分𧵑 ~x^3~ 覘差分料固世固性質相自能空。

~\Delta(x^3) = (x+1)^3 - x^3 = 3x^2 + 3x + 1~

結果呢空葉吧易汝如 ~(x^3)' = 3x^2~, 位丕欺爫役某差分，些勤類累承特別噲羅累承減﹝能群噲羅皆承減﹞

~x^{\underline{m}} = x(x-1)(x-2)...(x-m+1)~

些𧡊低羅辟𧵑 ~m~ 承數減寅 ~x~, ~x-1~, ..., ~x-m+1~. 既號 ~x^{\underline{m}}~ 讀羅 ~x~ 帽 ~m~ 減

些此性差分𧵑 ~x^{\underline{m}}~

~\Delta(x^{\underline{m}}) = (x+1)^{\underline{m}} - x^{\underline{m}} = (x+1)x(x-1)(x-2)...(x-m+2) - x(x-1)(x-2)...(x-m+1) = x(x-1)(x-2)...(x-m+2)[(x+1) - (x-m+1)]~

~\Delta(x^{\underline{m}}) = mx(x-1)(x-2)...(x-m+2) = mx^{\underline{m-1}}~

丕些固公識葉吧易汝 ~\boxed{\Delta(x^{\underline{m}}) = mx^{\underline{m-1}}}~

於𨕭眾些某定義累承減某數帽揚。些仕定義累承減朱數帽空揚如差帝性質棟哈於𨕭中。

~x^{\underline{0}} = 1~

~x^{\underline{-m}} = \frac{1}{(x+1)(x+2)(x+3)...(x+m)}~ (~m > 0~)

差欺定義得累承減朱每數元，些徐固得公識人台累承減

~\boxed{x^{\underline{n+m}} = x^{\underline{n}}(x-n)^{\underline{m}}}~

同時，些共固公識差﹝種公識開展二識Newton﹞

~(x+y)^{\underline{n}} = \sum_{k=0}^n C_n^k x^{\underline{k}}y^{\underline{n-k}}~

沒性質葉女𧵑道咸羅 ~(e^x)' = e^x~. 料固沒咸 ~f(x)~ 鬧課滿 ~\Delta f(x) = f(x)~ 能空？

些固： ~\Delta f(x) = f(x) \Rightarrow f(x+1) - f(x) = f(x) \Rightarrow f(x+1) = 2f(x)~

易𧡊 ~f(x) = 2^x~ 羅沒咸課滿 ~f(x+1) = 2f(x)~, 吧位世 ~\boxed{\Delta(2^x) = 2^x}~

役性差分咸帽共可丹澗

~\Delta(c^x) = c^{x+1} - c^x \Rightarrow \boxed{\Delta(c^x) = (c-1)c^x}~

2。總分

些諸別：

~\int_a^b f(x) dx = \lim_{n \rightarrow \infty} \sum_{i=1}^{n-1} (x_{i+1} - x_i)f(x_i)~

某 ~x_i = a + \frac{i}{n+1}(b-a)~ (tức ~x_0, x_1, ..., x_n, x_{n+1}~ 羅各點中斷 ~[a,b]~ 隔調饒)

﹝帝易想象吧汝公識呢，流意 ~\sum_{i=1}^{n-1} (x_{i+1} - x_i)f(x_i)~ 羅總面辟各刑字日用帝約量面辟噽𠁑途是咸數 ~f(x)~﹞

些禮敢興慈概念辟分帝定義總分如差：

~\sum_a^b f(x) \delta x = f(a) + f(a+1) + ... f(b-1) = \sum_{k=a}^{b-1} f(k)~

流意總止豸慈 ~a~ 典 ~b-1~ 帝總分固各性質種辟分差：

• ~\sum_a^b f(x) \delta x + \sum_b^c f(x) \delta x = \sum_a^c f(x) \delta x~ (種 ~\int_a^b f(x)dx + \int_b^c f(x)dx = \int_a^c f(x)dx~)
• 裊 ~g(x) = \Delta(f(x))~ 時
  • ~\sum_a^b g(x) \delta x = f(x)]_a^b = f(b) - f(a)~ (種裊 ~g(x) = f'(x)~ 時 ~\int_a^b g(x) dx = f(x)]_a^b~)
  • 些既號 ~\sum g(x) \delta x = f(x) + C~ (種元咸)

瘴明性質裊 ~g(x) = \Delta(f(x))~ 時 ~\sum_a^b g(x) \delta x = f(x)]_a^b = f(b) - f(a)~

些固：

~\sum_a^b g(x) \delta x = \sum_{k=a}^{b-1} g(x) = \Delta(f(a)) + \Delta(f(a+1)) + \Delta(f(a+2)) + ... + \Delta(f(b-1))~

~\sum_a^b g(x) \delta x = (f(a+1) - f(a)) + (f(a+2) - f(a+1)) + (f(a+3) - f(a+2)) + ... + (f(b) - f(b-1))~

~\sum_a^b g(x) \delta x = f(b) - f(a)~

慈各公識性差分於𨕭，些易陽固得各公識性總分差：

• ~\sum x^{\underline{m}} \delta x = \frac{x^{\underline{m+1}}}{m+1} + C~ (中欺 ~m \ne -1~)
• ~\sum c^x \delta x = \frac{c^x}{c-1} + C~ (中欺 ~c \ne 1~). 欺 ~c = 1~ 時 ~\sum c^x \delta x = \sum 1 \delta x = x + C~

悲徐些勤所公識朱 ~\sum x^{\underline{m}} \delta x~ 欺 ~m = -1~. 於門解辟，些別

~\int x^{-1} dx = \ln |x| + C~

相自，些共固

~\sum x^{\underline{-1}} = H_x + C~ 某 ~H_x = \sum_{1 \leq k \leq x} \frac{1}{k}~

調呢朱𧡊 ~H_x~ 固堯性質種某咸 ~\ln~. 倘些共諸瘴明得 ~|H_n - \ln n| < 1~ 欺 ~n~ 都懶.

3. 應用丹澗𧵑總分

察排算性 ~\square_n = \sum_{0 \leq k \leq n} k^2~

話𥆾時固𡲈如排算𨕭空連觀之典差分，總分位各性質於𨕭止停朱累承減𠹲空拜累承平常。雖然，些固世轉 ~k^2~ 朋總各累承減朋公識 ~k^2 = k^{\underline{2}} + k^{\underline{1}}~

些固：

~\sum_{0 \leq k \leq n} k^2 = \sum_0^{n+1} k^2 \delta k = \sum_0^{n-1} (k^{\underline{2}} + k^{\underline{1}}) \delta k~

~\boxed{\sum_{0 \leq k \leq n} k^2 = [\frac{k^{\underline{3}}}{3} + \frac{k^{\underline{2}}}{2}]_0^{n+1}}~

慈低些止役開展羅囉沒公識朱 ~\square_n~

相自，些固世用公識 ~k^3 = k^{\underline{3}} + 3k^{\underline{2}} + k^{\underline{1}}~ 帝性 ~C_n = \sum_{0 \leq k \leq n} k^3~ 如差：

~C_n = \sum_0^{n+1} (k^{\underline{3}} + 3k^{\underline{2}} + k^{\underline{1}}) \delta k~

~C_n = [\frac{k^{\underline{4}}}{4} + k^{\underline{3}} + \frac{k^{\underline{2}}}{2}]_0^{n+1}~

爫世鬧帝些尋得各係數中各公識 ~k^2 = k^{\underline{2}} + k^{\underline{1}}~ 吧 ~k^3 = k^{\underline{3}} + 3k^{\underline{3}} + k^{\underline{1}}~. 俱者利羅些使用數Sterling 類I ﹝蓋呢共種役些使用數祖合能三角Pascal 帝尋係數𧵑各數巷中開展 ~(a+b)^n~ 丕﹞。

4. 差分𧵑沒辟，總分曾焚

察差分𧵑沒辟台咸 ~u~ 吧 ~v~. 些仕尋隔性 ~\Delta(uv)~ 慈 ~u, v, \Delta(u), \Delta(v)~

~\Delta(uv) = u(x+1)v(x+1) - u(x)v(x) = u(x+1)v(x+1) + u(x+1)v(x) - u(x+1)v(x) - u(x)v(x)~

﹝役共除 ~u(x+1)v(x)~ 棟𦠘路爫求綏𡧲台數巷﹞

~\Delta(uv) = u(x+1)[v(x+1) - v(x)] + v(x)[u(x+1) - u(x)]~

~\Delta(uv) = u(x+1)\Delta(v) + v(x)\Delta(u)~

帝公識呢葉欣，些定義 ~Eu(x) = u(x+1)~ (~E~ 羅曰悉𧵑慈"Extra" ﹝添﹞中㗂英﹞，些固世曰論公識呢又如差：

~\boxed{\Delta(uv) = Eu\Delta(v) + v\Delta(u)}~

中索，公識呢羅 ~\boxed{\Delta(uv) = u\Delta(v) + Ev\Delta(u)}~. 墨油台公識呢空對稱仍些固世瘴明眾朋饒。

於門解辟，公識性道咸𧵑沒辟執些固得公識性辟分曾焚。相自，些共固公識性總分曾焚如差：

~\sum u\Delta(v) = uv - \sum Ev\Delta(u)~

種如公識性辟分曾焚，些常使用得公識性總分曾焚裊中表識勤性，固沒焚性差分易吧沒焚性總分易。

圍裕 1: 性 ~\sum_{0 \leq k \leq n} k2^k~

頭先，些性 ~\sum x2^x \delta x~

達 ~u(x) = x \Rightarrow \Delta(u) = 1~, ~\Delta(v) = 2^x \Rightarrow v = 2^x \Rightarrow Ev = 2^{x+1}~

欺帝： ~\sum x2^x \delta x = x2^x - \sum 2^{x+1} \delta x = x2^x + 2^{x+1} + C~

位世麻 ~\sum_{0 \leq k \leq n} k2^k = \sum_0^{n+1} x2^x \delta x = [x2^x + 2^{x+1}]_0^{n+1}~

圍裕 2: 性 ~\sum_0^n H_x \delta x~

些𧡊 ~H_x~ 羅沒焚易性差分，位世年些達

~u(x) = H_x \Rightarrow \Delta(u) = x^{\underline{-1}}~

~\Delta(v) = 1 \Rightarrow v = x^{\underline{1}} = x\Rightarrow Ev = (x+1)^{\underline{1}}~

些固： ~\sum H_x \delta x = xH_x - \sum (x+1)^{\underline{1}}x^{\underline{-1}} \delta x~

~\sum H_x \delta x = xH_x - \sum 1 \delta x~

~\sum H_x \delta x = xH_x + x + C~

慈帝易陽性得 ~\boxed{\sum_0^n H_x \delta x = nH_n + n}~

圍裕 3: 性 ~\sum_0^n xH_x \delta x~

達：

~u(x) = H_x \Rightarrow \Delta(u) = x^{\underline{-1}}~

~\Delta(v) = x \Rightarrow v = \frac{x^{\underline{2}}}{2} \Rightarrow Ev = \frac{(x+1)^{\underline{2}}}{2}~

些固：

~\sum xH_x \delta x = \frac{x^{\underline{2}}}{2}H_x - \sum \frac{(x+1)^{\underline{2}}x^{\underline{-1}}}{2} \delta x~

~\sum xH_x \delta x = \frac{x^{\underline{2}}}{2}H_x - \frac{1}{2} \sum x \delta x~

~\sum xH_x \delta x = \frac{x^{\underline{2}}}{2}H_x - \frac{x^{\underline{2}}}{4} + C~

慈帝易陽性得 ~\boxed{\sum_0^n xH_x \delta x = \frac{n^{\underline{2}}}{2}H_n - \frac{n^{\underline{2}}}{4}}~

5. 總合見識

~\Delta(x^{\underline{m}}) = mx^{\underline{m-1}} \Rightarrow \sum x^{\underline{m}} \delta x = \frac{x^{\underline{m+1}}}{m+1} + C~

(特別： ~\Delta(H_x) = x^{\underline{-1}} \Rightarrow \sum x^{\underline{-1}} \delta x = H_x + C~)

~\Delta(c^x) = (c-1)c^x \Rightarrow \sum c^x \delta x = \frac{c^x}{c-1} + C~

(特別：~\Delta(2^x) = 2^x \Rightarrow \sum 2^x \delta x = 2^x + C~)

~\Delta(cf) = c\Delta(f) \Rightarrow \sum cf = c \sum f~ (~c~ 羅恆數)

~\Delta(f + g) = \Delta(f) + \Delta(g) \Rightarrow \sum (f + g) = \sum f + \sum g~

~\Delta(fg) = f\Delta(g) + Eg\Delta(f) \Rightarrow \sum f\Delta(g) = fg - \sum Eg\Delta(f)~

Note này được mình viết trong lúc đọc sách Concrete Mathematics, phần 1.3. Khi đọc sách Toán, mình thấy không nên chỉ đọc sơ qua mà nên bắt tay vào làm cùng theo chỉ dẫn của sách, khi đó thì mình sẽ nhớ và nắm kĩ ý tưởng giải bài hơn. Ngoài ra, mình viết note này để phục vụ bản thân là chính: một số phần mình thấy dễ hiểu thì mình bỏ qua, phần khó hiểu mình note kĩ hơn, và vì thế một số bạn sẽ thấy note hữu ích và một số bạn sẽ không học được gì từ mấy note này.

Cho ~n~ người đứng thành một vòng tròn, mỗi người được đánh số từ 1 đến ~n~. Bắt đầu từ vị trí số 1, mỗi người sẽ đếm lần lượt 1, 2, ..., ~k~, người đếm ~k~ sẽ bị loại khỏi vòng tròn, và mọi người tiếp tục đếm lại từ ~1~ cho đến khi chỉ còn lại một người. Hỏi người đánh số nào là người ở lại vòng tròn cuối cùng.

Trong khuôn khổ bài viết này, ta nghiên cứu trường hợp ~k = 2~.

Gọi ~J(n)~ là số của người ở lại vòng tròn cuối cùng, ta sẽ thử tính ~J(n)~ với một số giá trị nhỏ của ~n~:

• ~J(1) = 1~
• ~J(2) = 1~
• ~J(3) = 3~ (thứ tự loại ~2, 1~)
• ~J(4) = 1~ (thứ tự loại ~2, 4, 3~)
• ~J(5) = 3~ (thứ tự loại ~2, 4, 1, 3~)
• ~J(6) = 5~ (thứ tự loại ~2, 4, 6, 1, 3~)

Qua những giá trị ban đầu, ta thấy ~J(n)~ là một số lẻ, điều này là do ở lần đi qua vòng tròn đầu tiên thì ta đã loại hết tất cả số chẵn. Ngoài ra, tùy vào tính chẵn lẻ của ~n~ mà ~1~ bị loại ngay sau lần duyệt đầu tiên, hoặc an toàn khá lâu, vì vậy ta nghĩ đến việc xét tính chẵn lẻ của ~n~.

Ta xét trường hợp có ~2n~ người. Sau một lần đi qua vòng tròn, vòng tròn trở thành ~1, 3, 5, ..., 2n-3, 2n-1~ (~n~ người). Ta thấy vòng tròn này giống hệt vòng tròn ~1, 2, 3, ..., n~, ngoại trừ việc số của người ~x~ trở thành ~2x-1~. Do đó, ~J(2n) = 2J(n) - 1~.

Xét trường hợp có ~2n+1~ người. Ta thấy sau khi người 1 đếm "2" thì vòng tròn còn ~n~ người ~3, 5, ..., 2n+1~. Vòng tròn này giống hệt vòng tròn ~n~ người của trò chơi ban đầu, ngoại trừ việc số của người ~x~ trở thành ~2x+1~. Do đó ~J(2n+1) = 2J(n)+1~.

Vậy ta có công thức truy hồi:

• ~J(1) = 1~
• ~J(2n) = 2J(n) - 1~
• ~J(2n+1) = 2J(n) + 1~

Liệu có công thức tổng quát cho công thức truy hồi này không?

Sử dụng công thức truy hồi này, ta sẽ tính được kết quả cho một số ~n~ lớn hơn một chút. Ta thấy được quy luật sau (các giá trị ~J(n)~ dưới đây được viết từ ~J(1)~ theo thứ tự từ trái qua phải, từ trên xuống dưới để thể hiện quy luật)

• ~1~ (~n=1~)
• ~1,3~ (~n=2..3~)
• ~1,3,5,7~ (~n=4..7~)
• ~1,3,5,7,11,13,15~ (~n=8..15~)

Ta thấy có một "chu kì" mới bắt đầu khi ~n = 2^m~, và các số trong "chu kì" có dạng ~1, 3, 5, 7, ...~. Ta có thể biểu diễn điều này dưới dạng toán học như sau

~J(2^m + l) = 2l+1~ với ~m \geq 0~ và ~0 \leq l < 2^m~ (cách kí hiệu này khá giống kí hiệu ~q, r~ trong định nghĩa phép chia hai số tự nhiên)

Ta sẽ chứng minh công thức tổng quát này bằng quy nạp theo ~m~

Nếu ~m = 0~, khi đó do ~0 \leq l < 2^m = 1~ nên ~l = 0~. ~J(2^m + l) = J(1 + 0) = J(1) = 1 = 2(0) + 1 = 2l+1~, nên trường hợp khởi đầu đúng.

Nếu ~m \geq 1~, ta có hai trường hợp

• Nếu ~l~ chẵn, ~J(2^m + l) = 2J(\frac{2^m+l}{2}) - 1 = 2J(2^{m-1} + \frac{l}{2}) - 1 = 2(2(\frac{l}{2}) + 1) + 1 = 2l + 1~

• Nếu ~l~ lẻ, ~J(2^m + l) = 2J(\frac{2^m+l-1}{2}) + 1 = 2(2(\frac{l-1}{2}) + 1) + 1 = 2l+1~

Từ hai trường hợp trên, ta thấy trường hợp quy nạp cũng đúng.

Do đó theo nguyên lí quy nạp thì công thức đúng.

Bây giờ ta sẽ thử mở rộng bài toán để có thể giải được các bài toán khác.

Ta thấy công thức xuất hiện số ~2^m~, và vì thế ta nghĩ đến việc viết lại công thức dưới dạng hệ nhị phân xem có gì đặc biệt không.

Giả sử ~n = (b_mb_{m-1}...b_1b_0)_2 = b_m \cdot 2^m + b_{m-1} \cdot 2^{m-1} + ... + b_1 \cdot 2^1 + b_0 \cdot 2^0~.

Khi ~n = 2^m + l~ thì

~n = (1b_{m-1}...b_1b_0)_2~

~l = (0b_{m-1}...b_1b_0)_2~

~2l = (b_{m-1}...b_1b_00)_2~ (dịch bit sang trái)

~2l + 1 = (b_{m-1}...b_1b_01)_2~

Nói cách khác, ~J((1b_{m-1}...b_1b_0)_2) = (b_{m-1}...b_1b_01)_2~, tức ta chỉ cần cyclic left shift số ~n~ là tính được ~J(n)~

Một cách mở rộng bài toán khác là giả sử ta không may mắn gặp phải một công thức truy hồi có dạng sau:

~f(1) = \alpha~

~f(2n) = 2f(n) + \beta~

~f(2n+1) = 2f(n) + \gamma~

thì liệu ta có giải được không?

Đầu tiên, ta lại thử với ~n~ nhỏ để tìm quy luật:

• ~f(1) = 1\alpha + 0\beta + 0\gamma~
• ~f(2) = 2\alpha + 1\beta + 0\gamma~
• ~f(3) = 2\alpha + 0\beta + 1\gamma~
• ~f(4) = 4\alpha + 3\beta + 0\gamma~
• ~f(5) = 4\alpha + 2\beta + 1\gamma~
• ~f(6) = 4\alpha + 1\beta + 2\gamma~
• ~f(7) = 4\alpha + 0\beta + 3\gamma~

Ta thấy xuất hiện các chu kì giống như trong dãy Josephus.

Đặt ~f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma~. Khi viết ~n = 2^m + l~, dễ thấy

• ~A(n) = 2^m~
• ~B(n) = 2^m - l - 1~
• ~C(n) = l~

Nếu giả sử các hàm ~A(n), B(n), C(n)~ không dễ thấy như trên thì liệu ta có thể dùng kĩ thuật nào khác để mò ra các hàm nào không. Ta có thể sử dụng repertoire method, với tư tưởng chính là:

• Chọn các hàm ~f(n)~ đặc biệt, rồi lấy ~\alpha, \beta, \gamma~ ứng với các hàm đó.
• Các ~\alpha, \beta, \gamma, f(n)~ sẽ tạo ra hệ phương trình ẩn ~A(n), B(n), C(n)~
• Giải hệ phương trình.

Ở ví dụ này, ta dễ thấy ~\boxed{A(n) = 2^m}~ với ~n = 2^m + l~, nhưng có thể ta không thấy được ~B(n), C(n)~. Ta sẽ ứng dụng repertoire method để giải.

Đầu tiên, a muốn tìm ~\alpha, \beta, \gamma~ để ~f(n) = 1~. Thay vào

~f(1) = \alpha~

~f(2n) = 2f(n) + \beta~

~f(2n+1) = 2f(n) + \gamma~

Ta có: ~\alpha = 1~, ~1 = 2 + \beta \Rightarrow \beta = -1~, ~1 = 2 + \gamma \Rightarrow \gamma = -1~. Thay các giá trị ~\alpha, \beta, \gamma~, và ~f(n) = 1~ vào ~f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma~, ta được: ~\boxed{A(n) - B(n) - C(n) = 1}~

Lấy ~f(n) = n~. Thay vào hệ thức truy hồi, ta có:

~\alpha = 1~

~2n = 2n + \beta \Rightarrow \beta = 0~

~2n + 1 = 2n + \gamma \Rightarrow \gamma = 1~

Thay các giá trị này cùng với ~f(n) = n~ vào ~f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma~, ta được ~\boxed{A(n) + C(n) = n}~

Giải hệ ~\begin{cases} A(n) = 2^m \\ A(n) - B(n) - C(n) = 1 \\ A(n) + C(n) = n \end{cases}~, ta ra được ~A(n), B(n), C(n)~ như quan sát ở trên.

Số ~2^m~ lại xuất hiện trong ~A(n)~ và ~B(n)~. Điều này khiến ta nghĩ tới việc giải công thức truy hồi dạng tổng quát dưới dạng hệ nhị phân.

Để thuận tiện, ta viết lại

~f(1) = \alpha~

~f(2n) = 2f(n) + \beta~

~f(2n+1) = 2f(n) + \gamma~

thành

~f(1) = \alpha~

~f(2n + j) = 2f(n) + \beta_j~ với ~j \in \{0,1\}~ (~\beta_0 = \beta, \beta_1 = \gamma~)

Khi đó

~f((b_mb_{m-1}...b_1b_0)_2) = 2f((b_mb_{m-1}...b_1)_2) + \beta_{b_0}~

~f((b_mb_{m-1}...b_1b_0)_2) = 4f((b_mb_{m-1}...b_2)_2) + 2\beta_{b_1} + \beta_{b_0}~

~f((b_mb_{m-1}...b_1b_0)_2) = 8f((b_mb_{m-1}...b_3)_2) + 2^2\beta_{b_2} + 2^1\beta_{b_1} + \beta_{b_0}~

...

~f((b_mb_{m-1}...b_1b_0)_2) = 2^mf((b_m)_2) + 2^{m-1}\beta_{b_{m-1}} + ... + 2^1\beta_{b_1} + \beta_{b_0}~

~f((b_mb_{m-1}...b_1b_0)_2) = 2^m\alpha + 2^{m-1}\beta_{b_{m-1}} + ... + 2^1\beta_{b_1} + \beta_{b_0}~

Nếu ta cho phép các chữ số trong kí hiệu hệ nhị phân được lấy giá trị bất kì, ta có thể viết

~f((b_mb_{m-1}...b_1b_0)_2) = (\alpha\beta_{b_{m-1}}...\beta_{b_1}\beta_{b_0})_2~

(cho ~\alpha~ làm số đầu tiên trong đáp án, với ~m-1~ số còn lại, đổi chữ số ~i~ thành ~\beta_i~)

Ví dụ, với bài toán Josephus ban đầu (~\alpha = 1, \beta_0 = -1, \beta_1 = 1~), để tính ~J(100)~, ta có thể làm như sau:

~100 = (1100100)_2~

Cho ~\alpha = 1~ ở đầu, trong ~m-1~ số còn lại, thay số 0 bằng -1 và thay số 1 bằng 1, ta có:

~J(100) = ((1)(1)(-1)(-1)(1)(-1)(-1))_2 = 64 + 32 - 16 - 8 + 4 - 2 - 1 = 73~

Ta thấy công thức truy hồi trên còn số 2 ta chưa tổng quát. Giả sử ta có hệ thức truy hồi sau

~f(j) = \alpha_j~ với ~1 \leq j < d~

~f(dn + j) = cf(n) + \beta_j~ với ~0 \leq j < d~ và ~n \geq 1~

thì bằng cách viết ~n~ dưới dạng hệ cơ số ~d~ và viết đáp án dưới dạng hệ cơ số ~c~, ta cũng ra được kết quả

~f((b_mb_{m-1}...b_1b_0)_d) = (\alpha_{b_m}\beta_{b_{m-1}}...\beta_{b_1}\beta_{b_0})_c~