Toán Rời Rạc- Hệ Thức đệ Quy - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (31 trang)

Trang chủ

Giáo án - Bài giảng

Toán học

Toán rời rạc- hệ thức đệ quy

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (375.08 KB, 31 trang )

TOÁN RỜI RẠC - HK1 - NĂM 2016 -2017Chương 4HỆ THỨC ĐỆ QUY />FB: fb.com/trr2016Đại học Khoa Học Tự Nhiên Tp. Hồ Chí Minh− − −− Tháng 10 năm 2016 − − −−Chương 4. Hệ thức đệ quyTháng 10 - 20161/31Nội dungChương 4. HỆ THỨC ĐỆ QUY1. Giới thiệu2. Hệ thức đệ quy tuyến tính với hệ số hằng3. Nghiệm của hệ thức đệ quy tuyến tính thuần nhất4. Nghiệm của hệ thức đệ quy tuyến tính không thuầnnhấtChương 4. Hệ thức đệ quyTháng 10 - 20162/314.1. Giới thiệuVí dụ. Tháp Hà NộiCó 3 cọc A, B, C và n đĩa với đường kính đôi một khác nhau. Nguyêntắc đặt đĩa vào cọc là: mỗi đĩa chỉ được chồng lên đĩa lớn hơn nó.Ban đầu, cả n đĩa được đặt chồng lên nhau ở cọc A, hai cọc B và C đểtrống. Vấn đề đặt ra là chuyển cả n đĩa ở cọc A sang cọc C (có thể quatrung gian cọc B), mỗi lần chỉ chuyển được một đĩa. Ta gọi xn là số lầnchuyển đĩa, tìm xn ?Chương 4. Hệ thức đệ quyTháng 10 - 20163/31Giải. Với n = 1, ta có x1 = 1.Với n > 1, trước hết ta chuyển n − 1 đĩa bên trên sang cọc B qua trunggian cọc C (giữ nguyên đĩa thứ n dưới cùng ở cọc A). Số lần chuyểnn − 1 đĩa đó là xn−1 . Sau đó ta chuyển đĩa thứ n từ cọc A sang cọcC. Cuối cùng ta chuyển n − 1 đĩa từ cọc B sang cọc C (cọc A làmtrung gian). Số lần chuyển n − 1 đĩa đó lại là xn−1 .Như vậy số lần chuyển toàn bộ n đĩa từ A sang C là:xn−1 + 1 + xn−1 = 2xn−1 + 1.Nghĩa làx1 = 1xn = 2xn−1 + 1với n > 1Chương 4. Hệ thức đệ quyTháng 10 - 20164/31Ví dụ. Một cầu thang có n bậc. Mỗi bước đi gồm 1 hoặc 2 bậc. Gọi xnlà số cách đi hết cầu thang. Tìm xn ?Giải. Với n = 1, ta có x1 = 1. Với n = 2, ta có x2 = 2.Với n > 2, để khảo sát xn ta chia thành hai trường hợp loại trừ lẫnnhau:Trường hợp 1. Bước đầu tiên gồm 1 bậc. Khi đó, cầu thang cònn − 1 bậc nên số cách đi hết cầu thang là xn−1 .Trường hợp 2. Bước đầu tiên gồm 2 bậc. Khi đó, cầu thang cònn − 2 bậc nên số cách đi hết cầu thang trong là xn−2 .Theo nguyên lý cộng, số cách đi hết cầu thang là xn−1 + xn−2 . Do đóta có:xn = xn−1 + xn−2Như vậyx1 = 1, x2 = 2;xn = xn−1 + xn−2với n > 2.Chương 4. Hệ thức đệ quyTháng 10 - 20165/314.2. Hệ thức đệ quy tuyến tính với hệ số hằngĐịnh nghĩa. Một hệ thức đệ quy tuyến tính cấp k với hệ sốhằng là một hệ thức có dạng:a0 xn + a1 xn−1 + . . . + ak xn−k = fn(1)trong đóa0 = 0, a1 , . . . , ak là các hệ số thực;{fn } là một dãy số thực cho trước;{xn } là dãy ẩn nhận các giá trị thực.Trường hợp dãy fn = 0 với mọi n thì (1) trở thànha0 xn + a1 xn−1 + . . . + ak xn−k = 0(2)Ta nói (2) là một hệ thức đệ quy tuyến tính thuần nhất cấp kvới hệ số hằng .Chương 4. Hệ thức đệ quyTháng 10 - 20166/31Ví dụ.2xn − 5xn−1 + 2xn−2 = −n2 − 2n + 3 −→ tuyến tính cấp 2.xn − 3xn−1 + 2xn−3 = 20 + n2n−2 + 3n −→ tuyến tính cấp 3.2xn+2 + 5xn+1 + 2xn = (35n + 51)3n −→ tuyến tính cấp 2.xn+2 − 2xn+1 + xn = 0 −→ tuyến tính thuần nhất cấp 2.Định nghĩa. Xét hệ thức đệ quy tuyến tính cấp ka0 xn + a1 xn−1 + . . . + ak xn−k = fn(1)Mỗi dãy {xn } thỏa (1) được gọi là một nghiệm của (1).Nhận xét rằng mỗi nghiệm {xn } của (1) được hoàn toàn xác định bởik giá trị ban đầu x0 , x1 , . . . , xk−1 .Họ dãy số {xn = xn (C1 , C2 , . . . , Ck )} phụ thuộc vào k họ tham sốC1 , C2 , . . . , Ck được gọi là nghiệm tổng quát của (1) nếu mọi dãycủa họ này đều là nghiệm của (1).Chương 4. Hệ thức đệ quyTháng 10 - 20167/31Với k giá trị ban đầu y0 , y1 , . . . , yk−1 , tồn tại duy nhất các giá trị của ktham số C1 , C2 , . . . , Ck sao cho nghiệm {xn } tương ứng thỏax0 = y0 , x1 = y1 , . . . , xk−1 = yk−1(∗)Khi đó, nghiệm {xn } tương ứng được gọi nghiệm riêng ứng với điềukiện ban đầu (∗).Giải một hệ thức đệ quy là đi tìm nghiệm tổng quát của nó; nhưngnếu hệ thức đệ quy có kèm theo điều kiện ban đầu, ta phải tìmnghiệm riêng thỏa điều kiện ban đầu đó.Ví dụ.3 n2xn − 3xn−1 = 0 có nghiêm tổng quát là xn = C.2 xn − 5xn−1 + 6xn−2 = 0;x0 = 4;có nghiệm riêng là xn = 3 · 2n + 3n .x1 = 9.Lưu ý. Trong phạm vi của chương trình ta chỉ xét các hệ thức đệ quytuyến tính (cấp 1 và 2) với hệ số hằng.Chương 4. Hệ thức đệ quyTháng 10 - 20168/314.3. Nghiệm của HTĐQTT thuần nhấtXét hệ thức đệ quy tuyến tính thuần nhấta0 xn + a1 xn−1 + . . . + ak xn−k = 0(1)Phương trình đặc trưng của (1) là phương trình bậc k định bởi:a0 λk + a1 λk−1 + . . . + ak = 0(∗)✄ Trường hợp k = 1. Phương trình đặc trưng (∗) trở thànha0 λ + a1 = 0nên có nghiệm làλ0 = −a1.a0Khi đó, (1) có nghiệm tổng quát là: xn = C · λn0.✄ Trường hợp k = 2. Phương trình đặc trưng (∗) trở thànha0 λ2 + a1 λ + a2 = 0(∗)Người ta chứng minh được kết quả sau:Chương 4. Hệ thức đệ quyTháng 10 - 20169/31Nếu (∗) có hai nghiệm thực phân biệt λ1 và λ2 thì (1) có nghiệmtổng quát là:nxn = C1 · λn1 + C 2 · λ2Nếu (∗) có nghiệm kép thực λ0 thì (1) có nghiệm tổng quát làxn = (C1 + nC2 ) · λn0Nếu (∗) có hai nghiệm phức liên hợp được viết dưới dạngλ = r(cos ϕ ± i sin ϕ)thì (1) có nghiệm tổng quát làxn = r n (A cos nϕ + B sin nϕ)Ví dụ. Giải hệ thức đệ quyxn − 2xn−1 = 0x0 = 5.(1)Giải. Phương trình đặc trưng là λ − 2 = 0 có nghiệm là λ = 2. Suy ra(1) có nghiệm tổng quát là xn = C · 2n .Từ điều kiện x0 = 5 ta có C = 5. Suy ra nghiệm của (∗) là xn = 5 · 2n .Chương 4. Hệ thức đệ quyTháng 10 - 201610/31 xn = 5xn−1 − 6xn−2 ;x0 = 4;Ví dụ. Tìm nghiệm củax1 = 9.Giải.(2)xn = 5xn−1 − 6xn−2⇔ xn − 5xn−1 + 6xn−2 = 0Phương trình đặc trưngλ2 − 5λ + 6 = 0có 2 nghiệm thực phân biệt λ1 = 2 và λ2 = 3. Suy ra (2) có nghiệmtổng quát làxn = C1 · 2n + C2 · 3n .C1 + C2 = 4;Suy ra C1 = 3, C2 = 1. Vậy2C1 + 3C2 = 9.nghiệm của hệ thức đệ quy làVì x0 = 4; x1 = 9 nênxn = 3 · 2n + 3n .Chương 4. Hệ thức đệ quyTháng 10 - 201611/31 4xn+1 − 12xn + 9xn−1 = 0;x0 = 2;Ví dụ. Tìm nghiệm củax1 = 9.(3)Giải. Phương trình đặc trưng4λ2 − 12λ + 9 = 0có 1 nghiệm thực kép là λ0 = 3/2. Suy ra (3) có nghiệm tổng quát làn32xn = (C1 + nC2 ). C1 = 2;Vì x0 = 2; x1 = 9 nênSuy ra C1 = 2, C2 = 4. Vậy 3 (C1 + C2 ) = 9.2nghiệm của hệ thức đệ quy làxn = (2 + 4n)32nChương 4. Hệ thức đệ quy.Tháng 10 - 201612/31 xn+2 − 2xn+1 + 4xn = 0;x0 = 1;Ví dụ. Tìm nghiệm củax1 = 4.(4)Giải. Phương trình đặc trưng λ2 − 2λ + 4 = 0 có 2 nghiệm phức liênhợp là√ππλ = 1 ± i 3 = 2 cos ± i sin.33Suy ra (4) có nghiệm tổng quát lànπnπ+ B sin.xn = 2n A cos33 A = 1; √13Vì x0 = 1; x1 = 4 nênSuy ra 2 2 A + 2 B = 4.√A = 1, B = 3. Vậy nghiệm của hệ thức đệ quy lànπ √nπxn = 2n cos+ 3 sin.33Chương 4. Hệ thức đệ quyTháng 10 - 201613/314.4. Nghiệm của HTĐQTT không thuần nhấtXét hệ thức đệ quy tuyến tính không thuần nhấta0 xn + a1 xn−1 + . . . + ak xn−k = fn(1)Hệ thức đệ quy tuyến tính thuần nhất tương ứng làa0 xn + a1 xn−1 + . . . + ak xn−k = 0(2)Phương trình đặc trưng của (2) là:a0 λk + a1 λk−1 + . . . + ak = 0(∗)Khi đóĐể tìm một nghiệm riêng của (1), ta xem xét các dạng đặc biệt của vếphải fn như sau:Chương 4. Hệ thức đệ quyTháng 10 - 201614/31Dạng 1. fn = β n Pr (n), trong đó Pr (n) là một đa thức bậc r theon; β là một hằng số.Dạng 2. fn = fn1 + fn2 + . . . + fns , trong đó các fn1 , fn2 , . . . , fnsthuộc Dạng 1.Dạng 1. fn = β n Pr (n). Có ba trường hợp xảy ra:TH 1. Nếu β 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:xn = β n Qr (n)TH 2. Nếu β là nghiệm đơn của phương trình đặc trưng (∗) thì(1) có một nghiệm riêng dạng:xn = nβ n Qr (n)TH 3. Nếu β 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:xn = n2 β n Qr (n)Chương 4. Hệ thức đệ quyTháng 10 - 201615/31Chú ý Qr (n) = Ar nr + Ar−1 nr−1 + . . . + A0 là đa thức có cùngbậ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à chon 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.Dạng 2. fn = fn1 + fn2 + . . . + fns . Bằng cách như trên ta tìm đượcnghiệm riêng xni (1 ≤ i ≤ s) của hệ thức đệ quya0 xn + a1 xn−1 + . . . + ak xn−k = fniKhi đóxn = xn1 + xn2 + . . . + xnslà một nghiệm riêng của (1).Chương 4. Hệ thức đệ quyTháng 10 - 201616/31Ví dụ. Cho hệ thức đệ quyxn − 5xn−1 + 6xn−2 = fn(1).Khi đó hệ thức đệ quy tuyến tính thuần nhất tương ứng là:xn − 5xn−1 + 6xn−2 = 0(2)Phương trình đặc trưng của (2) là:λ2 − 5λ + 6 = 0(∗)có hai nghiệm thực là λ1 = 2 và λ2 = 3.(p)Nếu fn = 2n + 1 thì (1) có nghiệm riêng dạng xn = An + B.(p)Nếu fn = 5n (3n2 + 2n + 1) thì xn = 5n (An2 + Bn + C).(p)Nếu fn = 5n , thì xn = 5n A.(p)Nếu fn = 3n thì xn = n3n A.(p)Nếu fn = 2n (3n + 1) thì xn = n2n (An + B).Chương 4. Hệ thức đệ quyTháng 10 - 201617/31Ví dụ. Cho hệ thức đệ quyxn − 6xn−1 + 9xn−2 = fn(1).Khi đó hệ thức đệ quy tuyến tính thuần nhất tương ứng là:xn − 6xn−1 + 9xn−2 = 0(2)Phương trình đặc trưng của (2) là:λ2 − 6λ + 9 = 0(∗)có nghiệm kép là λ0 = 3.(p)Nếu fn = 3n thì (1) có nghiệm riêng dạng xn = n2 3n A.(p)Nếu fn = 3n (5n + 1) thì xn = n2 3n (An + B).(p)Nếu fn = 2n (5n + 1) thì xn = 2n (An + B).Chương 4. Hệ thức đệ quyTháng 10 - 201618/31Ví dụ. Tìm nghiệm củaxn − 5xn−1 + 6xn−2 = 2n + 1;x0 = 1; x1 = 3.(1)Giải. Hệ thức đệ quy tuyến tính thuần nhất tương ứng là:xn − 5xn−1 + 6xn−2 = 0(2)Phương trình đặc trưng của (2) là:λ2 − 5λ + 6 = 0(∗)có hai nghiệm thực là λ1 = 2 và λ2 = 3. Do đó nghiệm tổng quát của(2) là:xn = C1 2n + C2 3n(3)Bây giờ ta tìm một nghiệm riêng của (1). Vế phải của (1) làfn = 2n + 1 có dạng β n Pr (n) với β = 1 và Pr (n) là đa thức bậc r = 1.Vì β = 1 không là nghiệm của phương trình đặc trưng (∗) nên (1) cómột nghiệm riêng dạng:xn = an + b(4)Chương 4. Hệ thức đệ quyTháng 10 - 201619/31Thế (4) vào (1) ta được:(an + b) − 5[a(n − 1) + b] + 6[a(n − 2) + b] = 2n + 1.Cho n lần lượt nhận hai giá trị n = 0; n = 1 ta được hệ:−7a + 2b = 1;−5a + 2b = 3.Giải hệ trên ta được a = 1; b = 4. Thế vào (4) ta tìm được một nghiệmriêng của (1) là:xn = n + 4(5)Từ (3) và (5) ta suy ra nghiệm tổng quát của (1) là:xn = C1 2n + C2 3n + n + 4(6)Thay điều kiện x0 = 1 và x1 = 3 vào (6) ta đượcC1 + C2 = −3;2C1 + 3C2 = −2.Từ đó ta có C1 = −7 và C2 = 4. Thế vào (6) ta đượcxn = −7 · 2n + 4 · 3n + n + 4.Chương 4. Hệ thức đệ quyTháng 10 - 201620/31Ví dụ. Giải hệ thức đệ quy2xn − 3xn−1 + xn−2 = 4n + 1.(1)Giải. Hệ thức đệ quy tuyến tính thuần nhất tương ứng là:2xn − 3xn−1 + xn−2 = 0(2)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. Do đó nghiệm tổng quát của(2) là:1 nx n = C1 + C22Bâ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 β n Pr (n) với β = 1 và Pr (n) là đa thức bậc r = 1.Chương 4. Hệ thức đệ quyTháng 10 - 201621/31Vì β = 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)Thế (4) vào (1) ta được: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ệ:a + b = 1;3a + b = 5.Giải hệ trên ta được a = 2; b = −1. Thế vào (4) ta tìm được mộtnghiệ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à:x n = C1 + C212n+ n(2n − 1)Chương 4. Hệ thức đệ quyTháng 10 - 201622/31Ví dụ. Tìm nghiệm củaxn+1 − 6xn + 9xn−1 = (18n + 12)3n ;x0 = 2; x1 = 0.(1)Giải. Hệ thức đệ quy tuyến tính thuần nhất tương ứng là:xn+1 − 6xn + 9xn−1 = 0(2)Phương trình đặc trưng của (2) là:λ2 − 6λ + 9 = 0(∗)có nghiệm kép là λ0 = 3. Do đó nghiệm tổng quát của (2) là:xn = (C1 + nC2 )3n(3)Bây giờ ta tìm một nghiệm riêng của (1).Vế phải của (1) làfn = (18n + 12)3n có dạng β n Pr (n) với β = 3 và Pr (n) là đa thức bậcr = 1.Vì β = 3 là nghiệm kép của phương trình đặc trưng (∗) nên (1) cómột nghiệm riêng dạng:xn = n2 3n (an + b)(4)Thế (4) vào (1) ta được:Chương 4. Hệ thức đệ quyTháng 10 - 201623/31(n + 1)2 3n+1 [a(n + 1) + b] − 6n2 3n (an + b)+9(n − 1)2 3n−1 [a(n − 1) + b] = (18n + 12)3n .Cho n lần lượt nhận hai giá trị n = 0; n = 1 ta được hệ:6b = 12;54a + 18b = 90.Giải hệ trên ta được a = 1; b = 2. Thế vào (4) ta tìm được một nghiệmriêng của (1) là:xn = n2 (n + 2)3n(5)Từ (3) và (5) ta suy ra nghiệm tổng quát của (1) là:xn = (C1 + nC2 )3n + n2 (n + 2)3n(6)Thay điều kiện x0 = 2 và x1 = 0 vào (6) ta đượcC1 = 23C1 + 3C2 + 9 = 0.Từ đó ta có C1 = 2 và C2 = −5. Thế vào (6) ta đượcxn = (2 − 5n)3n + n2 (n + 2)3n = 3n (n3 + 2n2 − 5n + 2)Chương 4. Hệ thức đệ quyTháng 10 - 201624/31Ví dụ. Tìm nghiệm của hệ thức đệ quyxn − 4xn−1 + 3xn−2 = 20 + (2 − n)2n−2 + 3 · 4n(1)Giải. Hệ thức đệ quy tuyến tính thuần nhất tương ứng là:xn − 4xn−1 + 3xn−2 = 0(2)Phương trình đặc trưng của (2) là:λ2 − 4λ + 3 = 0(∗)có hai nghiệm thực là λ1 = 1 và λ2 = 3. Do đó nghiệm tổng quát của(2) là:xn = C1 + C2 · 3n(3)Bây giờ ta tìm một nghiệm riêng của (1). Vế phải của (1) làfn = 20 + (2 − n)2n−2 + 3 · 4n thuộc Dạng 2. Ta xét các hệ thức đệquy sau:Chương 4. Hệ thức đệ quyTháng 10 - 201625/31