Một cách để có các cận dựa trên một phép lấy tổng khác đó là diễn tả chuỗi dưới dạng tổng của hai hay nhiều chuỗi bằng cách phân hoạch [partitioning] miền của chỉ số rồi định cận từng chuỗi kết quả. Ví dụ, giả sử ta gắng tìm một cận dưới dựa trên chuỗi câ”p sô” cộng ỵ.L\k, đã được chứng tỏ là có một cận trên n1. Ta có thể gắng định cận từng sô” hạng trong phép lấy tổng bằng sô” hạng nhỏ nhâ”t, nhưng do số hạng đó là 1, ta có một cận dưới n của phép lấy tổng—cách xa với cận trên n2 của chúng ta.
Để có một cận dưới tốt hơn, trước tiên ta tách phép lấy tổng. Để tiện dụng, giả sửn là chấn. Ta có
±k= Ễk+t k
k= I *=1 k=nt 2+1
> É 0 + X (n/2)
A=! Ẳ=n/2+l
> (n/2)2
= 0(«2),
là một cận sát tiệm cận, bởi ‘LLik = 0(n2).
Với một phép lấy tổng phát sinh từ việc phân tích một thuật toán, ta thường có thể tách phép lấy tổng và bỏ qua một số lượng bất biến các sô” hạng ban đầu. Nói chung, kỹ thuật này áp dụng khi từng sô” hạngak trong phép lấy tổng độc lập với n. Như vậy với bâ”t kỳ bằng k0>
0, ta có thể viết
n V* »
Jx = ỈX+ %ak
Ẳ=1 Jt=o k=kữ
= 0(1)+ tak,
k=k0
bởi tất cả số hạng ban đầu của phép lấy tổng là bâ”t biến và chúng có một số lượng bâ”t biến. Như vậy, ta có thể dùng các phương pháp khác để định cận ĩ,Uk ak. Ví dụ, để tìm một cận trên tiệm cận trên ta nhận thâ”y tỷ số của các số hạng liên tiếp là
(£+l)2/2*+1=(k+l)z k2/2k 2 k2
nếu k > 3. Như vậy, phép lâ”y tổng có thể được tách thànềi
Ẽf = tị+tị
k=0 z k=ì ^ k= 3 ^
– 0(1),
bởi phép lấy tổng thứ hai là một chuỗi câp số nhân giảm.
Kỹ thuật tách các phép lấy tổng có thểđược dùng để xác định các cận tiệm cận trong các tình huống khó khăn hơn nhiều. Ví dụ, có thể đạt được một cận 0(lg n) trên chuỗi điều hòa (3.5):
ùi k’
Ý tưởng đó là tách miền 1 đến nthànhh các mẩu Llg n\và định cận trên phần đóng góp của mỗi mẩu theo 1. Như vậy,
n 1 LlgrtJ 2u 1
ịịíịĨY-
Ẳ=1 * i=0 7=0 ^ +7
LlgnJ
s Zi4i
/=0 j=0 ”
Ug wj
< II
í=0
< lg n + 1 . (3.8)
Phép xấp xỉ bằng các tích phân
Khi một phép lấy tổng có thể được diễn tả dưới dạng ỵnk-mf(k), ở đó f(k) là một hàm tăng đơn điệu, ta có thể lấy xấp xỉ nó bằng các tích phân:
LtẪx)dx <Ệ/W<íl í{x)dx. (3-9)
Hình 3.1 chứng minh phép xấp xỉ này. Phép lấy tổng được biểu thị bằng diện tích các hình chữ nhật trong hình, và tích phân là vùng tô bóng dưới đường cung. Khi f (k) là một hàm giảm đơn điệu, ta có thể dùng phương pháp tương tự để cung cấp các cận
£ fix)dx< !/(*)<ị”mlfix)dx. <3-10)
k=m
Phép xấp xỉ tích phân (3.10) cho ra một ước tính chặt cho số điều hòa thứn. Với một cận dưới, ta có
vi >c+l dx-
ètk X
= ln(/z+l).
Với một cận trên, ta rút ra bâ’t đẳng thức
èĩs /: T
= ln n, cho ra cận
Hình 3.1 Phép xấp xl của ‘Lĩ.mf(k)t bằng các tích phân. Diện tích của từng hình chữ nhật được nêu trong hình chữ nhật, và tổng diện tích chữ nhật biểu thị cho giá trị của phép lấy tổng. Tích phân được biểu thị bằng diện tích tô bóng dưđi đường cung. Bàng cách so sánh các diện tích trong (a), ta có fm.ìf(x)dx < ‘LLmf(k)Ị roi bằng cách chuyển các hình chữ nhật sang phải một đơn vị, ta có 2.”.„/(£) <LZ’f(x)dx trong (b).
Bài tập
3.2- 1
Chứng tỏ Zĩ.t Mk2 được định cận bên trên bằng một hằng.
3.2- 2
Tìm một cận trên tiệm cận theo phép lấy tổng
hgd r -ị
ỉ ín/2‘1.
3.2- 3
Chứng tỏ số điều hòa thứn là Q(lg n) bằng cách tách phép lấy tổng.
3.2- 4
Tính xấp xỉ Eĩ.ìk3 bằng một tích phân.
3.2- 5
Tại sao ta không dùng phép xấp xỉ tích phân (3.10) trực tiếp trên Z”=I \Ịk để có một cận trên dựa trên sô” điều hòa thứtíì
Các Bài Toán
3- 1 Định cận các phép lấy tổng
Nêu các cận sát tiệm cận dựa trên các phép lây tổng dưới đây. Giả sửr> 0 và s> 0 là các hằng.
a.
a. Ẻig
k=ỉ
c.
Jt=J
Ghi chú Chương
Knuth [121] là tài liệu tham khảo tuyệt vời cho nội dung trình bày trong chương này. để tìm hiểu các tính chất căn bản của chuỗi, bạn có thể xem bất kỳ cuốn sách nào về hệ tính toán, như Apostol [12] hoặc Thomas and Finney [192].