Đề cương môn Toán rời rạc - Trường Đại học lao động - xã hội.
Một quy tắc cho phép tìm các số hạng tiếp theo từ các số hạng trước được gọi là một hệ thức truy hồi. Trong tin học, do tính chất kế thừa nên công thức truy hồi là một công cụ hổ trợ tốt cho việc lập trình vì giúp làm giảm độ phức tạp của quá trình tính toán.
Đề cương môn Toán rời rạc - Trường Đại học lao động - xã hội. Tài liệu được sưu tầm gồm 13 trang giúp bạn tham khảo , ôn tập và đạt kết quả cao
Môn: Toán rời rạc (TORR1123L) 22 tài liệu
Trường: Đại học Lao động - Xã hội 1.9 K tài liệu
Tác giả:
Preview text:
CHƯƠNG 4. HỆ THỨC TRUY HỒI
Chủ đề 4.1. Các khái niệm
4.1.1. Định nghĩa hệ thức truy hồi
Một quy tắc cho phép tìm các số hạng tiếp theo từ các số hạng trước được gọi là một hệ
thức truy hồi. Trong tin học, do tính chất kế thừa nên công thức truy hồi là một công cụ
hổ trợ tốt cho việc lập trình vì giúp làm giảm độ phức tạp của quá trình tính toán.
Hệ thức truy hồi của một dãy số {a } là một biểu thức, trong đó phần tử a của dãy được n n
định nghĩa thông qua một (hoặc nhiều) phần tử trước nó trong dãy cùng với một số điều
kiện đầu xác định, nghĩa là
a = f (a , a , ..., a ) , 6n ≥ k ≥ 0 n n–1 n–2 n–k
và các điều kiện đầu a = C , a = C , ..., a = C 0 0 1 1 k–1 k–1
Ví dụ 1. Cho dãy số {a } thỏa a = a – a
với n = 2, 3, 4, ... và a = 10, a = 18 . Tìm a và n n n–1 n–2 0 1 3 a ? 4 Giải. Ta có
a = a – a = 18 – 10 = 8 2 1 0
a = a – a = 8 – 18 = –10 3 2 1
a = a – a = –10 – 8 = –18 4 3 2
Ví dụ 2. Bác An gởi tiết kiệm vào ngân hàng 100 triệu theo hình thức lãi kép với lãi suất
7.5%/năm. Hỏi sau 10 năm Bác An nhận lại được bao nhiêu tiền? Giải.
Ta biết, với hình thức lãi kép thì tiền vốn của cuối năm nhất bao gồm tiền gốc ban đầu
cộng với tiền lãi của năm đầu tiên.
Gọi P = 100 (triệu) là tiền gởi ban đầu, r = 7.5% là lãi suất 0
Tiền nhận được sau năm nhất: P = P + r.P = (1 + r ) P 1 0 0 0
Tiền nhận được sau năm hai: P = (1 + r ) P + r.(1 + r ).P = (1 + r ) P .(1 + r ) = (1 + r )2 .P 2 0 0 0 0
Tiền nhận được sau năm ba:
P = (1 + r )2 .P + r.(1 + r )2 .P = (1 + r )2 .P .(1 + r ) = (1 + r )3 .P 3 0 0 0 0 ……
Tiền nhận được sau năm thứ n: P = (1 + r )n .P n 0
Vậy số tiền bác An nhận được sau 10 năm là
P = (1 + r )10 .P = (1 + 0.075)10 .100 = 206.103 (triệu). 10 0 a = a + a ,6n ≥ 2
Ví dụ 3. Dãy số kinh điển Fibonacci được định nghĩa n n–1 n–2 , các điều kiện a = 1, a = 1 0 1
đầu là a = 1, a = 1 , công thức truy hồi có hiệu lực từ n = 2. 0 1
Cụ thể, các số đầu tiên của dãy Fibonacci là 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
4.1.2. Nghiệm của hệ thức truyhồi
Dãy {a } được gọi là nghiệm của một hệ thức truy hồi nếu các số hạng của nó thỏa mãn n hệ thức truy hồi này. Ví dụ.
Dãy {a } = {1,1, 2, 3, 5, 8,13, 21,...} là nghiệm của dãy Fibonacci a = a
+ a , 6n ≥ 2 với n n n–1 n–2
a = 1, a = 1 , vì các số hạng của nó thỏa mãn dãy này. 0 1
4.1.3. Giải toán bằng mô hình hệ thức truy hồi.
Ví dụ 1. Một người gởi 100.000 vào ngân hàng với lãi kép 7.5%/năm. Hỏi sau 10 năm anh ta
có bao nhiêu tiền trong tài khoản? Giải
Ta biết, với hình thức lãi kép thì tiền vốn của cuối năm nhất bao gồm tiền gốc ban đầu
cộng với tiền lãi của năm đầu tiên.
Gọi P là tổng số tiền có được sau năm thứ n, ta có n
P = P + 0.075 P = 1.075 P n n–1 n–1 n–1
Dễ thấy P là công thức truy hồi với điều kiện đầu P = 100 (triệu), ta có n 0 P = 1.075 P 1 0
P = 1.075 P = (1.075)2 P 2 1 0
P = 1.075 P = (1.075)3 P 3 2 0 ....
P = (1.075)n P n 0
Thay n = 10 vào công thức, ta có số tiền sau 10 năm là
P = (1.075)10 100 = 206.103 10
Ví dụ 2. Tìm tất cả các chuỗi nhị phân n bit không có 2 số 0 liên tiếp? Giải
Gọi S là số chuỗi nhị phân n bit không có 2 số không liên tiếp. Ta chia S thành 2 tập n n
B = {(b b ...b 1) b b s 00} và B = {(b b ...b 0) b b s 00} 1 1 2 n–1 i i +1 2 1 2 n–1 i i +1
Ta có S = B + B , với B = S và B = S n 1 2 1 n–1 2 n–2
Vì trong B , b = 0 nên b
= 1 . Suy ra B = {(b b ...b 10) b b s 00} 2 n n–1 2 1 2 n–2 i i+1
Vậy ta có công thức truy hồi S = S
+ S , n ≥ 3, S = 2, S = 3 . n n–1 n–2 1 2
BÀI TẬP TỰ ĐÁNH GIÁ CHỦ ĐỀ 4.1
1. Nghiệm của hệ thức truy hồi a = a
+ 2a , 6n ≥ 2 với a = 0, a = 1 là dãy n n–1 n–2 0 1
A. {0,1,1, 3, 5,11, 21, 43, 85,...}
B. {0,1, 2, 5,12, 29,70,85, .... }
C. {0,1,1, 3, 5, 8,13, 21, 34, 55,...}
D. {0,1,1, 2, 3, 5,8,13, 21, 34, 55,...}
2. Đâu là một hệ thức truy hồi chính xác ?
A. a = a + 2a , 6n ≥ 2 với a = 0, a = 1 B. a = a + 2a , 6n ≥ 2 với a = 0 n n–1 n–2 0 1 n n–1 n–2 0
C. a = a + 2a , 6n ≥ 3 với a = 0, a = 1 D. a = a
+ 2a , 6n ≥ 2 với a = 1, a = 1 n n–1 n–2 0 1 n n–1 n–2 1 2
3. Một người gửi $20.000 vào ngân hàng với lãi kép 12%/năm. Hỏi sau 20 năm anh ta có bao
nhiêu tiền trong tài khoản? A. ~$192.926 B. ~$190.000 C. ~$448.000 D. ~$450.542
4. Số chuỗi nhị phân 8 bit không có 2 số 0 liên tiếp là? A. 55 B. 34 C.89 D. 144 Đáp án: 1.A, 2.A, 3.A, 4.A
Chủ đề 4.2. Giải hệ thức truy hồi
4.2.1. Các khái niệm.
Giải hệ thức truy hồi.
Giải hệ thức truy hồi của dãy số {a } là làm cho biểu diễn của số hạng a không còn phụ n n
thuộc vào các số hạng trước nó mà chỉ phụ thuộc vào n. Ví dụ
Trong ví dụ 2 ở phần 4.1.1. (bài toán lãi kép) ta đã giải công thức truy hồi
P = (1 + r )n .P với P = 100 (triệu) n 0 0
Ta thấy P chỉ phụ thuộc vào n mà không phụ thuộc các số hạng trước đó như P , … n n–1
Phân loại hệ thức truy hồi.
Hệ thức truy hồi bậc k > 0 có dạng
c ..a = c .a + c .a
+... + c .a , n ≥ k 0 n 1 n–1 2 n–2 k n–k
với c , c , c , ... , c là các số thực, c s 0 . Khi tất cả các số hạng a đều ở dạng nguyên mẫu 0 1 2 k k i
ta có hệ thức truy hồi tuyến tính.
Ví dụ. Dãy a = a
+ a + 2a + 2, 6n ≥ 3 với a = 0, a = 1, a = 2 là hệ thức truy hồi tuyến n n–1 n–2 n–3 0 1 2 tính bậc 3.
4.2.2. Hệ thức truy hồi tuyến tính thuần nhất.
Trong hệ thức truy hồi tuyến tính bậc k > 0
c .a = c .a + c .a
+ ... + c .a , n ≥ k 0 n 1 n–1 2 n–2 k n–k
với c , c , c , ... , c là các số thực, c s 0 là hệ thức truy hồi tuyến tính thuần nhất. 0 1 2 k k Ví dụ a = a + a Dãy Fibonacci n n–1 n–2
là hệ thức truy hồi tuyến tính thuần nhất bậc 2. a = 0, a = 1 0 1 a = 2a + 5a – 6a
Hệ thức truy hồi n n–1 n–2
n–3 là hệ thức truy hồi tuyến tính thuần nhất bậc 3.
a = 2, a = –2, a = 9 0 1 2
4.2.3. Giải hệ thức truy hồi tuyến tính thuần nhất
Cho hệ thức truy hồi tuyến tính thuần nhất bậc k > 0 a = c a
+ c a + ... + c a , n ≥ k (1) n 1 n–1 2 n–2 k n–k
Ta tìm nghiệm của hệ thức (1) dưới dạng dãy a = rn với r là hằng số. n
Ta có (1) e rn = c rn–1 + c rn–2 + ... + c rn–k (2) 1 2 k
Chia 2 vế của (2) cho rn–k , chuyển vế ta được rk – c rk–1 – c rk–2 –...– c = 0 (3) 1 2 k
(3) được gọi là phương trình đặc trưng của (1).
Nghiệm của (3) dùng để biểu diễn công thức của tất cả nghiệm của hệ thức truy hồi (1).
a. Hệ thức truy hồi tuyến tính thuần nhất bậc 2
Hệ thức truy hồi tuyến tính bậc 2 có dạng c .a + c .a + c .a = 0 0 n 1 n–1 2 n–2 Công thức nghiệm
Trường hợp 1. Nếu phương trình đặc trưng c .r2 + c .r + c = 0 (với c , c ϵ R ) có 2 nghiệm 0 1 2 1 2
thực phân biệt r và r . Khi đó nghiệm tổng quát của hệ thức truy hồi đã cho có dạng: 1 2 n 1 n 2 n
Ta có thể tìm các số α , β nhờ vào các dữ kiện ban đầu của công thức truy hồi đã cho.
Trường hợp 2. Nếu phương trình đặc trưng c .r2 + c .r + c = 0 (với c , c ϵ R ) có nghiệm 0 1 2 1 2
kép r = r = r . Khi đó nghiệm của hệ thức truy hồi đã cho có dạng: 1 2 n n
Ta có thể tìm các số α , β nhờ vào các dữ kiện ban đầu của công thức truy hồi đã cho. a = a + 2a
Ví dụ 1. Tìm nghiệm của hệ thức truy hồi tuyến tính thuần nhất sau n n–1 n–2 a = 2, a = 7 0 1 Giải
Ta có phương trình đặc trưng: r2 – r – 2 = 0 e
r = 2 (đơn), r = –1 (đơn). 1 2
Nghiệm tổng quát của hệ thức: a = α .(r )n + β .(r )n = α.(2)n + β (–1)n (*) n 1 2 a = 2 α + β = 2 α = 3 Với điều kiện đầu 0 thay vào (*) ta được e a = 7 2α – β = 7 β = –1 1
Vậy nghiệm của hệ thức truy hồi là: a = 3.2n – (–1)n , n ≥ 0 n a = 6a – 9a
Ví dụ 2. Tìm nghiệm của hệ thức truy hồi tuyến tính thuần nhất sau n n–1 n–2 a = 1, a = 6 0 1 Giải
Ta có phương trình đặc trưng: r2 – 6r + 9 = 0 e r = 3 (nghiệm kép)
Nghiệm tổng quát có dạng: a = (α + βn)(r )n = (α + βn).3n (*) n a = 1 α = 1 α = 1 Với điều kiện đầu 0 thay vào (*) ta được e a = 6 3α + 3β = 6 β = 1 1
Vậy nghiệm của hệ thức truy hồi là: a = (1 + n).3n , 6n ϵ . n
b. Hệ thức truy hồi tuyến tính thuần nhất bậc 3
Hệ thức truy hồi tuyến tính bậc 3 có dạng
c .a + c .a
+ c .a + c .a = 0 0 n 1 n–1 2 n–2 3 n–3 Công thức nghiệm
Trường hợp 1. Nếu phương trình đặc trưng c .r3 + c .r2 + c .r + c = 0 (với c , c , c ϵ R ) 0 1 2 3 1 2 3
có 3 nghiệm thực phân biệt r , r và r . Khi đó nghiệm tổng quát của hệ thức truy hồi đã 1 2 3 cho có dạng: 3 n n 2 n 1 n
Ta có thể tìm các số α , β , y nhờ vào các dữ kiện ban đầu của công thức truy hồi đã cho.
Trường hợp 2. Nếu phương trình đặc trưng c .r3 + c .r2 + c .r + c = 0 (với c , c , c ϵ R ) 0 1 2 3 1 2 3
có 1 nghiệm đơn r1 và 1 nghiệm kép r = r = r . Khi đó nghiệm của hệ thức truy hồi đã 2 3 cho có dạng: n 1 n n
Ta có thể tìm các số α , β , y nhờ vào các dữ kiện ban đầu của công thức truy hồi đã cho.
Trường hợp 3. Nếu phương trình đặc trưng c .r3 + c .r2 + c .r + c = 0 (với c , c , c ϵ R ) 0 1 2 3 1 2 3
có 1 nghiệm đơn bội 3 là r = r = r = r . Khi đó nghiệm của hệ thức truy hồi đã cho có 1 2 3 dạng: n n 2
Ta có thể tìm các số α , β , y nhờ vào các dữ kiện ban đầu của công thức truy hồi đã cho.
c. Hệ thức truy hồi tuyến tính thuần nhất bậc cao
Định lý 1. Giả sử phương trình c .rk – c .rk –1 –... – c = 0 (với c , c ,..., c ϵ R, c s 0 ) có k 0 1 k 1 2 k k
nghiệm thực phân biệt r1 , r2 , ... , r . Khi đó, dãy nghiệm của hệ thức truy hồi k
c .a = c .a + c .a +... + c .a 0 n 1 n–1 2 n–2 Có dạng tổng quát
a = α . r n + α . r n + ... n n 1 1 2 2 k k 1 2 k 1 2 2
Định lý 2. Giả sử phương trình c .rk – c .rk –1 –... – c = 0 (với c , c ,..., c ϵ R, c s 0 ) có nghiệm 0 1 k 1 2 k k
bội k là r = r = r = ... = r . Khi đó nghiệm tổng quát của hệ thức truy hồi 1 2 k
c .a = c .a + c .a +... + c .a 0 n 1 n–1 2 n–2 Có dạng tổng quát n 2 1 n 1 2 3 k 1 2 k 1 2 2
a = 6a – 11a + 6a
Ví dụ. Tìm nghiệm của hệ thức truy hồi tuyến tính thuần nhất sau n n–1 n–2 n–3
a = 2, a = 5, a = 15 0 1 2 Giải
Ta có phương trình đặc trưng: r3 – 6r 2 + 11r – 6 = 0 e r = 1, r = 2, r = 3 1 2 3
Nghiệm tổng quát có dạng: a = α .(r )n + α .(r )n + α .(r )n = α .1n + α .2n + α .3n (*) n 1 1 2 2 3 3 1 2 3 a = 2
α + α + α = 2 α = 1 0 1 2 3 1
Với điều kiện đầu a = 5
thay vào (*) ta được α + 2α + 3α = 5 e α = –1 1 1 2 3 2 a = 15
α + 4α + 9α = 15 α = 2 2 1 2 3 3
Vậy nghiệm của hệ thức truy hồi là: a = 1 – 2n + 2.3n , n ϵ . n
MỘT SỐ VÍ DỤ VỀ GIẢI HỆ THỨC TRUY HỒI 2a – 3 = 0
Ví dụ 1. Giải công thức truy hồi n a = 1 1 Bài giải 3
Ta có phương trình đặc trưng 2r – 3 = 0 e r = 2 ( n 3
Công thức nghiệm tổng quát có dạng a = α.rn e a = α. n n 2 ( 1 3
Mà ta có a = 1, nên ta được 1 = α . e α = 2 1 2 3 n 2 ( 3
Vậy nghiệm của công thức truy hồi đã cho là a = . , 6n ϵ . n 3 2 2a – 3a + a = 0
Ví dụ 2. Giải công thức truy hồi n n–1 n–2 a = 1, a = 3 0 1 Bài giải
Ta có phương trình đặc trưng 2r2 – 3r + 1 = 0 e r = 1 (đơn), r = 1 (đơn). 1 2 2 ( 1 n
Công thức nghiệm tổng quát có dạng a = α .(r )n + β .(r )n e a = α.(1)n + β . n n 1 2 2 1 = α + β a = 1 e α = 5
Mà ta có 0 a = 3 , nên ta được 3 = + β β = –4 α 1 2 ( n 1
Vậy nghiệm của công thức truy hồi đã cho là a = 5 – 4. n , 6n ϵ . 2
4a – 12a + 9a = 0
Ví dụ 3. Giải công thức truy hồi a n+1 = 2, a n n–1 = 4 0 1 Bài giải 3
Ta có phương trình đặc trưng 4r2 – 12r + 9 = 0 e r = (nghiệm kép) 2 ( 3 n
Công thức nghiệm tổng quát có dạng a = (α + βn).(r )n e a = (α + βn). n n 2 2 = α α = a 2 Mà ta có 0 = 2 , nên ta được e 3 a = 4 4 = (α + β ). β = 2 1 2 3 ( n 2 ( 3
Vậy nghiệm của công thức truy hồi đã cho là a = n . , 6n ϵ . n 2 + 3 2
a = a + 4a – 4a
Ví dụ 4. Giải công thức truy hồi n n–1 n–2 n–3
a = –1, a = 0, a = 1 0 1 2 Bài giải
Phương trình đặc trưng r3 – r2 – 4r + 4 = 0 e
r = –2 (đơn), r = 2 (đơn), r = 1 (đơn) 1 2 3
Công thức nghiệm tổng quát có dạng:
a = α.(r )n + β .(r )n + y .(r )n e a = α.(–2)n + β .(2)n + y .(1)n n 1 2 3 n α = – 1 a = –1
–1 = α + β + y 0 12 3
Mà ta có a = 0 , nên ta được 0 = –2α + 2β + y e β = 1 a = 1
1 = 4α + 4β + y 4 2 y = – 5 3
Vậy nghiệm của công thức truy hồi đã cho là a = – 1 .(–2)n + 3 .2n – 5 , 6n ϵ . n 12 4 3
a = 5a – 8a + 4a
Ví dụ 5. Giải công thức truy hồi n n–1 n–2 n–3
a = 3, a = 8, a = 17 0 1 2 Bài giải
Phương trình đặc trưng r3 – 5r2 + 8r – 4 = 0 e r = 1 (đơn), r = 2 (kép) 1 2
Công thức nghiệm tổng quát có dạng:
a = α.(r )n + (β + y n).(r )n e a = α + (β + y n).(2)n n 1 2 n a = 3 3 = α + β α = –3 0
Mà ta có a = 8 , nên ta được 8 = α + 2β + 2y e β = 6 1 a = 17
17 = α + 4β + 8y 1 2 y = – 2 (
Vậy nghiệm của công thức truy hồi đã cho là a = –3 + 6 – n .2n , 6n ϵ . n 2
BÀI TẬP TỰ ĐÁNH GIÁ CHỦ ĐỀ 4.2
1. Giải hệ thức truy hồi P = 1.08 P
, n ≥ 1, P = 50.000 ta được công thức n n–1 0
A. P = (1.08)n 50.000, n ≥ 0
= (50.000)n 1.08, n ≥ 0 n B. Pn
C. P = (1.08)n 50.000 n, n ≥ 0 = 1.08 n 50.000, n ≥ 0 n D. Pn
2. Nghiệm đặc trưng của hệ thức truy hồi a = 3a + 4a
, 6n ≥ 2 với a = 1, a = 6 là n n–1 n–2 0 1
A. r = –1, r = 4
B. r = 1, r = 4 1 2 1 2
C. r = –1, r = –4
D. r = 1, r = –4 1 2 1 2
3. Nghiệm đặc trưng của hệ thức truy hồi a = 4a
– 4a , 6n ≥ 2 với a = 1, a = 6 là n n–1 n–2 0 1 A. r = 2
B. r = 1, r = 4 1 2
C. r = 4, r = –4
D. r = 1, r = –4 1 2 1 2
4. Nghiệm đặc trưng của hệ thức truy hồi a = 2a
+ a – 2a , 6n ≥ 3 với n n–1 n–2 n–3
a = 2, a = 5, a = 15 là 0 1 2
A. r = 2, r = 1, r = –1
B. r = 1, r = 2, r = –2 1 2 3 1 2 3
C. r = 1, r = 2
D. r = 1, r = –2 1 2 1 2 Đáp án: 1.A, 2.A, 3.A, 4.A
Bài tập làm thêm phần giải hệ thức truy hồi
a = 5a – 6a
1. Giải công thức truy hồi n+1 n n–1 a = 1, a = 0 0 1 a = 4a – 4a
2. Giải công thức truy hồi n+2 n+1 n a = 6, a = 8 1 2 a = 3a – 4a
3. Giải công thức truy hồi n n–1 n–3
a = 2, a = 5, a = 21 0 1 2
a – 6a + 11a – 6a = 0
4. Giải công thức truy hồi n+3 n+2 n+1 n
a = 1, a = 5, a = 8 0 1 2
a – 3a + 3a – a = 0
5. Giải công thức truy hồi n+3 n+2 n+1 n
a = 3, a = 2, a = 8 0 1 2
a – 7a + 11a – 5a = 0
6. Giải công thức truy hồi n n–1 n–2 n–3
a = 0, a = 1, a = 3 0 1 2 Đáp số
1. a = 3.2n – 2.3n
2. a = (4 – n).2n
3. a = (–1)n + (1 + 2n).2n n n n
4. a = – 11 + 9.2n – 5 .3n
5. a = 7 n2 – 9 .n + 3
6. a = – 1 + 3 .n + 1 .5n n 2 2 n 2 2 n 16 4 16
Document Outline
- Chủ đề 4.1. Các khái niệm
- Giải.
- Giải. (1)
- 4.1.2. Nghiệm của hệ thức truyhồi
- Ví dụ.
- 4.1.3. Giải toán bằng mô hình hệ thức truy hồi.
- Giải
- Giải (1)
- BÀI TẬP TỰ ĐÁNH GIÁ CHỦ ĐỀ 4.1
- Ví dụ
- Phân loại hệ thức truy hồi.
- 4.2.2. Hệ thức truy hồi tuyến tính thuần nhất.
- Ví dụ (1)
- 4.2.3. Giải hệ thức truy hồi tuyến tính thuần nhất
- a. Hệ thức truy hồi tuyến tính thuần nhất bậc 2
- Công thức nghiệm
- Giải (2)
- Giải (3)
- Công thức nghiệm (1)
- c. Hệ thức truy hồi tuyến tính thuần nhất bậc cao
- Giải (4)
- MỘT SỐ VÍ DỤ VỀ GIẢI HỆ THỨC TRUY HỒI
- Bài giải
- Bài giải (1)
- Bài giải (2)
- Bài giải (3)
- Bài giải (4)
- BÀI TẬP TỰ ĐÁNH GIÁ CHỦ ĐỀ 4.2
- Đáp án: 1.A, 2.A, 3.A, 4.A
- Đáp số