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

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
Bài giảng môn học Toán Rời Rạc
Nguyễn Anh Thi
Trường Đại học Khoa học Tự nhiên, Tp Hồ Chí Minh
2017
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
Chương 4
Hệ thức đệ quy
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ộ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ế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