Link tải luận văn miễn phí cho ae Kết Nối
Hàm sinh
Hàm sinh là một trong những sáng tạo thần tình, bất ngờ, nhiều ứng dụng của toán rời rạc. Nói một cách nôm na, hàm sinh chuyển những bài toán về dãy số thành những bài toán về hàm số. Điều này là rất tuyệt vời vì chúng ta đã có trong tay cả một cỗ máy lớn để làm việc với các hàm số. Nhờ vào hàm sinh, chúng ta có thể áp dụng cỗ máy này vào các bài toán dãy số. Bằng cách này, chúng ta có thể sử dụng hàm sinh trong việc giải tất cả các dạng toán về phép đếm. Có cả một ngành toán học lớn nghiên cứu về hàm sinh, vì thế, trong bài này, chúng ta chỉ tìm hiểu những vấn đề căn bản nhất về chủ đề này.
Trong bài viết này, các dãy số sẽ được để trong ngoặc < > để phân biệt với các đối tượng toán học khác.
1. Hàm sinh
Hàm sinh thường của dãy số vô hạng là chuỗi luỹ thừa hình thức
G(x) = g0 + g1x + g2x2 + g3x3 …
Ta gọi làm sinh là chuỗi hình thức bởi vì thông thường ta sẽ chỉ coi x là một ký hiệu thay thế thay vì một số. Chỉ trong một vài trường hợp ta sẽ cho x nhận các giá trị thực, vì thế ta gần như cũng không để ý đến sự hội tụ của các chuỗi. Có
một số thường.
loại hàm sinh khác nhưng trong bài này, ta sẽ
chỉ
xét đến hàm sinh
Trong bài này, ta sẽ ký hiệu sự tương ứng giữa một dãy số và hàm sinh bằng dấu mũi tên hai chiều như sau
g0 + g1x + g2x2 + g3x3 +…
Ví dụ, dưới đây là một số dãy số và hàm sinh của chúng
<0, 0, 0, 0, …> 0 + 0.x + 0.x2 + 0.x3 + … = 0
<1, 0, 0, 0, …> 1 + 0.x + 0.x2 + 0.x3 + … = 1
<3, 2, 1, 0, …> 3 + 2x + x2 + 0.x3 + … = x2 + 2x + 3
Quy tắc ở đây rất đơn giản: Số hạng thứ i của dãy số (đánh số từ 0) là hệ số của xi trong hàm sinh.
Nhắc lại công thức tính tổng của các số nhân lùi vô hạn là
1 z z 2 z 3 ...
1 .
1 z
Đẳng thức này không đúng với |z| 1, nhưng một lần nữa ta không quan tâm đến vấn đề hội tụ. Công thức này cho chúng ta công thức tường minh cho hàm sinh của hàng loạt các dãy số
<1, 1, 1, 1, …> 1 + x + x2 + x3 + … = 1/(1-x)
<1, -1, 1, -1, …> 1 - x + x2 - x3 + … = 1/(1+x)
<1, a, a2, a3, …> 1 + ax + a2x2 + a3x3 + … = 1/(1-ax)
<1, 0, 1, 0, 1, 0, ...> 1 + x2 + x4 + … = 1/(1-x2)
Các phép toán trên hàm sinh
Phép màu của hàm sinh nằm ở chỗ ta có thể chuyển các phép toán thực hiện trên
dãy số thành các phép toán thực hiện trên các hàm sinh tương ứng của chúng.
Chúng ta cùng xem xét các phép toán và các tác động của chúng trong thuật ngữ dãy số.
Nhân với hằng số
Khi nhân hàm sinh với một hằng số thì trong dãy số tương ứng, các số hạng sẽ được nhân với hằng số đó. Ví dụ
<1, 0, 1, 0, 1, 0, ...> 1 + x2 + x4 + … = 1/(1-x2)
Nhân hàm sinh với 2, ta được
2/(1-x2) = 2 + 2x2 + 2x4 + …
là hàm sinh của dãy số
<2, 0, 2, 0, 2, 0, …>
Quy tắc 1. (Quy tắc nhân với hằng số)
Nếu F(x) thì cF(x) Chứng minh.
cf0 + (cf1)x + (cf2)x2 + (cf3)x3 + …
= c(f0 + f1x+f2x2 + f3x3 + …)
= cF(x).
Cộng
Cộng hai hàm sinh tương ứng với việc cộng các số hạng của dãy số theo đúng chỉ số. Ví dụ, ta cộng hai dãy số trước đó
<1, 1, 1, 1, …> 1/(1-x)
+ <1, -1, 1, -1, …> 1/(1+x)
<2, 0, 2, 0, …> 1/(1-x) + 1/(1+x)
Bây giờ ta thu được hai biểu thức khác nhau cùng sinh ra dãy (2, 0, 2, 0, …).
Nhưng điều này không có gì ngạc nhiên vì thực ra chúng bằng nhau: 1/(1-x) + 1/(1+x) = [(1+x) + (1-x)]/(1-x)(1+x) = 2/(1-x2)
Quy tắc 2. (Quy tắc cộng)
Nếu F(x), G(x) thì F(x) + G(x)
Chứng minh.
f0+g0+ (f1+g1)x + (f2+g2)x2 + …
Dịch chuyển sang phải
= (f0 + f1x + f2x2 + …) + (g0 + g1x + g2x2 + …)
= F(x) + G(x)
Ta bắt đầu từ một dãy số đơn giản và hàm sinh của nó
<1, 1, 1, 1, …> 1/(1-x)
Bây giờ ta dịch chuyển dãy số sang phải bằng cách thêm k số 0 vào đầu
<0, 0, …, 0, 1, 1, 1, …> xk + xk+1 + xk+2 + …
= xk(1+x+x2 + …)
= xk/(1-x)
Như vậy, thêm k số 0 vào đầu dãy số tương ứng với việc nhân hàm sinh với xk. Điều này cũng đúng trong trường hợp tổng quát.
Quy tắc 3. (Quy tắc dịch chuyển phải) Nếu F(x)
thì <0, …, 0, f0, f1, f2, …> xk.F(x) (có k số 0) Chứng minh.
<0, …, 0, f0, f1, f2, …> f0xk + f1xk+1 + f2xk+2 + …
= xk(f0 + f1x + f2x2 + …)
= xkF(x)
Đạo hàm
Điều gì sẽ xảy ra nếu ta lấy đạo hàm của hàm sinh? Chúng ta hãy bắt đầu từ việc lấy đạo hàm của một hàm sinh đã trở nên quen thuộc của dãy số toàn 1:
d (1 x x 2 x3 x 4 ...)
dx
d ( 1 )
dx 1 x
1 2x 3x 2 4x3 ...
1
(1 x)2
1, 2, 3, 4,...
1
(1 x)2
Ta tìm được hàm sinh cho dãy số <1, 2, 3, 4, …> !
Tổng quát, việc lấy đạo hàm của hàm sinh có hai tác động lên dãy số tương ứng: các số hạng được nhân với chỉ số và toàn bộ dãy số được dịch chuyển trái sang 1 vị trí.
Quy tắc 4. (Quy tắc đạo hàm) Nếu F(x)
thì dF(x)/dx Chứng minh.
f1 + 2f2x + 3f3x2 + …
= (d/dx)(f0 + f1x + f2x2 + f3x3 + …)
= dF(x)/dx
Quy tắc đạo hàm là một quy tắc rất hữu hiệu. Trong thực tế, ta thường xuyên cần đến một trong hai tác động của phép đạo hàm, nhân số hạng với chỉ số và dịch chuyển sang trái. Một cách điển hình, ta chỉ muốn có một tác động và tìm cách “vô hiệu hoá” tác động còn lại. Ví dụ, ta thử tìm hàm sinh cho dãy số <0, 1, 4, 9, 16, …>. Nếu ta có thể bắt đầu từ dãy <1, 1, 1, 1, …> thì bằng cách nhân với chỉ số 2 lần, ta sẽ được kết quả mong muốn
<0.0, 1.1, 2.2, 3.3, …> = <0, 1, 4, 9, …>
Vấn đề là ở chỗ phép đạo hàm không chỉ nhân số hạng dãy số với chỉ số mà còn dịch chuyển sang trái 1 vị trí. Thế nhưng, quy tắc 3 dịch chuyển phải cho chúng ta cách để vô hiệu hoá tác động này: nhân hàm sinh thu được cho x.
Như vậy cách làm của chúng ta là bắt đầu từ dãy số <1, 1, 1, 1, …>, lấy đạo hàm, nhân với x, lấy đạo hàm rồi lại nhân với x.
<1, 1, 1, 1, …> 1/(1-x)
<1, 2, 3, 4, …> (d/dx)(1/(1-x)) = 1/(1-x)2
<0, 1, 2, 3, 4, …> x/(1-x)2
<1, 4, 9, 16, …> (d/dx)( x/(1-x)2) = (1+x)/(1-x)3
<0, 1, 4, 9, 16, …> x(1+x)/(1-x)3
Như vậy hàm sinh cho dãy các bình phương là x(1+x)/(1-x)3.
3. Dãy số Fibonacci
Đôi khi chúng ta có thể tìm được hàm sinh cho các dãy số phức tạp hơn. Chẳng hạn dưới đây là hàm sinh cho dãy số Fibonacci:
<0, 1, 1, 2, 3, 5, 8, 13, …> x/(1-x-x2)
Chúng ta thấy dãy số Fibonacci biến đổi khá khó chịu, nhưng hàm sinh của nó thì rất đơn giản.
Chúng ta sẽ thiết lập công thức tính hàm sinh này và qua đó, tìm được công thức tường minh tính các số hạng tổng quát của dãy số Fibonacci. Dĩ nhiên, chúng ta đã biết công thức tính số hạng tổng quát của dãy Fibonacci trong phần phương
pháp giải các phương trình sai phân tuyến tính hệ số hằng. Nhưng điều này
không ngăn cản chúng ta một lần nữa tìm cách giải thích sự xuất hiện của
phương trình đặc trưng, cách xử lý trường hợp nghiệm kép thông qua công cụ hàm sinh. Hơn nữa, phương pháp hàm sinh còn giúp chúng ta giải quyết hàng loạt
các bài toán về
dãy số
đệ quy khác nữa, trong đó có những phương trình mà
chúng ta hoàn toàn bó tay với các phương pháp khác.
Tìm hàm sinh
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Hàm sinh
Hàm sinh là một trong những sáng tạo thần tình, bất ngờ, nhiều ứng dụng của toán rời rạc. Nói một cách nôm na, hàm sinh chuyển những bài toán về dãy số thành những bài toán về hàm số. Điều này là rất tuyệt vời vì chúng ta đã có trong tay cả một cỗ máy lớn để làm việc với các hàm số. Nhờ vào hàm sinh, chúng ta có thể áp dụng cỗ máy này vào các bài toán dãy số. Bằng cách này, chúng ta có thể sử dụng hàm sinh trong việc giải tất cả các dạng toán về phép đếm. Có cả một ngành toán học lớn nghiên cứu về hàm sinh, vì thế, trong bài này, chúng ta chỉ tìm hiểu những vấn đề căn bản nhất về chủ đề này.
Trong bài viết này, các dãy số sẽ được để trong ngoặc < > để phân biệt với các đối tượng toán học khác.
1. Hàm sinh
Hàm sinh thường của dãy số vô hạng
G(x) = g0 + g1x + g2x2 + g3x3 …
Ta gọi làm sinh là chuỗi hình thức bởi vì thông thường ta sẽ chỉ coi x là một ký hiệu thay thế thay vì một số. Chỉ trong một vài trường hợp ta sẽ cho x nhận các giá trị thực, vì thế ta gần như cũng không để ý đến sự hội tụ của các chuỗi. Có
một số thường.
loại hàm sinh khác nhưng trong bài này, ta sẽ
chỉ
xét đến hàm sinh
Trong bài này, ta sẽ ký hiệu sự tương ứng giữa một dãy số và hàm sinh bằng dấu mũi tên hai chiều như sau
Ví dụ, dưới đây là một số dãy số và hàm sinh của chúng
<0, 0, 0, 0, …> 0 + 0.x + 0.x2 + 0.x3 + … = 0
<1, 0, 0, 0, …> 1 + 0.x + 0.x2 + 0.x3 + … = 1
<3, 2, 1, 0, …> 3 + 2x + x2 + 0.x3 + … = x2 + 2x + 3
Quy tắc ở đây rất đơn giản: Số hạng thứ i của dãy số (đánh số từ 0) là hệ số của xi trong hàm sinh.
Nhắc lại công thức tính tổng của các số nhân lùi vô hạn là
1 z z 2 z 3 ...
1 .
1 z
Đẳng thức này không đúng với |z| 1, nhưng một lần nữa ta không quan tâm đến vấn đề hội tụ. Công thức này cho chúng ta công thức tường minh cho hàm sinh của hàng loạt các dãy số
<1, 1, 1, 1, …> 1 + x + x2 + x3 + … = 1/(1-x)
<1, -1, 1, -1, …> 1 - x + x2 - x3 + … = 1/(1+x)
<1, a, a2, a3, …> 1 + ax + a2x2 + a3x3 + … = 1/(1-ax)
<1, 0, 1, 0, 1, 0, ...> 1 + x2 + x4 + … = 1/(1-x2)
Các phép toán trên hàm sinh
Phép màu của hàm sinh nằm ở chỗ ta có thể chuyển các phép toán thực hiện trên
dãy số thành các phép toán thực hiện trên các hàm sinh tương ứng của chúng.
Chúng ta cùng xem xét các phép toán và các tác động của chúng trong thuật ngữ dãy số.
Nhân với hằng số
Khi nhân hàm sinh với một hằng số thì trong dãy số tương ứng, các số hạng sẽ được nhân với hằng số đó. Ví dụ
<1, 0, 1, 0, 1, 0, ...> 1 + x2 + x4 + … = 1/(1-x2)
Nhân hàm sinh với 2, ta được
2/(1-x2) = 2 + 2x2 + 2x4 + …
là hàm sinh của dãy số
<2, 0, 2, 0, 2, 0, …>
Quy tắc 1. (Quy tắc nhân với hằng số)
Nếu
= c(f0 + f1x+f2x2 + f3x3 + …)
= cF(x).
Cộng
Cộng hai hàm sinh tương ứng với việc cộng các số hạng của dãy số theo đúng chỉ số. Ví dụ, ta cộng hai dãy số trước đó
<1, 1, 1, 1, …> 1/(1-x)
+ <1, -1, 1, -1, …> 1/(1+x)
<2, 0, 2, 0, …> 1/(1-x) + 1/(1+x)
Bây giờ ta thu được hai biểu thức khác nhau cùng sinh ra dãy (2, 0, 2, 0, …).
Nhưng điều này không có gì ngạc nhiên vì thực ra chúng bằng nhau: 1/(1-x) + 1/(1+x) = [(1+x) + (1-x)]/(1-x)(1+x) = 2/(1-x2)
Quy tắc 2. (Quy tắc cộng)
Nếu
Chứng minh.
Dịch chuyển sang phải
= (f0 + f1x + f2x2 + …) + (g0 + g1x + g2x2 + …)
= F(x) + G(x)
Ta bắt đầu từ một dãy số đơn giản và hàm sinh của nó
<1, 1, 1, 1, …> 1/(1-x)
Bây giờ ta dịch chuyển dãy số sang phải bằng cách thêm k số 0 vào đầu
<0, 0, …, 0, 1, 1, 1, …> xk + xk+1 + xk+2 + …
= xk(1+x+x2 + …)
= xk/(1-x)
Như vậy, thêm k số 0 vào đầu dãy số tương ứng với việc nhân hàm sinh với xk. Điều này cũng đúng trong trường hợp tổng quát.
Quy tắc 3. (Quy tắc dịch chuyển phải) Nếu
thì <0, …, 0, f0, f1, f2, …> xk.F(x) (có k số 0) Chứng minh.
<0, …, 0, f0, f1, f2, …> f0xk + f1xk+1 + f2xk+2 + …
= xk(f0 + f1x + f2x2 + …)
= xkF(x)
Đạo hàm
Điều gì sẽ xảy ra nếu ta lấy đạo hàm của hàm sinh? Chúng ta hãy bắt đầu từ việc lấy đạo hàm của một hàm sinh đã trở nên quen thuộc của dãy số toàn 1:
d (1 x x 2 x3 x 4 ...)
dx
d ( 1 )
dx 1 x
1 2x 3x 2 4x3 ...
1
(1 x)2
1, 2, 3, 4,...
1
(1 x)2
Ta tìm được hàm sinh cho dãy số <1, 2, 3, 4, …> !
Tổng quát, việc lấy đạo hàm của hàm sinh có hai tác động lên dãy số tương ứng: các số hạng được nhân với chỉ số và toàn bộ dãy số được dịch chuyển trái sang 1 vị trí.
Quy tắc 4. (Quy tắc đạo hàm) Nếu
thì
= (d/dx)(f0 + f1x + f2x2 + f3x3 + …)
= dF(x)/dx
Quy tắc đạo hàm là một quy tắc rất hữu hiệu. Trong thực tế, ta thường xuyên cần đến một trong hai tác động của phép đạo hàm, nhân số hạng với chỉ số và dịch chuyển sang trái. Một cách điển hình, ta chỉ muốn có một tác động và tìm cách “vô hiệu hoá” tác động còn lại. Ví dụ, ta thử tìm hàm sinh cho dãy số <0, 1, 4, 9, 16, …>. Nếu ta có thể bắt đầu từ dãy <1, 1, 1, 1, …> thì bằng cách nhân với chỉ số 2 lần, ta sẽ được kết quả mong muốn
<0.0, 1.1, 2.2, 3.3, …> = <0, 1, 4, 9, …>
Vấn đề là ở chỗ phép đạo hàm không chỉ nhân số hạng dãy số với chỉ số mà còn dịch chuyển sang trái 1 vị trí. Thế nhưng, quy tắc 3 dịch chuyển phải cho chúng ta cách để vô hiệu hoá tác động này: nhân hàm sinh thu được cho x.
Như vậy cách làm của chúng ta là bắt đầu từ dãy số <1, 1, 1, 1, …>, lấy đạo hàm, nhân với x, lấy đạo hàm rồi lại nhân với x.
<1, 1, 1, 1, …> 1/(1-x)
<1, 2, 3, 4, …> (d/dx)(1/(1-x)) = 1/(1-x)2
<0, 1, 2, 3, 4, …> x/(1-x)2
<1, 4, 9, 16, …> (d/dx)( x/(1-x)2) = (1+x)/(1-x)3
<0, 1, 4, 9, 16, …> x(1+x)/(1-x)3
Như vậy hàm sinh cho dãy các bình phương là x(1+x)/(1-x)3.
3. Dãy số Fibonacci
Đôi khi chúng ta có thể tìm được hàm sinh cho các dãy số phức tạp hơn. Chẳng hạn dưới đây là hàm sinh cho dãy số Fibonacci:
<0, 1, 1, 2, 3, 5, 8, 13, …> x/(1-x-x2)
Chúng ta thấy dãy số Fibonacci biến đổi khá khó chịu, nhưng hàm sinh của nó thì rất đơn giản.
Chúng ta sẽ thiết lập công thức tính hàm sinh này và qua đó, tìm được công thức tường minh tính các số hạng tổng quát của dãy số Fibonacci. Dĩ nhiên, chúng ta đã biết công thức tính số hạng tổng quát của dãy Fibonacci trong phần phương
pháp giải các phương trình sai phân tuyến tính hệ số hằng. Nhưng điều này
không ngăn cản chúng ta một lần nữa tìm cách giải thích sự xuất hiện của
phương trình đặc trưng, cách xử lý trường hợp nghiệm kép thông qua công cụ hàm sinh. Hơn nữa, phương pháp hàm sinh còn giúp chúng ta giải quyết hàng loạt
các bài toán về
dãy số
đệ quy khác nữa, trong đó có những phương trình mà
chúng ta hoàn toàn bó tay với các phương pháp khác.
Tìm hàm sinh
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links