Bài giảng Toán rời rạc - Chương I: Phương pháp đếm

 1
1 2
2 4 0;
4; 4.
n n nx x x
x x
+ +− + =⎧⎨ = =⎩
25/03/2010 78
3. Hệ thức đệ quy
Ví dụ 1:
Hệ thức đệ quy tuyến tính thuần nhất
( )1 22 3 0 1n n nx x x− −− + =
Phương trình đặc trưng của (1) là:
2λ2 - 3λ + 1 = 0 (*)
có hai nghiệm thực là λ1 = 1 và λ2 = 1/2.
Do đó nghiệm tổng quát của (1) là:
25/03/2010 79
1
2
n
n A Bx = +
⎛ ⎞⎜ ⎟⎝ ⎠
3. Hệ thức đệ quy
Ví dụ 2:
Hệ thức đệ quy tuyến tính thuần nhất
( )1 1
0 1
4 12 9 0
 2
2; 4.
n n nx x x
x x
+ −− + =⎧⎨ = =⎩
Phương trình đặc trưng của (2) là:
4λ2 - 12λ + 9 = 0
có nghiệm thực kép là λ0 = 3/2. Do đó nghiệm
tổng quát của (2) là:
25/03/2010 80
( )
3
2
n
n A nBx = +
⎛ ⎞⎜ ⎟⎝ ⎠
Từ điều kiện ban đầu x0 = 2; x1 = 4 ta suy ra:
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính thuần nhất
2
3 ( ) 4
2
A
A B
=⎧⎪⎨ + =⎪⎩
Suy ra A = 2 và 3
2
B =
Vậy nghiệm của (2) là:
25/03/2010 81
1
(3 )
3
2
n
n nx
−
= + ⎛ ⎞⎜ ⎟⎝ ⎠
25/03/2010
21
⎧
3. Hệ thức đệ quy
Ví dụ 3:
Hệ thức đệ quy tuyến tính thuần nhất
( )2 1
1 2
2 4 0
 3
4; 4
n n nx x x
x x
+ +− + =⎨ = =⎩
Phương trình đặc trưng của (3) là:
λ2 - 2λ + 4 = 0 (*)
có hai nghiệm phức liên hợp là 1 3iλ = ±
Ta viết hai nghiệm trên dưới dạng lượng giác: 
2(cos sin )
3 3
iπ πλ = ±
25/03/2010 82
Do đó nghiệm tổng quát của (3) là 
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính thuần nhất
1 22 ( cos sin )3 3
n
n
n nx C Cπ π= +
Từ điều kiện ban đầu x1 = 4; x2 = 4 
ta suy ra:
1 32( ) 4C C
⎧ + =⎪⎪ 1 2
1 2
2 2
1 34( ) 4
2 2
C C
⎨⎪ − + =⎪⎩
Suy ra: 1 21, 3C C= =
Vậy nghiệm của (3) là : 2 (cos 3sin )
3 3
n
n
n nx π π= +
25/03/2010 83
Xét hệ thức đệ quy tuyến tính không thuần nhất
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
Hệ thức đệ quy tuyến tính thuần nhất tương ứng
là:
xn = a1xn-1 + + akxn-k + fn (1)
x = a x + + akx k (2)
25/03/2010 84
n 1 n-1  n-
Phương trình đặc trưng của (2) là: 
λk - a1λk-1 - - ak = 0 (*)
ổ
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
Nghiệm tổng quát của (1) =
Nghiệm t ng quát 
của (2)
Một nghiệm riêng 
của (1)
+
25/03/2010 85
25/03/2010
22
Cách tìm một nghiệm riêng của (1) khi vế phải
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
fn của (1) có dạng đặc biệt như sau:
Dạng 1: fn = βnPr(n), trong đó Pr(n) là một đa thức
bậc r theo n; β là một hằng số
Dạng 2: fn = Pm(n)cosnϕ + Ql(n)sinnϕ, trong đó
ầPm(n), Ql(n) l n lượt là các đa thức bậc m, l theo n;ϕ là hằng số (ϕ ≠ kπ).
Dạng 3: fn = fn1 + fn2 ++ fns, trong đó các fn1,
fn2,, fns thuộc 2 dạng đã xét ở trên.
25/03/2010 86
Dạng 1: f = βnP (n)
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
Khi đó ta xét λ0 = β. Có 3 trường hợp nhỏ:
Trường hợp 1: β không là nghiệm của phương trình
đặc trưng
n r
Trường hợp 2: β là nghiệm đơn của phương trình
đặc trưng
Trường hợp 3: β là nghiệm kép của phương trình
đặc trưng
25/03/2010 87
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
Dạng 1: f = βnP (n)
Nếu λ0 = β không là nghiệm của phương trình
đặc trưng (*) thì (1) có một nghiệm riêng
dạng:
Trường hợp 1
n r
xn = βnQr(n)
25/03/2010 88
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
Dạng 1: f = βnP (n)
Nếu λ0 = β là nghiệm đơn của phương trình
đặc trưng (*) thì (1) có một nghiệm riêng
dạng:
Trường hợp 2
n r
xn = nβnQr(n)
25/03/2010 89
25/03/2010
23
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
Dạng 1: f = βnP (n)
Nếu λ0 = β là nghiệm kép của phương trình
đặc trưng (*) thì (1) có một nghiệm riêng
dạng:
n r
Trường hợp 3
xn = n2βnQr(n)
25/03/2010 90
Chú ý:
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
Qr(n) = Arnr + Ar-1nr-1 ++ A0 là đa thức tổng quát có
cùng bậc r với Pr(n), trong đó Ar, Ar-1,, A0 là r+1 hệ
số cần xác định.
Để xác định các hệ số trên ta cần thế xn, xn-1,, xn-k
vào (1) và cho n nhận r + 1 giá trị nguyên nào đó hoặc
đồng nhất các hệ số tương ứng ở hai vế để được một hệ
phương trình. Các hệ số trên là nghiệm của hệ phương
trình này
25/03/2010 91
Dạng 2: f = P (n)cosnϕ + Ql(n)sinnϕ
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
n m
Khi đó ta xét λ0 = cosϕ ± isinϕ. Có 2 trường
hợp nhỏ:
Trường hợp 1: λ0 = cosϕ ± isinϕ không là nghiệm
của phương trình đặc trưng.
Trường hợp 2: λ0 = cosϕ ± isinϕ là nghiệm của
phương trình đặc trưng.
25/03/2010 92
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
Dạng 2: f = P (n)cosnϕ + Ql(n)sinnϕ
Nếu λ0 = cosϕ ± isinϕ không là nghiệm của
phương trình đặc trưng (*) thì (1) có một
nghiệm riêng dạng:
Trường hợp 1
n m
xn = Rk(n)cosnϕ + Sk(n)sinnϕ
25/03/2010 93
25/03/2010
24
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
Dạng 2: f = P (n)cosnϕ + Ql(n)sinnϕ
Nếu λ0 = cosϕ ± isinϕ là nghiệm của phương
trình đặc trưng (*) thì (1) có một nghiệm riêng
dạng:
n m
Trường hợp 2
xn = n(Rk(n)cosnϕ + Sk(n)sinnϕ)
25/03/2010 94
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
Chú ý:
Rk(n), Sk(n) là các đa thức tổng quát theo n có
bậc k = max{m,l} với 2k+2 hệ số cần xác định:
Rk(n) = Aknk + Ak-1nk-1 ++ A0
Sk(n) = Bknk + Bk-1nk-1 ++ B0 
25/03/2010 95
Dạng 3: f = f 1 + f 2 + + f
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
n n n  ns
Bằng cách như trên ta tìm được nghiệm riêng
xni (1≤ i ≤ s) của hệ thức đệ quy:
a0xn + a1xn 1 + + akxn k = fni - - 
Khi đó xn = xn1 + xn2++ xns là một nghiệm
riêng của (1).
25/03/2010 96
2 3 4 1x x x n+ +Ví dụ (2)
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
1 2n n n− −− =
Hệ thức đệ quy tuyến tính thuần nhất là:
1 22 3 0n n nx x x− −− + =
Phương trình đặc trưng của (2) là:
2λ2 - 3λ + 1 = 0 (*)
có hai nghiệm thực là λ1 = 1 và λ2 = 1/2
25/03/2010 97
25/03/2010
25
3. Hệ thức đệ quy
Do đó nghiệm tổng quát của (2) là:
1
n⎛ ⎞
Hệ thức đệ quy tuyến tính không thuần nhất
Bây giờ ta tìm một nghiệm riêng của (1).
Vế phải của (1) là fn = 4n+1 có dạng Pr(n) là
đ hứ bậ 1 h
1 2 2nx C C
= + ⎜ ⎟⎝ ⎠
a t c c r = t eo n.
Vì λ0 = 1 là nghiệm đơn của phương trình đặc
trưng (*) nên (1) có một nghiệm riêng dạng:
xn = n(an + b) (4)25/03/2010 98
Thế (4) vào (1) ta được:
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
2n(an+b) -3(n-1)[a(n-1)+b] + (n-2)[a(n-2) + b] = 4n + 1
Cho n lần lượt nhận hai giá trị n = 0; n = 1 ta
được hệ:
1;
3 5.
a b
a b
⎧⎨⎩
+ =
+ =
25/03/2010 99
Giải hệ trên ta được a = 2; b = -1 Thế vào (4) ta
3. Hệ thức đệ quy
Hệ thức đệ quy tuyến tính không thuần nhất
.
tìm được một nghiệm riêng của (1) là:
xn = n(2n – 1) (5)
Từ (3) và (5) ta suy ra nghiệm tổng quát của (1)
là:
25/03/2010 100
1 2 (2 1)
1
2
n
n n nx C C= + + −
⎛ ⎞⎜ ⎟⎝ ⎠
4. Nguyên lý bù trừ
Trong một số bài toán đếm phức tạp hơn, nếu
không có giả thiết gì về sự rời nhau giữa hai tập
A và B thì |A׫B| = |A| + |B| – |A∩B|.
BA A∩B
25/03/2010 101
25/03/2010
26
4. Nguyên lý bù trừ
Ví dụ
Lớp toán học rời rạc có 25 sinh viên giỏi tin học,
13 sinh viên giỏi toán và 8 sinh viên giỏi cả toán
và tin học. Hỏi lớp có bao nhiêu sinh viên nếu
mỗi sinh viên hoặc giỏi toán hoặc học giỏi tin
học hoặc giỏi cả hai môn?
25/03/2010 102
4. Nguyên lý bù trừ
Gọi A tập là tập các sinh viên giỏi Tin học, B là
tập các sinh viên giỏi toán. Khi đó A∩B là tập
sinh viên giỏi cả toán học và tin học. Vì mỗi sinh
viên trong lớp hoặc giỏi toán, hoặc giỏi tin học
hoặc giỏi cả hai nên ta có tổng số sinh viên trong
lớp là |A׫B|. Do vậy ta có:
25/03/2010 103
|A׫B| = |A| + |B| – |A∩B| = 25 + 13 – 8 = 30.
4. Nguyên lý bù trừ
Giả sử A1, A2,.., An là những tập hữu hạn. Khi
đó:
1 2
1
1 2
1 1 1
...
... ...( 1)
n
n
i i j i j k n
i n i j n i j k n
A A A
A A A A A A A A A
+
≤ ≤ ≤ < ≤ ≤ < < ≤
∪ ∪ ∪
= − ∩ + ∩ ∩ − + ∩ ∩ ∩−∑ ∑ ∑
25/03/2010 104
5. Nguyên lý quy nạp
Mệnh đề “∀n∈N, p(n)” là hệ quả logic của
“p(0)∧[∀n∈N, p(n)→p(n+1)]”
ểNguyên lý quy nạp được cụ th hóa thành phương pháp chứng
minh quy nạp như sau: Giả sử ta phải chứng minh mệnh
đề∀n∈N, p(n), khi đó ta sẽ thực hiện các bước sau:
Bước 1. Kiểm tra p(0) là mệnh đề đúng (trong thực tế, ta
có thể bắt đầu bằng giá trị nhỏ nhất có thể được của n không
25/03/2010 105
,
nhất thiết phải bắt đầu từ 0)
Bước 2. Với n bất kỳ, giả sử p(n) là mệnh đề đúng, ta sẽ
phải chứng minh p(n+1) cũng là mệnh đề đúng.
25/03/2010
27
5. Nguyên lý quy nạp
Ví dụ
Chứng minh ( 1 ), 0 1 . . .
2
n nn N n +∀ ∈ + + + =
Ta xét vị từ p(n) =
Ta có:
p(0)= , đây rõ ràng là một mệnh đề
( 1 )" 0 1 . . . "
2
n nn ++ + + =
0 . 1" 0 "
2
=
25/03/2010 106
đúng.
5. Nguyên lý quy nạp
Xét n là số tự nhiên bất kỳ, giả sử p(n) là mệnh đề đúng, nghĩa là
ta có:
( 1 )+
Ta sẽ chứng minh p(n+1) cũng đúng. Thật vậy, ta có:
0 1 . . .
2
n nn+ + + =
( 1 )0 1 . . . ( 1 ) ( 1 )
2
( 1 ) [ ( 1 ) 1 ]
n nn n n
n n
++ + + + + = + +
+ + +
25/03/2010 107
suy ra p(n+1) là mệnh đề đúng.
Theo nguyên lý quy nạp ta có điều phải chứng minh.
2
=
6. Phương pháp phản chứng
Một trong những cách giải bài toán tồn tại là
dùng lập luận phản chứng: giả thiết điều chứng
minh là sai từ đó dẫn đến mâu thuẫn, .
Ví dụ
Cho 7 đoạn thẳng có độ dài lớn hơn 10 và nhỏ
hơn 100 Chứng minh rằng ta luôn luôn tìm
25/03/2010 108
.
được 3 đoạn để có thể ghép lại thành một tam
giác.
6. Phương pháp phản chứng
Điều kiện cần và đủ để 3 đoạn là cạnh của một tam giác là
tổng của hai cạnh phải lớn hơn một cạnh. Ta sắp các đoạn
thẳng theo thứ tự tăng dần của độ dài a1, a2,..., a7 và chứng
i h ằ dã đã ế l ô tì đ 3 đ à tổ ủ h im n r ng y x p u n m ược oạn m ng c a a
đoạn đầu lớn hơn đoạn cuối. Để chứng minh, ta giả sử
không tìm được ba đoạn nào mà tổng của hai đoạn nhỏ hơn
một đoạn, nghĩa là các bất đẳng thức sau đồng thời xảy ra:
a1 + a2≤ a3֜ a3≥ 20 (vì a1, a2≥ 10 )
a2 + a3≤ a4֜ a4≥ 30 (vì a2≥ 10 a3≥ 20)
25/03/2010 109
,
a3 + a4≤ a5֜ a5≥ 50 (vì a3≥ 20, a4≥ 30 )
a4 + a5≤ a6֜ a6≥ 80 (vì a4≥ 30, a5≥ 50)
a5 + a6≤ a7֜ a7≥ 130 (vì a5≥ 50, a6≥ 80)
֜Mâu thuẫn (bài toán được giải quyết).