BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINH
Đào Thị Thu Hường
VÀNH CÁC CHUỖI LUỸ THỪA HÌNH THỨC
VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thành phố Hồ Chí Minh – 2019
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINH
Đào Thị Thu Hường
VÀNH CÁC CHUỖI LUỸ THỪA HÌNH THỨC
VÀ ỨNG DỤNG
Chuyên ngành : Đại số và lí thuyết số
Mã số
: 8460104
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
PGS.TS. MỴ VINH QUANG
Thành phố Hồ Chí Minh – 2019
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn thạc sĩ khoa học giáo dục với đề tài: Vành
các chuỗi luỹ thừa hình thức và ứng dụng là công trình nghiên cứu của riêng
tôi. Các nội dung và kết quả trong luận văn là trung thực và chưa từng được
công bố trong bất kì một công trình nào khác.
Tác giả
Đào Thị Thu Hường
LỜI CẢM ƠN
Lời nói đầu tiên, tôi xin bày tỏ lời cảm ơn sâu sắc và chân thành nhất đến
với thầy PGS TS. Mỵ Vinh Quang, người đã nhận hướng dẫn tôi, người đã
giúp đỡ tôi rất rất nhiều trong việc làm quen với công việc nghiên cứu và tận
tình chỉ dạy, động viên tôi hoàn thành luận văn này.
Bên cạnh đó, tôi xin trân trọng cảm ơn đến thầy TS. Trần Huyên – Người
cho tôi con đường yêu môn Đại số và quyết tâm theo đuổi ngành Đại số và lý
thuyết số. Tôi xin chân thành cảm ơn đến Ban Giám Hiệu và các thầy cô trong
tổ Toán của Trường TH, THCS, THPT Ngô Thời Nhiệm Quận 9 TP.HCM nơi
tôi công tác, đã tạo mọi điều kiện thuận lợi để tôi hoàn thành tốt khóa học của
mình. Xin chân thành cảm ơn ban lãnh đạo và chuyên viên Phòng Sau đại
học, Ban chủ nhiệm và giảng viên khoa Toán - Tin của Trường Đại học Sư
phạm Tp. Hồ Chí Minh đã tạo thuận lợi cho chúng tôi trong cả khóa học.
Tôi cũng rất cảm ơn các bạn, các anh chị học cùng Khóa 27 đã cùng tôi
chia sẻ những buồn vui, những khó khăn trong suốt quá trình học tập, đặc biệt
là bạn Nguyễn Thanh Ngọc lớp LL&PPDHBM Toán đã đồng hành, động viên
tôi cùng học tập . Cuối cùng tôi xin dành trọn tấm lòng biết ơn của mình đến
bố mẹ ruột, ba mẹ chồng, chồng và anh em tôi đã luôn động viên, giúp đỡ tôi
trong suốt thời gian qua. Đặc biệt là cảm ơn con gái đã thức cùng mẹ trong
những ngày mẹ ôn bài thi.
Tôi xin chân thành cảm ơn.
Đào Thị Thu Hường
MỤC LỤC
Trang phụ bìa
Lời cam đoan
Lời cảm ơn
MỞ ĐẦU ..................................................................................................... 1
Chương 1. VÀNH CÁC CHUỖI LŨY THỪA HÌNH THỨC ..................... 3
1.1. Vành các chuỗi lũy thừa hình thức ............................................................. 3
1.2. Căn và lũy thừa hữu tỷ ............................................................................... 5
1.3. Đạo hàm hình thức ..................................................................................... 7
1.4. Một số công thức ........................................................................................ 8
1.5. Hàm sinh của dãy số ................................................................................... 9
Chương 2. MỘT SỐ ỨNG DỤNG CỦA VÀNH CÁC CHUỖI LŨY
THỪA HÌNH THỨC – HÀM SINH ....................................... 10
2.1. Ứng dụng vành các chuỗi lũy thừa hình thức để nghiên cứu dãy số. ...... 10
2.2. Ứng dụng vành các chuỗi lũy thừa hình thức để giải các bài toán
đếm. ......................................................................................................... 17
2.3. Ứng dụng vành các chuỗi lũy thừa hình thức trong việc chứng minh
các công thức tổ hợp. .............................................................................. 24
2.4. Ứng dụng vành các chuỗi lũy thừa hình thức để giải một số bài toán
bậc phổ thông. ......................................................................................... 27
KẾT LUẬN ................................................................................................... 32
TÀI LIỆU THAM KHẢO ............................................................................ 33
1
MỞ ĐẦU
Trong toán học, việc sử dụng các kiến thức toán cao cấp để giải quyết
các bài toán ở phổ thông là điều rất quan trọng. Nó không chỉ giúp người làm
toán có nhiều phương pháp lựa chọn lời giải, mở rộng tầm hiểu biết toán học
mà còn phát huy được sự thông minh và sự sáng tạo, tầm bao quát toán, mở
rộng bài toán theo nhiều hướng khác nhau.
Như chúng ta đã biết các vấn đề liên quan đến dãy số là một phần quan
trọng của đại số và toán giải tích. Khi tiếp cận vấn đề này các em học sinh giỏi,
sinh viên và khá nhiều thầy cô giáo phổ thông thường phải đối mặt với rất
nhiều bài toán khó và lúng túng khi tìm cách giải.
Trong các kỳ thi học sinh giỏi Quốc gia, thi Olympic toán quốc tế, thi
Olympic toán sinh viên giữa các trường Đại học, cao đẳng, các bài toán liên
quan đến dãy số cũng hay được đề cập và thường rất khó, đòi hỏi người học,
người làm toán phải có tầm hiểu biết rộng và rất sâu sắc các kiến thức về dãy
số và chuỗi mới đưa ra các phương pháp giải toán hay và hoàn thiện được bài
toán.
Để phục vụ cho việc bồi dưỡng học sinh giỏi và học tập, nghiên cứu các
n
bài toán về dãy số, các bài toán tổ hợp, các bài toán trong lý thuyết số…Vành
a x n
0
n
các chuỗi lũy thừa hình thức đã tỏ ra rất có ích và nó là một công cụ
hữu hiệu để giải quyết các vấn đề trên.
Dưới sự hướng dẫn của PGS TS Mỵ Vinh Quang, tác giả đã quyết định
chọn đề tài luận văn :” Vành các chuỗi lũy thừa hình thức và ứng dụng ”.
Nội dung luận văn gồm có 2 chương:
Chương 1. Vành các chuỗi lũy thừa hình thức.
2
Trình bày định nghĩa và một số tính chất cơ bản của vành các chuỗi lũy
thừa hình thức và hàm sinh.
Chương 2. Một số ứng dụng của vành các chuỗi lũy thừa hình thức và hàm
sinh.
Trình bày cách ứng dụng của vành các chuỗi lũy thừa hình thức để
giảiquyết các bài toán về dãy số, các bài toán tổ hợp, các bài toán trong lý
thuyết số, các bài toán sơ cấp…
Mặc dù đã cố gắng rất nhiều, nhưng luận văn sẽ không tránh khỏi những
thiếu sót. Rất mong nhận được sự đóng góp từ quý thầy cô và đọc giả.
3
Chương 1. VÀNH CÁC CHUỖI LŨY THỪA HÌNH THỨC
1.1. Vành các chuỗi lũy thừa hình thức
2
...
.
a 0
a x a x 1
2
a i
i a x a i i
x
i
0
i
,
f
1
f
Ký hiệu vành các chuỗi lũy thừa hình thức một biến trên trường là:
0 x , được gọi là một chuỗi lũy
a x i
x
0
i
với Mỗi phần tử
x
thành một vành thừa hình thức của biến x với các hệ tử thuộc . Để biến
n
f
,n a x g
giao hoán có đơn vị ta cần các phép toán sau:
n
b x n
x
n
n
f
g
,
0;1;...
n
a n
b n
ta định nghĩa Cho
n
f
g
a
n
b x n
n
n
fg
. 1.1.1
c x n
c n
k n k
a b
n
k
và
2
x
0.
x
...
1 0.
Để thuận tiện, ta kí hiệu 0 cho chuỗi luỹ thừa với tất cả các hệ số bằng 0
và gọi chúng tương ứng là (chuỗi luỹ
và 1 cho chuỗi luỹ thừa
2
0.
x
0.
x
...
thừa) “không” và “đơn vị”. Một cách tổng quát hơn, với hằng số , ta vẫn
. Cuối cùng, ta kí giữ kí hiệu cho chuỗi luỹ thừa hình thức
hiệu A cho chuỗi luỹ thừa nhận được từ A bằng cách đổi dấu hệ số của nó.
x
là một vành giao hoán có đơn vị, có nghĩa là các phép Nói rằng
x
,
có các tính chất sau đây và việc kiểm tra là rất toán ” + “ và ” . “ trên
A A x
B B x C C x ,
x
đơn giản: với mọi ,
0
0
A
A A
0
A
C A
A B
A B B A
B C
A
A A A .1 1.
.
.
.
.
.
.
.
.
A B B A A B C
A B A C
A
A B C A B C . A .0
0.
0
1 2 3 A 4 A 5 6 7 8 9
4
Lưu ý rằng các đẳng thức (4), (7) nói rằng các phép toán ‘’+, . “ có tính kết hợp, các đẳng thức (2), (6) nói rằng các phép toán “+” và “. “ là giao
hoán.
Tất cả các tính chất mà chúng ta nêu lên ở trên là các tính chất quen
x
x
. Giống như với , đẳng thức (9) có phát thuộc trên vành các đa thức
,A B
0
biểu đảo sau đây
A B thì hoặc
x
0A
0.
B
Mệnh đề 1.1.1. Nếu sao cho .
hoặc
A
0,
B
0
Chứng minh.
. Gọi
,a b tương ứng là các hệ số khác 0 với
0
a b .
Thật vậy, giả sử
0
AB .
chính là hệ số 0 của AB với chỉ chỉ số nhỏ nhất của A và B . Thế thì
A
B
số nhỏ nhất. Nói riêng
x
x
1
AB . Phần tử B như vậy nếu tồn tại là duy nhất và được gọi là nghịch
Định nghĩa 1.1.2. Ta nói là khả nghịch nếu tồn tại sao
cho
1A hay
1 A
0A . Mặt khác, nếu A là nghịch
. đảo của A . Ta còn kí hiệu nghịch đảo của A bởi
Nói riêng, nếu A là khả nghịch thì
đảo của B thì B là nghịch đảo của A .
5
x
lập thành một vành giao hoán Mệnh đề 1.1.3. Với các phép toán trên, có đơn vị.
Chứng minh.
i
f
Việc kiểm tra các tiên đề của vành là thoả mãn.
a x i
là khả nghịch khi và chỉ
i
0
0.
Định lý 1.1.4. Chuỗi lũy thừa hình thức
a 0
khi
n
b x n
Giả sử f có nghịch đảo, nghĩa là
1 f
0
n
0.
1
f
1
Chứng minh.
. 1 /
f và theo (1.1.1) ta có
c 0
a b . 0 0
a 0
vì thế Khi đó
n
c 1, n
k n k
a b
Hơn nữa, trường hợp này (1.1.1) cho ta biết rằng với
k
n
1 1.1.2
b n
a b k n k
k
1
1 a 0
,...
, từ đó ta tìm được trong 0
b b 2,
0
,...
duy nhất. Điều này xác định 1
Ngược lại, giả sử
a . Khi đó ta có thể xác định 0
b b 1, 0
n
f
.
từ
n
b x là nghịch đảo của
n
(1.1.2), và kết quả chuỗi
,m n là các số nguyên với
1.2. Căn và lũy thừa hữu tỷ
x
1 n
Cho A x có hệ số tự do bằng 1 và
n A x là chuỗi luỹ thừa
A x
B x
n dương. Ta định nghĩa luỹ thừa
n
hay
A x
. Một cách tổng quát hơn, ta định với hệ số tự do bằng 1 sao cho B x
m n
n A x
6
m
n
m
A x
, hay nghĩa A x như là chuỗi luỹ thừa B x với hệ số bằng 1 duy
.
nhất thoả mãn B x
A x
x
B
có hệ số tự do bằng 1 và n là một số Định lý 1.2.1. Cho
B x
x
nB
A .
với hệ số tự nguyên dương. Tồn tại duy nhất một phần tử
do bằng 1 sao cho
A
Để chứng minh định lý này ta có bổ đề sau
A x
x
nA cũng có hệ số tự do bằng 1. Một cách cụ thể hơn, nếu
2
nA
...
1
...
A
na
1
(đa thức của
Bổ đề 1.2.2. Nếu có hệ số tự do bằng 1 thì với mọi số
b x 1
b x 2
trong đó k b
k
a x 1
, ...,
a
, ...,
a 1
2
1
k
a ).
nguyên dương n , thì
Chứng minh. Bằng quy nạp theo n .
2
k
...
1
Chứng minh định lý 1.2.1.
...
A A x
a x 1
a x 2
a x k
2
k
B
...
...
1
Theo bổ đề 1.2.2, ta có
b x 1
b x 2
b x k
n
2
k
B
x
...
f
,...,
x
...
1
nb x 1
nb 2
f b 1 1
nb k
k
b 1
b k
1
,...,
,...,
Viết và giả sử
f b 1 k
k
1
b
1
k
b với mọi k .
nB
Trong đó là một đa thức của 1 b
A tương đương với một hệ phương trình vô hạn
nb 1
nb 2
f a 1 1
a 1 a 2
,...,
nb k
b k
a k
1
f b 1
Từ đây, đẳng thức
,... :
7
b b 2,
Dễ thấy, hệ này xác định một nghiệm duy nhất 1 trước hết 1b xác
2b xác định bởi
1b
k
định duy nhất bởi phương trình đầu tiên, rồi
b 1, k
,...,
.
k
1
b
và phương xác định bởi phương trình trình thứ 2, và một cách truy hồi, với mọi
thứ k và các giá trị 1 b
1.3. Đạo hàm hình thức
a
...
Định nghĩa 1.3.1.
A x
0
a x 1
x
2
Đạo hàm hình thức của là chuỗi lũy thừa
'A x cho bởi công thức
' A x
a 1
a x 2
1 k ka x k
...
k
1
''A x cho đạo hàm của
'A x và một cách
hình thức .
nA
Theo thông lệ, ta sẽ kí hiệu
A x , được định nghĩa bằng quy
x
tổng quát, cho đạo hàm thứ n của
.A
1n của
nạp như đạo hàm của đạo hàm thứ
A B ,
.
Ta có
Mệnh đề 1.3.2.
x ,
A const
0
A
'
A
'
.
'
'
' A B
'
'
'
A B AB
n
n
A
'
1 nA A n
',
0.
1 2 A B 3 4 5
A ' AB
Giả sử
1
A
'
6
A ' 2 A
n
A
'
n
n
,
.
0
7
A ' 1 n A
Hơn nữa, nếu A là khả nghịch thì
Chứng minh.
8
là hiển nhiên. Đẳng thức (4) cũng dễ dàng suy Các đẳng thức 1 , 2 , 3
ra từ việc so sánh hệ số lũy thừa của x trong hai vế. Công thức (5) được suy ra
1
A A và sử 1 .
bằng quy nạp theo n và bằng cách sử dụng (4).
n
nA
A
Để thiết lập (6), ta chỉ cần đạo hàm hai vế đẳng thức
1
'
n
n
1
A
A
dụng công thức Leibniz cho vế trái. Cuối cùng, do ta suy ra
n
1
1
1
A
1 n
'.
A
n A nA
Công thức Leibniz có thể được phát biểu cho một tích hữu hạn như sau
...
...
...
...
.
...
'
A A A 1 2 n
' A A A 1 2 n
' A A A 1 2 n
' A A A 1 2 n
mà việc chứng minh đơn giản là sử dụng qui nạp
Hệ quả 1.3.3. Hai chuỗi lũy thừa hình thức có cùng đạo hàm khi và chỉ khi
sai khác một hằng số. 1.4. Một số công thức
2
3
n
x
x
x
x
1
...
... 1.4.1
x
1
1
2
3
n
x
e
... 1.4.2
1
...
x n
x 1!
x 2!
x 3!
!
2
3
4
n
... 1.4.3
log
x
...
1
x
x 2
x 3
x 4
x n
1
2
3
4
n
n
1
x
...
... 1.4.4
x
ln 1
1
x n
x 2
x 3
x 4
Khai triển thành chuỗi lũy thừa hình thức một số hàm đơn giản sau đây:
2
n
3
5
1
n
1
sin
...
... 1.4.5
x
x
1
x 3!
x 5!
x 2 n
1 !
2
n
2
4
n
cos
...
... 1.4.6
x
1
1
x 2!
x 4!
x 2 ! n
k
x
x
1.4.7
1
k
k
n
x
1.4.8
1
k
n
n k n
1 x
1
n
n
2
3
4
5
x
x
x
x
x
x
1
2
5
14
42
1 4
... 1.4.9
1
2 n
n
1 x 2
n
1 1
x
k
1
k
2
3
4
5
1 2
x
6
x
20
x
70
x
252
x
2 k
k
1 4
8
9
7
x 6
12870
48620
... 1.4.10
3432
924
x
x
x
x
x
9
1.5. Hàm sinh của dãy số
n
được gọi là
f x
Cho dãy số na . Chuỗi lũy thừa hình thức
a x n
0
n
hàm sinh của dãy na .
10
Chương 2. MỘT SỐ ỨNG DỤNG CỦA VÀNH CÁC CHUỖI
LŨY THỪA HÌNH THỨC – HÀM SINH
ta có thể ứng dụng hàm
Nếu biết công thức truy hồi của dãy số na
sinh của dãy số này để tìm hoặc nghiên cứu số hạng tổng quát
na của dãy theo
phương pháp chung như sau:
n
2.1. Ứng dụng vành các chuỗi lũy thừa hình thức để nghiên cứu dãy số.
.
A x
a x n
là hàm sinh của dãy na
n
0
Bước 1: Ký hiệu
nx , rồi tính tổng theo
n , từ đó rút ra phương trình đối với
. A x
Bước 2: Nhân cả hai vế của công thức truy hồi với
. A x Từ đó dựa vào các công thức đã biết
suy ra
.na
Sau đây là một số ví dụ minh hoạ.
Bước 3: Giải phương trình tìm
,...
Cho dãy các số 0
a a 1,
2
n
1
0 .
a n
1
a n
thỏa mãn điều kiện a 0; 0
2.1.1
.
Hãy tìm dãy
.
na
Ví dụ 2.1.1.
.n
Đặt
A x
a x n
n
0
với
nx rồi tính tổng theo n ta được:
Nhân vế trái của
2.1.1
n
2
3
...
a 1
a x a x 2
3
a x 4
a x 1 n
n
0
2
3
/
x
a x a x 1
2
a x 3
a 0
a 0
...
A x x
Bài giải.
11
nx rồi tính tổng theo n ta được:
với
Tương tự, nhân vế phải của
2.1.1
n
n
n
2
x
2
x
1
a n
a x n
0
0
0
n
n
2
A x
x
1
n 1
Cho 2 vế bằng nhau, ta được:
2
A x
A x x
x
1
x
A x
1
x
1
1 2 x
1
x
A x
1
x
x
x
x
1
1
n
n
2
2 . x
x
x
x 1 2
AD 1.4.1
2 1 2
. x
n
n
0
0
2
2
3
3
2
3
2
2
x
x
x
x
x
...
2
2
3
2
...
x
x
x
2 2 1
1
... 3 2
x 1
n
2
n
Vậy
1
0 .
na
,...
Cho dãy các số 0
1, a a
a
2
a
n
thỏa mãn điều kiện 0;
n
1 .
1
n
n
a 0
2.1.2
Hãy tìm dãy
.
na
Ví dụ 2.1.2.
.n
Đặt
A x
a x n
n
0
nx rồi tính tổng theo n ta được:
Nhân vế trái của
2.1.2 với
Bài giải.
12
n
2
3
...
a 1
a x a x 2
3
a x 4
a x 1 n
n
0
2
3
...
/
x
a x a x 1
2
a x 3
a 0
a 0
1
A x x
nx rồi tính tổng theo n ta được:
Tương tự, nhân vế phải của
2.1.2 với
n
n
n
2
a
2
nx
n x
n
a x n
n
0
0
n 2
S
n 0 A x
S
nx
.n
Với
0
n
n
n
n
n
1
1
1
1
Sdx
x
C
x
x
C
x
C
1
1
1
x
n
1
n
1
n
1
1
1
n
0
n
0
n
n
n 1
0 1
x
n
x
S
2
2
2
x
1
0 1
0
n
x
x
x
1
1
1
Cho 2 vế bằng nhau, ta được:
1
x
2
A x
2
A x x
x
x
x
A x
2
1 1 x
1 2 x
x
1
2
2
2
x
x
A x
2
2
x
1 1 2
x
x
x
x
x 1
1 2
1 2
2 1
1
1
2
x
2 1 2
x
1
Áp dụng công thức (1.4.8) và (1.4.1)
1
1
n
2
3
n
1 2
3
4
...
x
x
x
n
x
...
1
2
n
0
x
n n
x
n
2
2
n
n
2
2
2
... 2
...
x
x
x
x
2. 1 2
x
1 2 1 2
0
n
13
n
1
n
1
n 2.2 = 2
n
n
Vậy
1
0 .
na
Xét dãy Fibonacci :
n
1;
0,
1 .
2.1.3
F n
F n
F n
F 0
F 1
1
1
Hãy tìm
.nF
Ví dụ 2.1.3.
.n
Xét hàm sinh:
F x
F x n
n
0
2.1.3
với
Nhân vế trái của
nx rồi tính tổng theo n ta được:
2
3
...
F x 4
2
3
x
2
3
...
/
x
F 0
F x F x 1
2
F x 3
F 0
F x F x
F x 1
F x x
với
Tương tự, nhân vế phải của
nx rồi tính tổng theo n ta được:
2.1.3
2
3
2
3
2
F x 3
F x F x 1
0
F x 2
...
x F x .
F x F x 1 F x
... F x x F x .
Cho 2 vế bằng nhau, ta được:
x
F x
x F x .
F x x
.
x
1
1
F x
F x
2
1 x
1
x
x x
1
1
1
F x
5
5
1
1
5
5
1
1
5
1
1
. x
. x
1
. x
. x
2
2
2
2
x . 1
j
j
1
1
5
1
5
j
j
x
x
.
2
2
0
0
j
j
5
n
n
5
1
5
1
1
n
0 .
nF
Vậy
2
2
5
Bài giải.
14
được xác định bởi:
Cho dãy số nu
1
2
2
*
u
u 2
,
n
2.1.4
n
n
n
2
1
u 1 u u
1
.
a
Tính
Đặt
lim n
.a
u n u n
Ví dụ 2.1.4.
n
2
u
...
Đặt
f x
u x n
0
u x u x 1
2
0 u và 0
n
0
2.1.4
Nhân vế trái của
nx rồi tính tổng theo n ta được:
với
n
2
u
x
...
n
2
u 2
u x u x 3
4
n
0
2
3
2
u
...
u
/
x
0
u x u x 1
2
u x 3
0
Bài giải.
u x 1
x
2
f x x
Tương tự, nhân vế phải của
2.1.4 với
nx rồi tính tổng theo n ta được:
n
n
n
u
u 2
x
2
n
n
u x n
1
u x 1 n
0
0
0
n
n
n
2
f x
f x x
Cho 2 vế bằng nhau, ta được:
15
x
2.
f x
2
f x x
.
1
f x
f x
2
f x x 1 x
2 x
1
1 2 x
x
x
x 2
1
1
1
x
f x
2 2 1
2
1
2
1
2
. 1 x
. 1 x
. 1 x
2 . 1
. 1 x
j
j
1
.
2
2
. 1 x
. 1 x
j
j
0
0
2 2
n
1
2
u
n
0 .
n
1
1
n 2
2 2
n
n
1
2
1
2
0
Do
1
1
n
Vậy
0 .
nu
1
n 2
2 2
n
1
2
1
a
2
1
n
lim n
lim n
u n u
n
2
1 1
1 2 2 1 2 2
2.
a 1
Vậy:
Dãy số
na được xác định như sau:
1
n n .2 ,
n
0 2.1.5
a 5 n
1
a 0 a n
Hãy tìm dãy
.na
Ví dụ 2.1.5.
.n
Đặt
f x
a x n
n
0
Bài giải:
16
2.1.5
nx rồi tính tổng theo n ta được:
Nhân vế trái của
với
n
2
3
...
a 1
a x a x 2
3
a x 4
a x 1 n
n
0
2
3
...
/
x
a x a x 1
2
a x 3
a 0
a 0
1
f x x
2.1.5
với
Tương tự, nhân vế phải của
nx rồi tính tổng theo n ta được:
n
n
n
n
n
5
a
n .2
x
n .2
x
n
a x n
5
0
0
n
n 5
S
0
n f x
n
n
S
n .2
x
.
Với
n
0
n
1
n
n
1
Sdx
n .2
C
1
n .2 .
x
C
x n
1
n
1
1
n
0
n
0
n
n
n
n
1
1
2
x
2
x
C
n
1
1
0
n
0
n
n
n
n
1
2
x
2
x
C
1
1
1
n
n
n
n
1
.
2
x
C
1 2
x
n
1
n 0 1
n
0
n 1 2 0 1 1 2 1 2 1
1
2
x
n
n
2
x
S
2
2
2
x
1 1 2
n
0
x
x
x
1 2
1 2
1 2
Cho 2 vế bằng nhau, ta được:
17
1
2
x
5
f x
2
f x x
x
x
2
x
.
f x
2
1 2 1 x
1 5 x
x
1 2
2
2
6
x
x
1
f x
2
2
x
1 1 5
x
x
x
x
1 2
1 2
1 5
1 5
4
.
.
.
f x
2
x
x
1 11 9 1 5
x 2 1 1 9 1 2
x
n
n
n
5
2
x
x
n
x
1 2
11 9
1 9
1 1 3 1 2 1 3
n
n
n
0
0
0
n
11.5
2
n n 2 3
n
n
n
n
.5 + .2
.
n 1 .2 =
0 .
a n
Vậy
11 9
1 9
1 3
9
Hàm sinh là một công cụ rất hữu hiệu để giải quyết các bài toán đếm phức
tạp, sau đây tôi sẽ đưa ra một số ví dụ minh hoạ.
2.2. Ứng dụng vành các chuỗi lũy thừa hình thức để giải các bài toán đếm.
Giả sử có một kho trái cây gồm đủ nhiều các quả chuối, ổi, xoài và
bưởi. Với mỗi n, ta sẽ thử đếm xem có bao nhiêu cách tạo thành một giỏ trái
cây gồm tổng cộng n quả sao cho số chuối là chẵn, số ổi chia hết cho 5, số
xoài không vượt quá 4, số bưởi không vượt quá 1?
Ví dụ 2.2.1.
Số cách tạo thành một giỏ trái cây thoả yêu cầu bài toán bằng số cách
k
n
k
k
dưới dạng
trong đó
biểu diễn n
k 1
2
4
3
k 2,
k 5,
k 4,
1
ik là các số tự nhiên, . Số cách tạo thành một giỏ trái cây thỏa yêu cầu bài
k 1
2
3
4
toán chính là hệ số của
nx trong khai triển của chuỗi luỹ thừa hình thức:
Bài giải.
18
2
4
5
2
3
4
x
x
x
10 x
x
x
x
x
x
1
... 1
... 1
1
2
3
4
.
x
x
x
x
x
5
2
. 1
. 1
1
1 x
A x 1 x
2
3
4
x
x
x
x
x
. 1
. 1
2
3
4
x
x
x
x
x
x
1 x
1 1 1
1
. 1
. 1
2
1
2
2
x
x
x
x
...
1 2
3
...
2
1
x
1
chính là số cách chọn hoa quả
Hệ số của
A x
nx trong khai triển của
cần tìm.
Dễ thấy hệ số của
A x
nx trong
n 1.
bằng
1.
n
Vậy số cách chọn hoa quả cần tìm là
Có bao nhiêu cách đổi tờ n nghìn đồng (n nguyên dương) thành hai loại
tiền 1.000 đồng và 2.000 đồng?
Ví dụ 2.2.2.
Số cách đổi tờ n nghìn đồng thành hai loại tiền 1 nghìn đồng và 2 nghìn
n
k
trong đó
đồng bằng số cách biểu diễn n dưới dạng
k 1
2
,k k là các số 1
2
. Số cách đổi tờ n nghìn đồng thỏa yêu cầu bài toán chính là hệ
2 2k
tự nhiên,
số của
4
2
2
n
...
x
x
x
x
A x
a x n
nx trong khai triển của chuỗi luỹ thừa hình thức: 1
... 1
n
0
1
.
.
2
2
1
x
1
x
1
1 x
1
x
1
2
2
3
x
3
x
x
...
x
... 1
n
/ 2
x
.
n
x 1
1 1 2
n
0
n
/ 2
1.
Vậy số cách đổi là
na
Bài giải.
19
Tiếp theo, ta trình bày ứng dụng của hàm sinh để nghiên cứu số “mất trật
tự”
Cho trước tập có n phần tử. Ta định nghĩa số mất trật tự
nD là số các hoán vị không có điểm bất động trên một tập n phần tử cho trước. Một phần tử
được gọi là điểm bất động của hoán vị nếu nó bị cố định bởi hoán vị đã cho.
Ví dụ 2.2.3. Định nghĩa số mất trật tự.
n
...
n
1
nD
1 2!
1 ! n
! 1 1!
2.2.1
Ví dụ 2.2.4. Số mất trật tự được tính bởi công thức
Ta sử dụng phương pháp hàm sinh để chứng minh công thức trên.
Cố định một tập S với n phần tử. Dễ thấy mỗi hoán vị của S có đúng k
k
0,1,...,
n
điểm bất động với
nào đó. Như vậy, tập các hoán vị của S được
phân hoạch thành các tập con các hoán vị với đúng k điểm bất động với
0,1,...,
k
n
n
. Với mỗi 0 k
, ta hãy đếm số các hoán vị của S với đúng
k điểm bất động. Việc cho một hoán vị của S với đúng k điểm bất động
tương ứng với việc chọn một tập con k phần tử A của S (tập các điểm bất
động) và một hoán vị không có điểm bất động trên tập
\S A . Có
cách
n k
chọn A như vậy và
\S A . Việc
n kD hoán vị không có điểm bất động trên tập
phân hoạch các hoán vị thành các tập con các hoán vị với đúng k điểm bất
n
động 0 k
n
với dẫn tới n
n
!
.
n k
k
k
0
D
n
1
!
Bằng cách chia hai vế cho !n ta thu được 1 ! k
D n k n k
k
0
Chứng minh.
20
n
x
với
n
0
Dễ thấy rằng vế trái chính là hệ số thứ n của tích của
2
n
1
x
x
...
x
còn vế phải rõ ràng là hệ số thứ n của
.
n
0
x
1
D n n !
1 n ! 1
n
x
e
Đặt
n
x . n ! 0
Thế thì ta có
x
n
n
e
x
x .
n
n
0
D n n ! 0
Nhận xét rằng ta có công thức quen thuộc
n
x
x
e
.
n 1 . n
!
1 x e
0
n
Suy ra
n
x
2
x
e
x
...
x
1
D n n !
0
n
n
n
x
2
x
1
...
x
... .
1 n
x 1!
!
... 1
2.2.1
Từ đây ta thu được
Để tiếp tục, ta giới thiệu cách sử dụng hàm sinh để nghiên cứu số Catalan.
n
giác lồi cho trước
2
nC là số các cách chia một hình
bởi
2n đường chéo của nó, đôi một không cắt nhau bên trong đa giác, thành các tam giác. Một cách phân chia như vậy được gọi là một tam giác
1
C .
Ta
có
với mọi
0n ,
phân.
Ta
quy
ước
0
2
n
. 2.2.2
C
n
n
n
1 1
Ví dụ 2.2.5. Gọi
Chứng minh.
21
Trước hết, ta xác định công thức truy hồi cho số Catalan
nC . Gọi đa giác
đã cho là
... n
2
2
1
1
A A A . Trong mỗi tam giác phân, cạnh
2nA A phải thuộc đúng
2,...,
n
1
. Tương ứng với mỗi
một tam giác, chẳng hạn
A A A 1 i n
i 2 ,
i
2,...,
n
1
. Việc tam giác phân của
... n
n
2
i
A A nhận 1 2
A A A làm một tam 1
giác tương ứng với việc tam giác phân các đa giác
A A 1
2...,
A và i
2
1
n
i
A A A . ...
...
Số các tam giác phân của
A A bằng 1... i
2
i
1n
2iC và của
A A A là 1 n
iC . Từ đó
suy ra
C
...
. 2.2.3
n
C C 0
n
0
1
C C 1 n
Chú ý rằng, nếu ta không sử dụng hàm sinh thì rất khó để suy ra (2.2.2)
từ (2.2.3). Ta sử dụng hàm sinh sẽ dễ dàng hơn. Đặt
n
C
...
...
f x
C x n
0
C x 1
1
hay
Thế thì quan hệ (2.2.3) dẫn đến
f x
2 x f x .
x 1 4 .
xf x
1 2
2
1 2
1 4 . x
Như vậy,
Thế nhưng, bằng cách để ý đến hệ số tự
xf x
do của hai vế, ta thấy rằng đẳng thức trên phải xảy ra với dấu” +”. Cuối cùng,
bằng cách sử dụng công thức (1.4.9) cho biểu thức trên ta thu được đẳng thức
2
n
.
C
n
n
n
1 1
Để kết thúc phần này, chúng tôi xin giới thiệu ứng dụng của hàm sinh để
nghiên cứu số Stirling.
Số Stirling đóng vai trò quan trọng trong lý thuyết số, đặc biệt là trong
việc xây dựng các hàm số số học. Số Stirling được định nghĩa như sau:
Định nghĩa 2.2.6. Số Stirling
22
n
Cho , n k là số tự nhiên và 1 k
. Ký hiệu
số cách phân hoạch tập
n k
được gọi là số Stirling loại 2. Sử dụng công
1, 2,..., n thành k lớp. Số
n k
cụ hàm sinh ta có thể tìm được công thức tính của số Stirling loại 2.
1, 2, 3, 4, 5 thành 2 lớp.
1 2345 ; 2 1345 ; 3 1245 ; 4 1235 ; 5 1234 12 345 ; 13 245 ; 14 235 ; 15 234 23 145 ; 24 135 ; 25 134 34 125 ; 35 145 45 123
15
cách phân hoạch.
Vậy có
5 2
Ví dụ 2.2.7. Phân hoạch
n ta có
n
k
k r
. (2.2.4)
1
!
r
r
1
r ! r k
n k
Mệnh đề 2.2.8. Với hai số nguyên dương n, k thoả mãn 1 k
Đầu tiên ta chứng minh công thức
n
n
n
k
n k ,
1 2.2.5
0, 0 ;
k
k
k
1 1
0 0
1
Ta xét 2 loại:
Chứng minh:
là 1 lớp.
Dễ thấy số cách phân hoạch loại 1 chính là:
n k
1 1
Loại 1: Số cách phân hoạch n thành k lớp trong đó n
n có ít nhất 1 phần tử nữa.
Loại 2: Số cách phân hoạch n thành k lớp không là loại 1. Nghĩa là lớp chứa
23
.
k
Do đó có tất cả
cách phân hoạch tập n thành k lớp loại 2.
n k
1 n
n
k
.
Vậy ta có:
k
k
n k
1 1
1
Bây giờ ta xét hàm sinh :
n
x
2.2.6
B x k
n
n k
Nhân cả hai vế (2.2.5) với
nx rồi tính tổng trên n, ta có
k
1;
B x k
xB k
kxB x k
B x 0
1
1 .
x
B x k
B k
1
1
x x kx
Và cuối cùng ta đánh giá
k
n
x
k
0 . 2.2.7
B x k
x
x
kx
1 2
n
1
x 1 3 ... 1 x
n k
j
1,...,
k
,
Suy ra tồn tại
thỏa:
j
k
x
x
x
kx
1 2
j
1
1
3 ... 1
1
j jx 1
x
,1r
k
r
, nhân cả hai vế với 1 rx
và đặt
. Ta
Ta tìm , cố định
1 r
thu được kết quả
r
r
r
r
r
r
r
/ k r
1 2 /
1 1 /
1 /
... 1
1 1 /
... 1
1
k
1
k r
k
r
1
2.2.8
1 !
k
r
r
r 1 !
n
Cho
f x
a x n
k
kx trong khai triển của
Ta kí hiệu
f x .
ka
x
là hệ số của
24
Từ (2.2.7) và (2.2.8) ta thu được, cho n
k
k
x
n
x
x
kx
1
1 2 ... 1 x
n k
n k
=
x
kx
x
1 1 2 ... 1 x
1
k
n k
=
x
k
1
r 1 rx
r
1
k
n k
=
x
r
1 1 rx
r
1
k
n k
=
r
r
r
1
k
1
k
k r
n k
=
r
1
!
r
k
r
r
1
r 1 !
n
k
k r
=
n k ,
1
0
r
!
r
1
r r k !
2.3. Ứng dụng vành các chuỗi lũy thừa hình thức trong việc chứng minh
các công thức tổ hợp.
n
Chứng minh rằng
, = 0,1, 2,... 2.3.1
F n
k n k
1
k
0
Ví dụ 2.3.1.
Đặt
f n
k
k
0
k n
nx và cộng lại, ta được:
Nhân cả hai vế của
2.3.1 với
n
F x
x
0
n
k
k n k
n
F x
0
k
n
k n k
x
Bài giải.
25
k
n k
x
F x
x
0
k
n
k n k
n k
Đặt r
, ta được:
k
k
r
x
F x
x
r
k
0
r
. Do đó
Chúng ta nhận ra bên trong tổng trực tiếp như là 1
kx
k
k
k
x
x
x
x
F x
1
2
2
1
x
1 x
0
0
k
k
Hàm sinh bên vế phải thì quen thuộc, đó là hàm Fibonacci theo công thức
và chúng ta thu được
(2.1.3). Do đó f n
1n
F
n
0,1, 2,...
F n
1
k
0
k n k
m n k
m n ,
k 2
0 2.3.2
Chứng minh rằng
k
k
k
k m
m n n
Ví dụ 2.3.2.
Nhân vế trái (2.3.2) với
nx , tính tổng trên
0n ta được
m
x
k
k
n k
x
x
x
m
1
m k
n k m
m k
0
k
n
k
x
1
m
m
x
m
1
1 x
1
x
m
.
m
1
x
x
1 1 1
Nhân vế phải (2.3.2) với
nx , tính tổng trên
0n ta được
Bài giải.
26
k
k
n
2
x
m k
m k
x
1
0
k
n
k
1
2 x 1 x
n k
m
x
2 x 1 x
1
m
m
1
x
1 x
1 1 1
Cho hai tổng trên bằng nhau ta có điều phải chứng minh.
n
n k
2
f
n
0 2.3.3
n
Tính tổng
0
k
n k 2 k
Ví dụ 2.3.3.
nx , tính tổng trên
Đặt F là hàm sinh của dãy,nhân cả 2 vế
2.3.3 với
0n , và hoán vị hai tổng bên vế phải ta được
k
n
n
F
x
2
2
k
n
0
n k k 2
k
n k
k
x
x
2
2
2
k
n
0
k
2
x
2
k
k
x
2
2
k
2
1
k
x
n k k 2 1 2
k
x
2
x
1 1 2
k
0
x
1 2 1
x
x
1 1 2
1
2
x
x
1 2 1 2 x 1 x
1 4
n
n
4
x
x
2 3
1 3
x
x
2 3 1 4
1 3 1
Bài giải.
27
Bây giờ rất dễ để đọc hệ số của
nx ở hai vế và ta có kết quả sau
2
n
1
n
2
n k
2
f
n
1
0
n
3
k
0
n k 2 k
2.4. Ứng dụng vành các chuỗi lũy thừa hình thức để giải một số bài toán
Hàm sinh còn là một công cụ khá hữu ích trong việc giải các bài toán sơ
cấp ở bậc trung học phổ thông, nhất là trong các kỳ thi học sinh giỏi. Dưới đây
chúng tôi xin giới thiệu một số bài toán như vậy.
bậc phổ thông.
Cho trước số tự nhiên
1n . Có bao nhiêu số tự nhiên chia hết cho 3, có n
3; 4;5; 6 ?
chữ số và các chữ số thuộc
Ví dụ 2.4.1. (PTNK 2009)
S
,
Gọi số cần tìm có dạng
3; 4;5;6
2...
1
n
i
Đặt
3; 4;5; 6 và có tổng các chữ số bằng k.
ka bằng các số có n chữ số thuộc
,
k
.
S
3; 4;5;6 ,
1,...,
n i
Suy ra ka bằng các bộ số
i
n
3
4
5
6
x
x
x
x
kx
trong khai triển
Và bằng hệ số của
f x
k
6
n
...
...
Nghĩa là
f x
a 0
a x 1
a x k
a x 6 n
Hay
f x chính là hàm sinh của dãy ka
...
..
. 0
3k
6n
Khi đó số các số chia hết cho 3 bằng
a 0
a 3
a 3
k
n
6
T
k
Vậy ta cần tìm
a 3
k
0
Đặt
cos
i
sin
2 3
2 3
1
k nếu k chia hết cho 3.
Bài giải.
28
1
k nếu k không chia hết cho 3.
k
k
k
1
0
2
với mọi k không chia hết cho 3.
3 1 k 1
Ta có
f
...
a 0
a 1
a 2
a m
f
...
a 0
2 a a 1 2
m a m
m
f
...
a 0
m
m
f
f
f
...
2
2
1 2 1
a 1
a m
2 a 1 2
1
T 3
4 a 2
k
2 a m 1
n
f
f
f
1
4
2
a 3 0 a 3 3 2
T
3
3
Cho số nguyên dương k. Tìm số các số tự nhiên n 10k
thỏa mãn đồng
thời các điều kiện sau:
a) n chia hết cho 3
b) các chữ số trong biểu diễn thập phân của n thuộc tập
2; 0;1;5 .
Ví dụ 2.4.2. (VMO 2015)
S
,
Gọi số cần tìm có dạng
2;0;1;5
2...
1
k
i
2; 0;1;5 .và có tổng các
có các chữ số thuộc
Đặt ma
bằng các số 10k
chữ số bằng m .
Suy ra ma bằng số các bộ số
,
2;0;1;5 ,
m .
S
k i
1,...,
i
k
2
5
x
x
x
Và bằng hệ số của
kx trong khai triển
f x
1
Bài giải.
29
m
5
k
...
...
Nghĩa là
f x
a 0
a x 1
a x m
a x 5 k
Hay
f x chính là hàm sinh của dãy
ma
a 3
a l
a Khi đó số các số chia hết cho 3 bằng 0
... ..
3 l
T
a l
Vậy ta cần tìm
l 3
Đặt
cos
i
sin
2 3
2 3
1
k nếu k chia hết cho 3.
1
k nếu k không chia hết cho 3.
k
k
k
1
0
2
với mọi k không chia hết cho 3.
3 1 k 1
f
...
a 0
a 1
a 2
a m
f
...
a 0
2 a a 1 2
m a m
m
f
...
a 0
m
m
f
f
f
2
...
2
1 2 1
a 3 0
a 1
a m
2 a m 1
2 a 1 2
1
4 a 2
f
f
f
1
3 T 2
T
2
k
4
3 k k
3
Vậy
k
4
2
T
nếu k chia hết cho 3
3
k
4
1
T
nếu k không chia hết cho 3.
Hoặc
3
30
,...,
Một dãy các số nguyên
a được gọi là p-cân bằng nếu các tổng n
a a , 1 2
a
a
a
...
k
1, 2,...,
p
.
là bằng nhau với mọi
(Chẳng hạn dãy
k
k
2
p
k p
2
là 3 cân bằng). Giả sử dãy
a 1
a 1, 2
a 2, 3
a 3, 4
a 4, 5
a 3, 6
,...,
3, 5, 7,11,13,17
p
, chứng minh rằng
a a , 1 2
a là p – cân bằng với 50
...
0.
a 1
a 50
Ví dụ 2.4.3. (Leningrad 1991)
n
...
...
Gọi
f x
a x n
a x 1
là hàm sinh của dãy na như trên.
Cho p số nguyên tố
2
2
cos
i
sin
Đặt
k
k p
k p
k
1,...,
p
1.
Với
1p k
m
Nếu m không chia hết cho p thì
1, k do đó
1
1
0
...
m k
m p k
mp 1 k m 1 k
b
a
a kp
thì b
do đó
Hơn nữa, nếu
b modp
a k
k
Ta có nếu f là p – cân bằng thì
a
...
a
...
...
... S
a 1
p
a 2
2
p
a 2
p
p
a 1
Khi đó
Bài giải.
31
n
f
...
a n k
a k 1
p
p
1
1 2
k
...
p k
p k
a k 1
a 1
a 1 2
p
2
2
...
p k
a k 2
a 2
p
p
2
a
...
p k
a 2
2
...
...
a 2
a 2
a 1
k
p
p
p
a 1
a 1 2
p
p
1
a
a
a
...
...
p
p
p
p
a 2
p
1
1
...
p
p
2
1
S
0
...
k
k k
k
p k k k
k
,...,
Vậy nếu 1
a a , 2
a là p – cân bằng thì n
f
0
1,...,
p
1
k
k
3, 5, 7,11,13,17
p
là p – cân bằng với
x f
có ít nhất
x f
50
3 1
5 1
7 1
nghiệm khác 0.
11 1
13 1
17 1
f
0
Ngoài ra
0
f
0.
Suy ra
x có 51 nghiệm nên
f x
...
0
a Vậy 1
a 50
32
KẾT LUẬN
Trong luận văn này tôi đã trình bày các vấn đề về vành các chuỗi lũy
thừa hình thức và một số ứng dụng của vành các chuỗi lũy thừa hình thức –
hàm sinh. Tôi đã nghiên cứu và tìm ra được 4 ứng dụng của vành các chuỗi lũy
thừa hình thức – hàm sinh. Cụ thể là:
1. Ứng dụng vành các chuỗi lũy thừa hình thức để nghiên cứu dãy số.
2. Ứng dụng vành các chuỗi lũy thừa hình thức để giải các bài toán đếm.
3. Ứng dụng vành các chuỗi lũy thừa hình thức trong việc chứng minh các
công thức tổ hợp.
4. Ứng dụng vành các chuỗi lũy thừa hình thức để giải một số bài toán bậc
phổ thông.
Với những ứng dụng này có thể giúp các giáo viên bồi dưỡng học sinh giỏi
ở trường phổ thông hoặc Đại học, cao đẳng có thể tìm được đáp số của các bài
toán khó về dãy số, các bài toán tổ hợp…một cách hiệu quả.
33
TÀI LIỆU THAM KHẢO
[1] Bộ Giáo dục và Đào tạo. Sách giáo khoa Giải tích 11, nâng cao. Nxb Giáo
dục Việt Nam.
[2] Bộ Giáo dục và Đào tạo. Sách giáo khoa Giải tích 11, cơ bản. Nxb Giáo
dục Việt Nam.
[3] Võ Giang Giai, Nguyễn Ngọc Thu. Một số bài toán về dãy số. Nxb Đại
học Quốc gia Hà Nội.
[4] Herbert S. Wilf. (1992). Philadelphia, PA, Generatingfunctionology.
May 21.
[5] The American Mathematical Monthly. Formal Power Series. vol. 76, No. 8
(Oct., 1969), pp. 871 – 889.
