Toán học - Chương I: Phương pháp đếm

ó nghiệm tổng quát là: 0( ) n nx A nB λ= + 25/03/2010 76 c) Nếu (*) có hai nghiệm phức liên hợp được ế 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính thuần nhất vi t dưới dạng lượng giác : (cos sin )r iλ ϕ ϕ= ± thì (2) có nghiệm tổng quát là: ( cos sin )nnx r A n B nϕ ϕ= + 25/03/2010 77 25/03/2010 20 Giải các hệ thức đệ quy sau: 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính thuần nhất Ví dụ 1 Ví dụ 2 1 22 3 0n n nx x x− −− + = 1 14 12 9 0; 2; 4 n n nx x x x x + −− + =⎧⎨ = =⎩ Ví dụ 3 0 1 . 2 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).