Bài Giảng Toán Rời Rạc - Chương 4: Hệ Thức đệ Quy - Nguyễn Anh Thi

Có thể bạn quan tâm

Trang chủ
Đăng ký
Đăng nhập
Liên hệ

Tài liệu - Ebook

Thư viện tài liệu, ebook, đồ án, luận văn, giáo trình tham khảo cho học sinh, sinh viên

Bài giảng Toán rời rạc - Chương 4: Hệ thức đệ quy - Nguyễn Anh Thi

Dạng 1, fn = βnPr(n), có ba trường hợp xảy ra:

• TH1: 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 = βnQr(n).

• TH2: 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βnQr(n).

• TH3: 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βnQr(n)

Nguyễn Anh Thi Bài giảng môn học Toán Rời RạcBài giảng môn

học Toán Rời

Rạc

Nguyễn Anh

Thi

Nội dung

Hệ thức đệ quy tuyến

tính với hệ số hằng

Nghiệm của hệ thức

đệ quy tuyến tính

thuần nhất

Nghiệm của hệ thức

đệ quy tuyến tính

không thuần nhất

Nội dung

Hệ thức đệ quy tuyến tính với hệ số hằng

Nghiệm của hệ thức đệ quy tuyến tính thuần nhất

Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất

Chú ý

Qr(n) = Arnr + Ar−1nr−1 + · · · + A0 là đa thức 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 phương trình này.

33 trang | Chia sẻ: trungkhoi17 | Lượt xem: 7460 | Lượt tải: 3

Bạn đang xem trước 20 trang tài liệu Bài giảng Toán rời rạc - Chương 4: Hệ thức đệ quy - Nguyễn Anh Thi, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trênNguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất 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 a0xn + a1xn−1 + · · ·+ akxn−k = fn trong đó • a0 6= 0, a1, a2, . . . , ak là các hệ số thực, • {fn} là một dãy các số thực cho trước, • {xn} là dãy ẩn nhận giá trị thực. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Trường hợp dãy fn = 0 với mọi n thì hệ thức trên trở thành a0xn + a1xn−1 + · · ·+ akxn−k = 0(∗) và ta gọi (∗) là hệ thức đệ quy tuyến tính thuần nhất cấp k với hệ số hằng. Ví dụ • 2xn + 3xn−1 + 5xn−2 = n2 + 1 • xn+2 − xn+1 + xn = 0 • xn + xn−1 − 2xn−2 = 3n(n3 + 1) Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Định nghĩa Mỗi dãy {xn} thỏa mãn hệ thức a0xn + a1xn−1 + · · ·+ akxn−k = fn được gọi là một nghiệm của hệ thức đó. Ta thấy mỗi nghiệm {xn} của hệ thức trên được hoàn toàn xác định bởi k 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 nếu mọi dãy của họ này đều là nghiệm. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Với k giá trị ban đầu y0, y1, . . . , yk−1 tồn tại duy nhất các giá trị của k tham số C1,C2, . . . ,Ck sao cho nghiệm {xn} tương ứng thỏa x0 = y0, x1 = y1, . . . , xk−1 = yk−1 Khi đó nghiệm xn tương ứng được gọi là nghiệm riêng ứng với điều kiện ban đầu. Chú ý Giải một hệ thức đệ quy là đi tìm nghiệm tổng quát của nó. Nếu hệ thức đệ quy có đi kèm điều kiện ban đầu, ta phải tìm nghiệm thỏa mãn điều kiện ban đầu đó. Ví dụ • 2xn − 3xn−1 = 0 có nghiệm tổng quát là xn = C(32)n. •  xn − 5xn−1 + 6xn−2 = 0; x0 = 4; x1 = 9. có nghiệm là xn = 3.2n + 3n. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Định nghĩa Xét hệ thức đệ quy tuyến tính thuần nhất a0xn + a1xn−1 + · · ·+ akxn−k = 0 Phương trình đặc trưng của hệ thức trên là phương trình bậc k định bởi a0λk + a1λk−1 + · · ·+ ak = 0. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất • Với k = 1, phương trình đặc trưng trở thành a0λ+ a1 = 0, và có nghiệm là λ0 = −a1a0 . Khi đó hệ thức đệ quy có nghiệm tổng quát là xn = C.λn0 . • Với k = 2, phương trình đặc trưng trở thành a0λ2 + a1λ+ a2 = 0. • Nếu phương trình đặc trưng có hai nghiệm thực phân biệt λ1, λ2 thì hệ thức đệ quy có nghiệm tổng quát là xn = C1.λn1 + C2.λn2 . • Nếu phương trình đặc trưng có nghiệm kép thực λ0 thì hệ thức đệ quy có nghiệm tổng quát là xn = (C1 + nC2).λn0 . • Nếu phương trình đặc trưng có hai nghiệm phức liên hợp được viết dưới dạng λ = r(cosϕ± i sinϕ) thì hệ thức đệ quy có nghiệm tổng quát là xn = rn(A cosnϕ+ B sinnϕ). Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Giải hệ thức đệ quy { xn − 2xn−1 = 0 x0 = 5 Nghiệm xn = 5.2n. Ví dụ Tìm nghiệm của  xn = 5xn−1 − 6xn−2; x0 = 4; x1 = 9. Nghiệm xn = 3.2n + 3n. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Giải hệ thức đệ quy { xn − 2xn−1 = 0 x0 = 5 Nghiệm xn = 5.2n. Ví dụ Tìm nghiệm của  xn = 5xn−1 − 6xn−2; x0 = 4; x1 = 9. Nghiệm xn = 3.2n + 3n. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Giải hệ thức đệ quy { xn − 2xn−1 = 0 x0 = 5 Nghiệm xn = 5.2n. Ví dụ Tìm nghiệm của  xn = 5xn−1 − 6xn−2; x0 = 4; x1 = 9. Nghiệm xn = 3.2n + 3n. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Tìm nghiệm của  4xn+1 − 12xn + 9xn−1 = 0; x0 = 2; x1 = 9. Nghiệm xn = (2+ 4n) ( 3 2 )n Ví dụ Tìm nghiệm của  xn+2 − 2xn+1 + 4xn = 0; x0 = 1; x1 = 4. Nghiệm xn = 2n ( cos npi3 + √ 3 sin npi3 ) Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Tìm nghiệm của  4xn+1 − 12xn + 9xn−1 = 0; x0 = 2; x1 = 9. Nghiệm xn = (2+ 4n) ( 3 2 )n Ví dụ Tìm nghiệm của  xn+2 − 2xn+1 + 4xn = 0; x0 = 1; x1 = 4. Nghiệm xn = 2n ( cos npi3 + √ 3 sin npi3 ) Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Tìm nghiệm của  4xn+1 − 12xn + 9xn−1 = 0; x0 = 2; x1 = 9. Nghiệm xn = (2+ 4n) ( 3 2 )n Ví dụ Tìm nghiệm của  xn+2 − 2xn+1 + 4xn = 0; x0 = 1; x1 = 4. Nghiệm xn = 2n ( cos npi3 + √ 3 sin npi3 ) Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Xét hệ thức đệ quy tuyến tính không thuần nhất a0xn + a1xn−1 + · · ·+ akxn−k = fn (1) Hệ thức đệ quy tuyến tính thuần nhất tương ứng là a0xn + a1xn−1 + · · ·+ akxn−k = 0 (2) Phương trình đặc trưng của (2) là a0λk + a1λk−1 + · · ·+ ak = 0. (∗) Khi đó nghiệm tổng quát của (1) =nghiệm tổng quát của (2)+ nghiệm riêng của (1) Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Để tìm một nghiệm riêng của (1), ta xem xét hai dạng đặc biệt của vế phải fn 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 = fn1 + fn2 + · · ·+ fns , trong đó các fn1 , fn2 , . . . , fns thuộc dạng 1. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Dạng 1 Dạng 1, fn = βnPr(n), có ba trường hợp xảy ra: • TH1: 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 = βnQr(n). • TH2: 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βnQr(n). • TH3: 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βnQr(n) Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Chú ý Qr(n) = Arnr + Ar−1nr−1 + · · ·+ A0 là đa thức 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 phương trình này. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Dạng 2 Dạng 2, fn = fn1 + fn2 + · · ·+ fns 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). Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Cho hệ thức đệ quy xn − 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 Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất • Nếu fn = 2n+ 1 thì (1) có nghiệm riêng dạng x(P)n = An+ B • Nếu fn = 5n(3n2 + 2n+ 1) thì x(P)n = 5n(An2 + Bn+ C) • Nếu fn = 5n, thì x(P)n = 5nA • Nếu fn = 3n, thì x(P)n = n3nA • Nếu fn = 2n(3n+ 1), thì x(P)n = n2n(An+ B) Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Cho hệ thức đệ quy xn − 6xn−1 + 9xn−2 = fn (1). Ta có hệ thức đệ quy tuyến tính thuần nhất là xn − 6xn−1 + 9xn−2 = 0 (2) Phương trình đặc trưng của (2) là λ2 − 6λ+ 9 = 0. (∗) Phương trình (∗) có nghiệm kép là λ0 = 3. • Nếu fn = 3n thì (1) có nghiệm riêng dạng x(P)n = n23nA. • Nếu fn = 3n(2n+ 1) thì x(P)n = n23n(An+ B). • Nếu fn = 4n(2n+ 1) thì x(P)n = 4n(An+ B). Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Một số ví dụ Ví dụ (Bài toán Tháp Hà Hội) Cho n ≥ 1, có ba cọc I, II, và III. Tại cọc I đang có n cái đĩa tròn có bán kính khác nhau (ta đặt đĩa theo nguyên tắc là đĩa nhỏ ở phía trên đĩa lớn). Chuyển n cái đĩa ở cọc I sang cọc III, có thể qua trung gian cọc II, mỗi lần chuyển được 1 chiếc đĩa. Gọi xn là số lần chuyển đĩa, tìm xn? Hướng dẫn. Với n = 1, ta có x1 = 1. Với n ≥ 1, đầu tiên ta chuyển n− 1 đĩa bên trên sang cọc II (lấy cọc III làm trung gian), giữ nguyên đĩa thứ n cuối cùng ở cọc I. Ta thấy số lần chuyển n− 1 đĩa đó là xn−1. Sau đó ta chuyển đĩa thứ n từ cọc I sang cọc III. Cuối cùng chuyển n− 1 đĩa từ cọc II qua cọc III (lấy cọc I làm trung gian). Số lần chuyển n− 1 đĩa đó là xn−1. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Vậy số lần chuyển n đĩa từ cọc I sang III là xn = 2xn−1 + 1 Ta có { x1 = 1 xn = 2xn−1 + 1 với n > 1. SV giải hệ thức đệ quy trên. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Một cầu thang có n bậc. Mỗi bước đi gồm 1 hay 2 bậc. Gọi xn là số cách đi hết cầu thang. Tìm xn? Hướng dẫn. • Với n = 1, ta có x1 = 1. • Với n = 2, ta có x2 = 2. • Với n > 2, ta xét hai trường hợp: • TH1: bước đầu tiên gồm 1 bậc. Khi đó, cầu thang còn n− 1 bậc nên số cách đi hết cầu thang là xn−1. • TH2: bước đầu tiên gồm 2 bậc. Khi đó, cầu thang còn n− 2 bậc nên số cách đi hết cầu thang là xn−2. Theo nguyên lý cộng, số cách đi hết cầu thang là xn−1 + xn−2. Do đó xn = xn−1 + xn−2. Như vậy, { x1 = 1, x2 = 2; xn = xn−1 + xn−2 với n > 2. SV giải hệ thức trên. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Giải hệ thức đệ quy { xn − 5xn−1 + 6xn−2 = 2n+ 1; x0 = 1; x1 = 3. Đáp án. xn = −7.2n + 4.3n + n+ 4. Ví dụ Giải hệ thức đệ quy 2xn − 3xn−1 + xn−2 = 4n+ 1. Đáp án. xn = C1 + C2 ( 1 2 )n + n(2n− 1). Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Giải hệ thức đệ quy { xn − 5xn−1 + 6xn−2 = 2n+ 1; x0 = 1; x1 = 3. Đáp án. xn = −7.2n + 4.3n + n+ 4. Ví dụ Giải hệ thức đệ quy 2xn − 3xn−1 + xn−2 = 4n+ 1. Đáp án. xn = C1 + C2 ( 1 2 )n + n(2n− 1). Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Giải hệ thức đệ quy { xn − 5xn−1 + 6xn−2 = 2n+ 1; x0 = 1; x1 = 3. Đáp án. xn = −7.2n + 4.3n + n+ 4. Ví dụ Giải hệ thức đệ quy 2xn − 3xn−1 + xn−2 = 4n+ 1. Đáp án. xn = C1 + C2 ( 1 2 )n + n(2n− 1). Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Giải hệ thức đệ quy { xn+1 − 6xn + 9xn−1 = (18n+ 12)3n; x0 = 2; x1 = 0. Đáp án. xn = 3n(n3 + 2n2 − 5n+ 2). Ví dụ Giải hệ thức đệ quy xn − 4xn−1 + 3xn−2 = 20+ (2− n)2n−2 + 3.4n Đáp án. xn = C1 + C2.3n − 10n+ n2n + 4n+2. Ví dụ Cho x0 = 1 và x1 = 2. Tìm nghiệm của hệ thức đệ quy xn+1 − 3xn + 2xn−1 = n, với n ≥ 1. Đáp án. xn = 3.2n − 12n2 − 32n− 2. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Giải hệ thức đệ quy { xn+1 − 6xn + 9xn−1 = (18n+ 12)3n; x0 = 2; x1 = 0. Đáp án. xn = 3n(n3 + 2n2 − 5n+ 2). Ví dụ Giải hệ thức đệ quy xn − 4xn−1 + 3xn−2 = 20+ (2− n)2n−2 + 3.4n Đáp án. xn = C1 + C2.3n − 10n+ n2n + 4n+2. Ví dụ Cho x0 = 1 và x1 = 2. Tìm nghiệm của hệ thức đệ quy xn+1 − 3xn + 2xn−1 = n, với n ≥ 1. Đáp án. xn = 3.2n − 12n2 − 32n− 2. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuyến tính thuần nhất Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Giải hệ thức đệ quy { xn+1 − 6xn + 9xn−1 = (18n+ 12)3n; x0 = 2; x1 = 0. Đáp án. xn = 3n(n3 + 2n2 − 5n+ 2). Ví dụ Giải hệ thức đệ quy xn − 4xn−1 + 3xn−2 = 20+ (2− n)2n−2 + 3.4n Đáp án. xn = C1 + C2.3n − 10n+ n2n + 4n+2. Ví dụ Cho x0 = 1 và x1 = 2. Tìm nghiệm của hệ thức đệ quy xn+1 − 3xn + 2xn−1 = n, với n ≥ 1. Đáp án. xn = 3.2n − 12n2 − 32n− 2. Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc Bài giảng môn học Toán Rời Rạc Nguyễn Anh Thi Nội dung Hệ thức đệ quy tuyến tính với hệ số hằng Nghiệm của hệ thức đệ quy tuy

Các file đính kèm theo tài liệu này:

bai_giang_toan_roi_rac_chuong_4_he_thuc_de_quy_nguyen_anh_th.pdf

Tài liệu liên quan

Luận văn Phân lớp đối đồng điều các ANN - Hàm tử và các ANN - phạm trù bện
114 trang | Lượt xem: 1522 | Lượt tải: 0
Luận văn Phương pháp lặp Banach cho bài toán bất đẳng thức biến phân
49 trang | Lượt xem: 1555 | Lượt tải: 1
Nhị thức Niutơn - Lý thuyết và bài tập
11 trang | Lượt xem: 53013 | Lượt tải: 1
Gián án Toán 10 - Đường hypebol
8 trang | Lượt xem: 3751 | Lượt tải: 0
Chuyên đề Hệ phương trình đối xứng loại I
14 trang | Lượt xem: 26497 | Lượt tải: 1
Giáo án Toán Lớp 10 - Chương 3, Bài 3: Phương trình và hệ phương trình bậc nhất nhiều ẩn
11 trang | Lượt xem: 590 | Lượt tải: 0
Bài giảng Lý thuyết xác suất - Chương 6: Tổng thể và mẫu
15 trang | Lượt xem: 471 | Lượt tải: 0
Giáo trình Lý thuyết đồ thị - Chương 1: Các khái niệm cơ bản về đồ thị
17 trang | Lượt xem: 572 | Lượt tải: 0
Tài liệu Ép tích bằng ẩn phụ
39 trang | Lượt xem: 432 | Lượt tải: 0
Một số phương trình Diophantine và cách giải chúng
21 trang | Lượt xem: 7931 | Lượt tải: 1