Header Page 1 of 126.

Lời cảm ơn
Tôi xin bày tỏ lòng biết ơn sâu sắc đến GS.TSKH Hà Huy Khoái, đã
định hướng chọn đề tài và nhiệt tình hướng dẫn để tôi có thể hoàn thành
luận văn này.

Tôi cũng xin bày tỏ lòng biết ơn chân thành tới Phòng Sau đại học, các
thầy cô giáo giảng dạy chuyên ngành Phương pháp Toán sơ cấp, trường
Đại học Thăng Long đã giúp đỡ tôi trong suốt quá trình học tập tại trường.

Nhân dịp này tôi cũng xin gửi lời cảm ơn đến gia đình, bạn bè đã cổ vũ,
động viên để tôi hoàn thành luận văn này.
Hà Nội, tháng 4 năm 2016
Tác giả

Lê Thị Thọ

Footer Page 1 of 126.


Header Page 2 of 126.

Lời cam đoan
Tôi xin cam đoan, dưới sự chỉ bảo và hướng dẫn của GS.TSKH Hà Huy
Khoái, luận văn chuyên ngành Toán Đại số với đề tài:”Phương pháp quy
nạp trong các bài toán tổ hợp” được hoàn thành bởi sự nhận thức và
tìm hiểu của bản thân tác giả.

Trong quá trình nghiên cứu và thực hiện luận văn, tác giả đã kế thừa
những kết quả của các nhà khoa học với sự trân trọng và biết ơn.

1.2

So sánh và đánh giá . . . . . . . . . . . . . . . . . . . . . . 12

1.3

Chứng minh các đồng nhất thức và bất đẳng thức nhờ quy
nạp toán học . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.4

Bài toán của Fibonacci . . . . . . . . . . . . . . . . . . . . 16

1.5

Một số đồng nhất thức . . . . . . . . . . . . . . . . . . . . 19

2 QUY NẠP VÀ CÁC BÀI TOÁN TỔ HỢP

22

2.1

Số tập con . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2

Dãy số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3


2.6.4

Giải một số bài toán tổ hợp . . . . . . . . . . . . . . 41

Hệ số nhị thức và tam giác Pascal . . . . . . . . . . . . . . 48
2

Footer Page 3 of 126.


Header Page 4 of 126.

2.7.1

Tam giác Pascal . . . . . . . . . . . . . . . . . . . . 50

2.7.2

Công thức trong tam giác Pascal . . . . . . . . . . . 51

Kết luận

55

Tài liệu tham khảo

56

3

4

Footer Page 5 of 126.


Header Page 6 of 126.

tổng quát.
Vai trò của kết luận quy nạp là rất lớn. Nó cho những xuất phát điểm
để từ đó, bằng con đường phân tích người ta rút ra những lý thuyết sâu
hơn.
Vì những lý do trên tôi chọn đề tài: Phương pháp quy nạp trong
các bài toán tổ hợp. Khi nghiên cứu và thực hiện đề tài bản thân tôi sẽ
hiểu rõ hơn về quy nạp toán học và các bài toán tổ hợp. Từ đó có thêm
kiến thức để hướng dẫn học sinh học tập tốt môn học này.
Chúng tôi không có ý định sưu tầm những bài toán khó, mà gần như
ngược lại, phân tích ý tưởng quy nạp dựa trên những bài toán tương đối
dễ. Mục tiêu là giúp học sinh hiểu được rằng, quy nạp là phương pháp
phát hiện ra các mệnh đề toán học chưa biết, chứ không đơn thuần như
quan điểm rộng rãi hiện nay là quy nạp chỉ dùng để chứng minh mệnh đề
cho trước, bằng cách chứng minh "đã đúng đến k thì đúng đến k + 1”.

2. Mục đích nghiên cứu
Đề tài nhằm nghiên cứu phương pháp chứng minh quy nạp toán học và
các bài toán tổ hợp.

3. Nhiệm vụ nghiên cứu
Nghiên cứu các bài toán tổ hợp trong chương trình THPT và một số bài
toán nâng cao.


1.1

Phương pháp quy nạp toán học

Bây giờ ta tìm hiểu các công cụ quan trọng nhất trong toán rời rạc. Ta
bắt đầu bằng câu hỏi:
Cộng n số lẻ đầu tiên lại ta thu được số bằng bao nhiêu?
Có lẽ cách tốt nhất là ta thử tìm câu trả lời bằng thực nghiệm. Thử với
các giá trị n nhỏ, thì thứ ta tìm được là:

1=1
1+3=4
1+3+5=9
1 + 3 + 5 + 7 = 16
1 + 3 + 5 + 7 + 9 = 25
1 + 3 + 5 + 7 + 9 + 11 = 36
1 + 3 + 5 + 7 + 9 + 11 + 13 = 49

7

Footer Page 8 of 126.

Thang Long University Library


Header Page 9 of 126.

1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64
1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 = 81
1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 = 100


Footer Page 9 of 126.


Header Page 10 of 126.

Điều đó là đủ để kết luận rằng khẳng đúng với mọi n. Ta đã thấy nó
đúng với n = 1; nên theo trên, nó cũng đúng với n = 2 (ta đã thấy điều
này bằng tích toán trực tiếp, nhưng việc đó không thực sự cần thiết: nó
được suy ra trừ trường hợp n = 1). Theo cách tương tự, tính đúng đắn
của khẳng định với n = 2 kéo theo nó cũng đúng với n = 3, và đến lượt
nó lại kéo theo tính đúng đắn với n = 4, v.v.. Nếu ta lặp lại điều này đủ
nhiều, ta thu được tính đúng đắn với giá trị n bất kỳ. Do đó khẳng định
trên là đúng với mọi giá trị n.
Kỹ thuật chứng minh này được gọi là quy nạp (hoặc đôi khi gọi là quy
nạp toán học, để phân biệt với khái niệm trong triết học). Nó được tóm
tắt lại như sau.
Giả sử rằng ta muốn chứng minh một tính chất của các số nguyên dương.
Giả sử thêm ta có thể chứng minh hai điều:
(a) số 1 có tính chất đó, và
(b) bất cứ khi nào n − 1 có tính chất đó thì n cũng có tính chất đó
(n > 1).
Nguyên lý quy nạp nói rằng nếu (a) và (b) đúng, thì mọi số tự nhiên có
tính chất như vậy.
Điều này chính là những gì ta làm ở trên. Ta đã chỉ ra “tổng” của số lẻ
đầu tiên là 12 , và tiếp theo ta chỉ ra nếu tổng của n − 1 số lẻ đầu tiên là

(n − 1)2 , thì tổng của n số lẻ đầu tiên là n2 , với mọi số nguyên n > 1.
Do đó, theo Nguyên lý quy nạp ta có thể kết luận rằng với mọi số nguyên
dương n, tổng của n số lẻ đầu tiên là n2 .

khẳng định là sai với n = 1.
Bài toán 1.1.1. Chứng minh bằng quy nạp và không bằng quy nạp rằng

n(n + 1) luôn là số chẵn với mọi số nguyên dương n.
Bài toán 1.1.2. Chứng minh bằng quy nạp rằng tổng của n số nguyên
dương đầu tiên là n(n + 1)/2.
Bài toán 1.1.3. Nhận xét rằng n(n + 1)/2 là số cái bắt tay giữa n + 1
người. Giả sử rằng tất cả mọi người chỉ đếm số bắt tay với người nhiều
tuổi hơn mình (khá là lố bịch, phải không?). Ai là người có số bắt tay
nhiều nhất? Có bao nhiêu người có 6 cái bắt tay? (Chúng ta giả sử rằng
không có hai người nào bằng tuổi).
10

Footer Page 11 of 126.


Header Page 12 of 126.

Dựa vào kết quả của bài tập 1.1.2 chứng minh các kết quả của bạn.
Chúng ta thường dùng chữ “v.v.”: để miêu tả một số lập luận mà phải
lặp n lần mới thu được kết quả ta cần, nhưng sau khi lập luận một hoặc
hai lần, ta nói “v.v.” thay vì tiếp lục lặp lại. Không có gì là sai ở đây, nếu
lập luận đủ đơn giản thì ta có một cách trực quan thấy những chỗ mà
phép lặp bắt đầu. Nhưng sẽ tốt hơn nếu có thể dùng một số công cụ thay
vì “v.v.” trong trường hợp mà kết quả của phép lặp không quá rõ ràng.
Cách chính xác để làm điều này là dùng phép quy nạp. Giả sử ta chứng
minh công thức tính số tập con của một tập n phần tử (đáp án là 2n ).
Nguyên lý quy nạp cho ta biết ta phải kiểm tra khẳng định đúng với

n = 0. Việc này là rõ ràng. Tiếp theo, ta giả sử rằng n > 0 và khẳng định

Thật tốt nếu có công thức tính các số nhất định (ví dụ, có n! hoán vị
của n phần tử), nhưng quan trọng hơn là phải có một ý tưởng sơ bộ về độ
lớn những con số này. Ví dụ, số 100! có bao nhiêu chữ số?
Ta bắt đầu với các câu hỏi đơn giản hơn. Số nào lớn hơn, n hay
Với n = 2, 3, 4 giá trị

n
2

n
2

?

là 1, 3, 6, nên nó nhỏ hơn n với n = 2, bằng

nhau với n = 3 và lớn hơn với n = 4. Thật ra, n =

n
1



nếu n ≥ 3.

(b) Dùng (a) để chứng minh 2n /n2 lớn tùy ý khi n đủ lớn.
Bây giờ ta giải quyết vấn đề ước lượng số 100!, hay tổng quát hơn,

n! = 1 · 2 · · · n. Nhân tử 1 đầu tiên không ảnh hưởng gì, nhưng tất cả các
nhân tử khác đều ít nhất là 2, nên n! ≥ 2n−1 . Tương tự n! ≤ nn−1 , vì (bỏ
qua nhân tử 1) n! là tích của n − 1 nhân tử, mỗi trong số đó đều nhỏ hơn
12

Footer Page 13 of 126.


Header Page 14 of 126.

n. (Vì tất cả trừ một trong số chúng nhỏ hơn n, nên tích nhỏ hơn nhiều.)
Do vậy ta biết rằng

2n−1 ≤ n! ≤ nn−1 .

(1.3)

Các cận này cách nhau khá xa, với n = 10, cận dưới là 29 = 512, trong
khi cận trên là 109 (một tỉ).
Dưới đây là một câu hỏi vẫn chưa được trả lời bằng các ước lượng trong
(1.3). Số nào lớn hơn, n! hay 2n ? Nói cách khác, tập với n phần tử có số
phép hoán vị nhiều hơn số tập con hay không? Với các giá trị n nhỏ, số tập
con thắng nhiều hơn: 21 = 2 > 1! = 1, 22 = 4 > 2! = 2, 23 = 8 > 3! = 6.
Nhưng từ đây thì lại đổi chiều: 24 = 16 < 4! = 24, 25 = 32 < 5! = 120.
Dễ thấy rằng khi n tăng, n! tăng nhanh hơn 2n : Nếu ta đi từ n tới n + 1,


Cả hai số vô tỉ siêu việt e và π xuất hiện trong cùng một công thức!

13

Footer Page 14 of 126.

Thang Long University Library


Header Page 15 of 126.

Ta quay trở lại câu hỏi: Số 100! có bao nhiêu chữ số? Theo công thức
Stirling ta biết rằng

100! ≈ (100/e)100 ·

√

200π.

Số chữ số của số này là logarit cơ số 10 của nó được làm tròn. Do đó ta có

lg(100!) ≈ 100 lg(100/e) + 1 + lg

√

2π = 157.969...

Nên số chữ số trong số 100! là vào khoảng 158 (thật ra đây là giá trị đúng).

−
=
+
+ ... +
2 3 4
2n − 1 2n n + 1 n + 2
2n

Chứng minh.
14

Footer Page 15 of 126.

(1.3.1)


Header Page 16 of 126.

Khi n = 1, đồng nhất thức có dạng 1 −

1
2

=

1
2

đúng.


1
1− +...− +
−
=
+...+ +
+
, (1.3.1.2)
2
2k 2k + 1 2(k + 1) k + 2
2k 2k + 1 2k + 2
Trừ từng vế các đồng nhất thức này cho nhau ta được

1
1
1
1
1
−
=
+
−
,
2k + 1 2(k + 1) 2k + 1 2k + 2 k + 1
hay là

2
1
=
.
2(k + 1) k + 1

Do kx2 ≥ 0 nên từ đó suy ra

(1 + x)k+1 ≥ 1 + (k + 1)x .
Theo quy nạp toán học ta kết luận được rằng bất đẳng thức (1.3.2) đúng
với mọi số tực nhiên n

1.4

Bài toán của Fibonacci

Vào thế kỉ XIII, nhà toán học người Italia Leonardo Fibonacci nghiên
cứu câu hỏi sau:
Một người nông dân nuôi các con thỏ. Sau hai tháng tuổi, mỗi
con thỏ sinh ra một thỏ con, và sau đó cứ mỗi tháng lại sinh một
con. Giả sử các con thỏ không bao giờ chết, và ta xem là không
có thỏ đực. Hỏi người nông dân có bao nhiêu con thỏ sau n tháng
nếu ông ta bắt đầu bằng một con thỏ mới sinh?
Ta dễ dàng hình dung ra đáp án với các giá trị n nhỏ. Người nông dân
có một con thỏ trong tháng đầu tiên và một con thỏ trong tháng thứ hai,
vì con thỏ cần đủ hai tháng tuổi trước khi nó biết đẻ. Người nông dân có
2 thỏ trong thang thứ ba, và ba con thỏ trong tháng thứ tư, vì con thỏ
đầu tiên sinh ra một con sau tháng thứ hai. Sau 4 tháng, con thỏ thứ hai
cũng sinh một con thỏ mới, nên hai con thỏ con được thêm vào. Điều này
có nghĩa người nông dân có 5 con thỏ sau tháng thứ 5.
Dễ dàng suy ra quy tắc tăng trưởng đàn thỏ với số tháng bất kỳ, nếu ta
chú ý rằng số thỏ mới sinh trong mỗi tháng chính bằng số thỏ ít nhất hai
tháng tuổi, tức là, những con đã có ở tháng trước. Nói cách khác, để tính
số thỏ trong tháng tiếp theo, ta phải cộng thêm số thỏ trong tháng trước
16


Trước khi thảo luận thêm về các số này, ta xét một bài toán đếm khác:
Một cầu thang có n bậc. Bạn đi lên theo từng bậc một hoặc 2
bậc. Hỏi có bao nhiêu cách để bạn đi lên?
Với n = 1, chỉ có một cách. Với n = 2, bạn có 2 lựa chọn: đi hai lần
bước đơn hoặc đi một lần bước kép. Với n = 3, ta có ba cách: ba lần bước
17

Footer Page 18 of 126.

Thang Long University Library


Header Page 19 of 126.

đơn, hoặc một bước đơn rồi một bước kép, hoặc một bước kép rồi một
bước đơn.
Ta dừng lại và thử đoán đáp án tổng quát! Nếu bạn dự đoán số cách đi
lên với n bậc là n cách, bạn đã sai. Trường hợp tiếp theo, n = 4, có 5 cách
(1 + 1 + 1 + 1, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, 2 + 2).
Nên thay vì dự đoán, ta thử cách sau. Ký hiệu Jn là đáp án. Ta thử hình
dung Jn+1 bằng bao nhiêu, giả sử ta biết giá trị của Jk với 1 ≤ k ≤ n.
Nếu ta bắt đầu bằng một bước đơn, ta có Jn cách để đi tiếp n bước còn
lại. Nếu bắt đầu bằng một bước kép, ta có Jn−1 cách đi lên n − 1 bước còn
lại. Nên tất cả có

Jn+1 = Jn + Jn−1 .
Câu hỏi này cũng tương tự như câu hỏi ta đã dùng để tính dãy số Fibonacci

Fn . Điều này có phải có nghĩa là Fn = Jn ? Tất nhiên là không rồi, như ta
thấy ở các giá trị ban đầu: Ví dụ, F3 = 2 nhưng J3 = 3. Tuy nhiên, dễ

0 + 1 + 1 + 2 + 3 + 5 = 12,
0 + 1 + 1 + 2 + 3 + 5 + 8 = 20,
0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33.
Bắt đầu bằng các số này, không khó để nhận ra rằng bằng cách cộng thêm
1 vào vế phải ta thu được dãy số Fibonacci, thật ra, ta được số Fibonacci
sau hai bước của số hạng cuối cùng. Ta có

F0 + F1 + F2 + · · · + Fn = Fn+2 − 1.
Tất nhiên, tại thời điểm này thì đây mới chỉ là một khẳng định, một phát
biểu toán học chưa được chứng minh mà ta tin là đúng. Để chứng minh
nó, ta dùng phép quy nạp theo n (vì dãy Fibonacci được xác định bằng
phép truy hồi, phép quy nạp là tự nhiên, và thường là phương pháp chứng
minh duy nhất).
Ta đã kiểm tra công thức đúng với n = 0 và 1. Giả sử rằng công thức
đúng với n − 1 số Fibonacci đầu tiên. Xét tổng của n số Fibonacci đầu
tiên:

F0 + F1 + . . . + Fn = (F0 + F1 + . . . + Fn−1 ) + Fn = (Fn+1 − 1) + Fn ,
19

Footer Page 20 of 126.

Thang Long University Library


Header Page 21 of 126.

theo giả thiết quy nạp. Nhưng bây giờ ta có thể dùng phương trình truy
hồi của dãy Fibonacci để thu được


20

Footer Page 21 of 126.


Header Page 22 of 126.

chứng minh (1.6), ta dùng công thức truy hồi cơ bản (1.4) hai lần:

Fn+1 Fn + Fn Fn−1 = (Fn + Fn−1 )Fn + (Fn−1 + Fn−2 )Fn−1
2
= (Fn2 + Fn−1
) + (Fn Fn−1 + Fn−1 Fn−2 )

= F2n−1 + F2n−2 = F2n .
(áp dụng (1.5) cho số hạng đầu tiên và phép quy nạp cho số hạng thứ hai).
Chứng minh của (1.5) là tương tự:
2
2
Fn2 + Fn−1
= (Fn−1 + Fn−2 )2 + Fn−1
2
2
2
= (Fn−1
+ Fn−2
) + 2Fn−1 Fn−2 + Fn−1
2
2
= (Fn−1

Header Page 23 of 126.

Chương 2
QUY NẠP VÀ CÁC BÀI TOÁN
TỔ HỢP
2.1

Số tập con

Ta quay lại với bài toán: Có tất cả bao nhiêu tập con của một tập có n
phần tử?
Ta bắt đầu bằng cách thử với các số nhỏ. Các phần tử của tập là gì thì
cũng không có gì khác biệt, ta gọi chúng là a, b, c, v.v. Tập rỗng chỉ có một
tập con (cụ thể là chính nó). Một tập có một phần tử, ví dụ {a}, có hai
tập con: tập {a} và tập rỗng Ø. Một tập có hai phần tử, ví dụ {a, b} có
bốn tập con: Ø, {a}, {b}, {a, b}. Để liệt kê các tập con của tập có 3 phần
tử {a, b, c} ta phải tính nhiều hơn:

Ø, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c}.

(2.1)

Ta có thể lập thành bảng
Số phần tử trong tập

0

1

2

có thể chọn về a1 và a2 là 2 · 2 = 4. Bây giờ không quan trọng ta đã chọn

a1 và a2 , ta phải quyết định chọn a3 , và một lần nữa ta có hai cách. Mỗi
một trong hai cách này có thể kết hợp với 4 lựa chọn ta có thể đưa ra về

a1 và a2 , tạo ra 4 · 2 = 8 khả năng để quyết định về a1 , a2 và a3 .
Ta có thể tiếp tục như vậy: Không quan trọng về k phần tử đầu tiên,
ta có hai lựa chọn về số tiếp theo, và do vậy số khả năng nhân đôi mỗi lần
ta lấy một phần tử mới. Để quyết định về tất cả n phần tử của tập hợp,
ta có 2n khả năng.
Do đó ta suy ra định lý sau.
Định lý 2.1.1. Một tập với n phần tử có 2n tập con.

2.2

Dãy số

Từ việc "mã hóa" các tập con là các chuỗi 0 và 1, chúng ta muốn xác
định số lượng các chuỗi có độ dài n được xây dựng từ một tập các ký hiệu
khác nhau, ví dụ, a, b và c. Các lập luận mà chúng ta đưa ra cho trường
hợp của chuỗi 0 và 1 có thể được chuyển sang trường hợp này mà không
có bất kỳ sự thay đổi bản chất. Chúng ta có thể thấy rằng với phần tử
đầu tiên của chuỗi, chúng ta có thể chọn bất kỳ phần tử từ a, b và c, tức
là, chúng ta có 3 lựa chọn. Không quan trọng chúng ta chọn cái gì, có 3
lựa chọn cho phần tử thứ hai của chuỗi, do đó, số cách để chọn hai phần
tử đầu tiên là 32 = 9. Tiến hành theo cách thức tương tự, chúng tôi nhận
23

Footer Page 24 of 126.


Ta có thể tổng quát hóa định lý 2.2.1 (chứng minh bao gồm lặp lại các
lập luận như trên).
Định lý 2.2.2. Giả sử ta muốn lập một chuỗi có độ dài n bằng một tập bất
kỳ có k1 ký hiệu làm phần tử đầu của chuỗi, một tập bất kỳ có k2 ký hiệu
24

Footer Page 25 of 126.