Toán rời rạc P4

Phần IV
Hệ thức đệ quy

Biên soạn:
TS.Nguyễn Viết Đông

1
Tài liệu tham khảo
[1] TS. Trần Ngọc Hội, Toán rời rạc
[2] GS.TS. Nguyễn Hữu Anh, Toán rời rạc, Nhà xuất bản giáo dục.
[3] Nguyễn Viết Hưng’s Slides
2
Định nghĩa
Một hệ thức đệ qui tuyến tính cấp k là một
hệ thức có dạng:
xn = a1xn-1 +. + akxn-k + fn (1)

trong đó :
ak ? 0, a1,., ak-1 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.
3
Định nghĩa
Trường hợp dãy fn= 0 với mọi n thì (1) trở
thành:
xn = a1xn-1 +. +akxn-k (2)

Ta nói (2) là một hệ thức đệ qui tuyến tính
thuần nhất cấp k
4
Nghiệm tổng quát
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ở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 của (1) nếu mọi dãy của họ này đều là nghiệm của (1)
5
Nghiệm riêng
Cho {xn} là nghiệm tổng quát của (1) và vôùi moïi k
giaù trò ban ñaàu y0, y1,…, yk-1, toàn taïi duy nhaát caùc
giaù trò cuûa k tham soá C1, C2,…,Ck sao cho nghieäm
{xn} töông öùng thoûa:
x0 = y0, x1 = y1,…, xk-1 = yk-1 (*)
Khi ñoù, nghieäm {xn} töông öùng ñöôïc goïi nghieäm rieâng öùng vôùi ñieàu kieän ban ñaàu (*).
6
Mục đích giải hệ thức đệ qui

Giải một hệ thức đệ qui là đi tìm nghiệm tổng quát của nó.

Nếu hệ thức đệ qui có kèm theo điều kiện ban đầu, ta phải tìm nghiệm riêng thỏa điều kiện ban đầu đó.
7
Fibonacci (1170-1250)
8
Một số ví dụ
Ví dụ 1(Dãy Fibonacci)
Bài toán:Một đôi thỏ(gồm một thỏ đực và một thỏ cái)cứ mỗi tháng đẻ được một đôi thỏ con(cũng gồm một đực và một cái),mỗi đôi thỏ con, khi tròn hai tháng tuổi, lại mỗi tháng đẻ ra một đôi thỏ con và quá trình sinh nở cứ thế tiếp diễn.Tính Fn là số đôi thỏ có ở tháng n?
9
Một số ví dụ
Giải:
Tháng đầu tiên và tháng thứ 2 chỉ có mộtđôithỏ.Sang
tháng thứ 3 đôi thỏ này sẽ đẻ ra một đôi thỏ, vì thế
tháng này sẽ có hai đôi thỏ .Với n3 ta có
Fn = Fn-1+Số đôi thỏ được sinh ra ở tháng thứ n.
Do các đôi thỏ được sinh ra ở tháng thứ n-1 chưa
đẻ con ở tháng thứ n , và ở tháng này mỗi đôi thỏ
có ở tháng n-2 sẽ đẻ ra được một đôi thỏ con nên số
đội thỏ được sinh ra ở tháng thứ n chính bằng Fn-2
10
Một số ví dụ
Như vậy việc giải bài toán Fobonacci dẫn ta
tới việc khảo sát dãy số (Fn), xác định bởi
F1 = 1
F2 =1
Fn = Fn-1+Fn-2 với n >2.
11
Một số ví dụ
Ví d?2: Một cầu thang có n bậc. Mỗi bước đi gồm 1 hoặc 2 bậc. Gọi xn là số cách đi hết cầu thang. Tìm một hệ thức đệ qui cho xn
12
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ẫn nhau:
Trường hợp 1: 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 trong trường hợp này là xn-1.
Một số ví dụ
13
Ví dụ
Trường hợp 2: 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 trong trường hợp này 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-2


14
Vậy ta có hệ thức đệ qui tuyến tính thuần nhất cấp 2:
Một số ví dụ
15
Example3: The tower of Hanoi puzzle consists of three pegs mounted on a board and disks with different sizes.
How can we move the disks to the 2nd peg, following the rule: larger disks are never placed on top of smaller ones?
16
How can we move the disks to the 2nd peg, one in a time,following the rule: larger disks are never placed on top of smaller ones?
17
Let Hn be the minimum number of moves to complete the puzzle. First we must move the top (n – 1) disks to the 3rd peg, using at least Hn – 1 moves
18
We need one more move to take the largest disk to peg 2
Then carry (n – 1) smaller disks from 3rd peg to the 2nd peg, using at least Hn – 1 moves .
19
one more move to take the largest disk to peg 2
carry (n – 1) smaller disks from 3rd peg to the 2nd peg, using at least Hn – 1 moves .
Thus Hn = 2Hn – 1 + 1
In fact we can prove by induction that
Hn = 2 Hn – 1 + 1
First, move the top (n – 1) disks to the 3rd peg, using at least Hn – 1 moves
Modeling with Recurrence Relations
20
Hn = 2 Hn – 1 + 1
We can prove by induction that
To solve this recurrence relation, we write
Hn + 1 = 2 Hn – 1 + 2 = 2(Hn – 1+ 1)
This is a geometric progression, so the solution is:
Hn + 1 = C 2n
Since H1 = 1, we have C = 1 and
Hn = 2n – 1
E.g. H64 = 18,446,744,073,709,551,615:
It takes 500 billion years to solve the puzzle !!
21
Xét hệ thức đệ qui tuyến tính thuần nhất
xn = a1xn-1 +. + akxn-k (2)
Hệ thức đệ qui tuyến tính thuần nhất
Phương trình đặc trưng của (2) là phương trình bậc k định bởi:
?k - a1?k-1 -. - ak = 0 (*)
22
Hệ thức đệ qui tuyến tính thuần nhất
Trường hợp k = 1
Phương trình đặc trưng (*) trở thành
? - a1 = 0
nên có nghiệm là ?0 = a1
Khi đó, (2) có nghiệm tổng quát là:
23
Hệ thức đệ qui tuyến tính thuần nhất
Ví dụ: Hệ thức đệ qui
là một hệ thức đệ qui tuyến tính thuần nhất cấp 1
24
Hệ thức đệ qui tuyến tính thuần nhất
Phương trình đặc trưng: 2? - 3 = 0 có nghiệm là ?0 = 3/2
Do đó nghiệm tổng quát là:
25
Hệ thức đệ qui tuyến tính thuần nhất
Từ điều kiện ban đầu x1 = 1, ta có :
Suy ra:
Do đó nghiệm của hệ thức đệ qui đã cho là:
26
Hệ thức đệ qui tuyến tính thuần nhất
Trường hợp k = 2:
Phương trình đặc trưng (*) trở thành:

?2 - a1? - a2 = 0 (*)
a) Nếu (*) có hai nghiệm thực phân biệt ?1 và ?2 thì (2) có nghiệm tổng quát là:
27
Hệ thức đệ qui tuyến tính thuần nhất
b) Nếu (*) có nghiệm kép thực ?0 thì (2) có nghiệm tổng quát là:
28
Hệ thức đệ qui tuyến tính thuần nhất
c) Nếu (*) có hai nghiệm phức liên hợp được viết dưới dạng lượng giác :
thì (2) có nghiệm tổng quát là:
29
Ví dụ:
Ví dụ 1
Ví dụ 2
Ví dụ 3
Giải các hệ thức đệ qui sau:
30
Một số ví dụ
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à:
xn = A + B(1/2)n
31
Một số ví dụ
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à:
xn = (A + nB)(3/2)n
32
Một số ví dụ
Từ điều kiện ban đầu x0 = 2; x1 = 4 ta suy ra:
Suy raA = 2 và B = 2/3
Vậy nghiệm của (2) là:
xn = (3 + n)(3/2)n-1
33
Một số ví dụ
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à
Ta viết hai nghiệm trên dưới dạng lượng giác:
34
Do đó nghiệm tổng quát của (3) là
Từ điều kiện ban đầu x1 = 4; x2 = 4 ta suy ra:
Suy ra:
Vậy nghiệm của (3) là :
35

36
Hệ thức đệ qui tuyến tính không thuần nhất
Xét hệ thức đệ qui tuyến tính không thuần nhất
xn = a1xn-1 +… + akxn-k + fn (1)
Hệ thức đệ qui tuyến tính thuần nhất tương ứng là:
xn = a1xn-1 +… + akxn-k (2)
Phương trình đặc trưng của (2) là:
k - a1k-1 -… - ak = 0 (*)
37
Hệ thức đệ qui 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)
+
38
Hệ thức đệ qui tuyến tính không thuần nhất
Cách tìm một nghiệm riêng của (1) khi vế phải 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 da 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
39
Hệ thức đệ qui tuyến tính không thuần nhất
Khi đó ta xét 3 trường hợp nhỏ:
Trường hợp 1  khoâng laø nghieäm cuûa phöông trình ñaëc tröng :
Trường hợp 2  laø nghieäm đơn cuûa phöông trình ñaëc tröng :
Trường hợp 3  laø nghieäm kep cuûa phöông trình ñaëc tröng :
40
D?ng 1: fn = ?nPr(n),
Hệ thức đệ qui tuyến tính không thuần nhất
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)
41
Trường hợp 1.
Hệ thức đệ qui tuyến tính không thuần nhất
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)
42
Trường hợp 2.
Hệ thức đệ qui tuyến tính không thuần nhất
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)
43
Trường hợp 3.
Hệ thức đệ qui tuyến tính không thuần nhất
Chú ý:
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.
Các hệ số xác định như thế nào ?
Để 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
44
Hệ thức đệ qui tuyến tính không thuần nhất
D?ng 2: fn = Pm(n)cosn? + Ql(n)sinn?
Khi đó ta xét ?0 = cos??? isin?. Có 2 trường hợp nhỏ:
Trường hợp 1 0 = cos  isin khoâng laø nghieäm cuûa phöông trình ñaëc tröng
Trường hợp 2 0 = cos  isin laø nghieäm cuûa phöông trình ñaëc tröng
45
Hệ thức đệ qui tuyến tính không thuần nhất
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:
xn = Rk(n)cosn + Sk(n)sinn
46
Trường hợp 1.
Hệ thức đệ qui tuyến tính không thuần nhất
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:
xn = n(Rk(n)cosn + Sk(n)sinn)
47
Trường hợp 2.
Hệ thức đệ qui tuyến tính không thuần nhất
Ghi 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
48
Hệ thức đệ qui tuyến tính không thuần nhất
D?ng 3 : 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 đệ qui:
a0xn + a1xn-1 +… + akxn-k = fni
Khi đó xn = xn1 + xn2+.+ xns là một nghiệm riêng của (1)
49
Ví dụ:
a)
b)
c)
d)
e)
50
(1)
Ví Dụ 1
Hệ thức đệ qui tuyến tính thuần nhất là:
(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à:
xn = C1 + C2(1/2)n
51
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à đa thức bậc r = 1 theo 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)
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ệ:
52
Giải hệ trên ta được a = 2; b = -1. Thế vào (4) ta 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à:
xn = C1 + C2(1/2)n + n(2n - 1)
53

54
Ví Dụ 2
55
56
57
Ví Dụ 3
Xét hệ thức đệ qui:
Hệ thức đệ qui tuyến tính thuần nhất là:
Phương trình đặc trưng của (2) là:
42 - 12 + 9 = 0 (*)
có một nghiệm thực kép là ? = 3/2.
Do đó nghiệm tổng quát của (2) là
xn = (C1 + nC2)(3/2)n. (3)
58
Bây giờ ta tìm một nghiệm riêng của (1).
Vế phải c?a (1) là
có dạng ?nPr(n) với ? = 2 và Pr(n) là đa thức bậc r = 2 theo n.
Vì ? = 2 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 = (an2 + bn + c)2n (4)
Thế (4) vào (1) ta được :
4[a(n+1)2 + b(n+1) + c)2n+1 -12[an2 + bn + c] 2n + 9[a(n-1)2 + b(n-1) + c] 2n-1 = (2n2 + 29n +56)2n-1
59
Cho n lần lượt nhận ba giá trị n = -1; n = 0; n = 1 ta được hệ:
Giải hệ trên ta được a = 2; b = 1; c = -1. Thế vào (4) ta tìm được một nghiệm riêng của (1) là
xn = (2n2 + n - 1)2n (5)
60
Từ (3) và (5) ta suy ra nghiệm tổng quát của (1) là:
xn = (C1 + nC2)(3/2)n + (2n2+ n -1) 2n (6)
Thay điều kiện x0 = 1; x1 = -2 vào (6) ta được:
Từ đó ta có:
C1= 2; C2 = - 6.
Thế vào (6) ta có nghiệm riêng cần tìm của (1) là:
xn = (2 - 6n)(3/2)n + (2n2+ n -1) 2n
61
Ví Dụ 4
Hệ thức đệ qui tuyến tính thuần nhất là:
Phương trình đặc trưng của (2) là:
2 - 3 + 2 = 0 (*)
có hai nghiệm thực phân biệt là ?1 = 1; ?2 = 2.
Do đó nghiệm tổng quát của (2) là:
xn = C1 + C2.2n. (3)
62
Bây giờ ta tìm một nghiệm riêng của (1).
Vế phải c?a (1) là
có dạng ?cosn? + ?sinn? với ? = ?/4
Vì
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:
63
Thế (4) vào (1) ta được:
Cho n lần lượt nhận hai giá trị n = 0; n = -1; ta được hệ:
Giải hệ trên ta được a = 1; b = -1. Thế vào (4) ta tìm được một nghiệm riêng của (1) là
64
Từ (3) và (5) ta suy ra nghiệm tổng quát của (1) là:
65
Ví Dụ 5
Hệ thức đệ qui tuyến tính thuần nhất là:
Phương trình đặc trưng của (2) là:
2 - 4 + 3 = 0 (*)
có hai nghiệm thực phân biệt là ?1 = 1; ?2 = 3.
Do đó nghiệm tổng quát của (2) là:
xn = C1 + C2. 3n. (3)
66
Bây giờ ta tìm một nghiệm riêng của (1).
Vế phải c?a (1) là
có dạng ở Trường hợp 4.
Xét các hệ thức đệ qui:
67
Lý luận tượng tự như trên ta tìm được:
Một nghiệm riêng của (1`) là xn1 = -10n
Một nghiệm riêng của (1``) là xn2 = n2n
Một nghiệm riêng của (1```) là xn3 = 4n+2
Suy ra một nghiệm riêng của (1) là:
xn1 = -10n + n2n + 4n+2 (4)
Từ (3) và (4) ta suy ra nghiệm tổng quát của (1) là:
xn = C1 + C2.3n - 10n + n2n + 4n+2
68
Vídụ(Bài 4 Đề thi2007)

a) Tìm nghiệm tổng quát của hệ thức đệ qui:
an = an- 1 + 6 an-2
b) Tìm nghiệm thỏa điều kiện đầu a 0 = 1, a1 = 5 của hệ thức đệ qui:
an = a n – 1 + 6 a n – 2 + 50n 3 n – 1
69
Đáp án: 1,5đ
a) Phương trình đặc trưng r 2 – r – 6 = 0 có 2 nghiệm r 1 = 3, r2 = –2 nên nghiệm tổng quát có dạng: an = c 3n + d (–2)n (0,5đ)
b) Ta tìm nghiệm đặc biệt có dạng n(An+B)3n :
(An2 +Bn) 3n = (A(n–1)2 + B(n–1)) 3n -1 + 6 (A(n–2)2 + B(n–2)) 3n - 2 + 50n 3n-1
10An – 50 n + 5B – 9A = 0 hay A = 5 , B = 9 (0,5đ)
Do đó nghiệm tổng quát có dạng: an = c 3n + d (–2) n + (5n2 + 9n) 3n
Các điều kiện ban đầu cho:
a 0 = c + d = 1,
a1 = 3c – 2 d + 42 = 5
giải hệ phương trình trên ta được c = –7, d = 8 (0,5đ)
70
Vídụ(Đềthi2006). Cho X= . Mỗi chuỗi ký tự có dạng a1a2...an với a1, a2,..,an  X (n nguyên dương)được gọi là một từ có chiều dài n trên X. Gọi Ln là số các từ có chiều dài n trên X không chứa 2 số 2 liên tiếp.
a) Tìm một công thức truy hồi cho Ln.
b)Tìm biểu thức của Ln theo n.
71
Đápán. (2 điểm)
a)1 điểm
_ Số các từ có chiều dài n mà a1 = 0 là Ln-1
_ Số các từ có chiều dài n mà a1 = 1 là Ln-1
_ Số các từ có chiều dài n mà a1 = 2 :
+ Có Ln-2 từ mà a2 = 0
+ Có Ln-2 từ mà a2 = 1
Vậy Ln = 2Ln-1 + 2Ln-2 (n > 3)
b)1 điểm
Các từ có chiều dài 1 là : 0,1,2. L1 = 3;
Các từ có chiều dài 2 là : 00,01,02,10,11,12,20,21 . L2 = 8;
Ta quy ước L0 = 1 thì hệ thức đệ quy thoả với n >1
Phương trình đặc trưng
72
Nghiệm tổng quát :
73
Ví dụ (Đềthi2006).
a)Tìm nghiệm tổng quát của hệ thức đệ qui :
an= 4an-1- 4 an-2
b)Tìm nghiệm của hệ thức đệ qui:
an= 4an-1- 4 an-2+3. 2n+1
thoả điều kiện đầu:a0=4,a1=4
74
Đáp án
a) Phương trình đặc trưng x2-4x+4 = 0 có nghiệm kép x = 2nên nghiệm tổng quát có dạng
an = (A+nB) 2n (0,5đ)
b) Vì β=2 là nghiệm kép của phương trình đặc trưng nên ta tìm nghiệm riêng dưới dạng Cn22n.
Ta có Cn22n =4C(n-1)22n-1-4C(n-2)22n-2+3.2n+1
 C = 3 (0,5đ)
75
Do đó nghiệm tổng quát có dạng
an =A 2n +Bn2n +3n22n
Sử dụng ĐKĐ
a0 = A = 4
a1 =2A+2B +6 = 4 .Nên B = -5
76

Đềthi 2006
Cho X={0,1,2}.Gọi an là số các từ có chiều dài n trên X trong đó số 1 không xuất hiện liên tiếp và số 2 không xuất hiện liên tiếp.
Chứng minh rằng an thoả hệ thức đệ qui:
an= 2an-1+an-2 với n>2.
b)Tìm biểu thức của an theo n.
77
Đềthi 2006
Đáp án (2,5 điểm)
a)1 điểm
Gọi bn,cn,dn lần lượt là số từ x1x2…xn ứng với
x1= 0,x1=1,x1=2.
Ta có bn = an-1 ; cn = bn-1 +dn-1 ;dn= bn-1+cn-1
Do đó an = bn + cn +dn = an-1 +bn-1+dn-1+bn-1+cn-1
= an-1+an-2+(dn-1+bn-1+cn-1) = an-1+an-2+an-1
= 2an-1+an-2

78
Đềthi 2006
b)1,5 điểm.
Các từ có chiều dài 1 là 0,1,2 nên a1 =3.
Các từ có chiều dài 2 thoả yêu cầu là: 00,01,02,10,12,20,21 nên a2 =7.Ta qui ước a0=1thì hệ thức đệ qui thoả với n >1. Phương trình đặc trưng x2 – 2x – 1 = 0 có hai nghiệm là
79
Đềthi 2006

Do đó nghiệm tổng quát là
Trong đó A và B xác định bởi

80
Đềthi 2006
Suy ra
81
Đề thi 2008
Tìm số các chuỗi ký tự chiều dài n chứa chuỗi con 11 hay 22, trong đó các ký tự được chọn trong {0, 1, 2}.
Cách giải 1.(Phương pháp đối lập).
Gọi an là số chuỗi không chứa chuỗi con 11 và 22. Giải như đề 2006 ta được
82
Đề thi 2008
Như vậy số chuỗi chứa chuỗi con 11 hoặc 22 là

Cách giải 2 (Trực tiếp)
Gọi bn,cn,dn lần lượt là số từ x1x2…xn ứng
với x1= 0,x1=1,x1=2. Khi đó:
an = bn +cn +dn .
bn = an-1 .
cn = bn-1 + 3n-2 +dn-1(vì khi ký tự thứ 2 là 1 thì
kết hợp với mọi chuỗi n- 2 ký tự phía sau đều thỏa).
83
Đề thi 2008
Tương tự :
dn = bn-1 +cn-1+3n-2 . Do đó:
an = an-1 +bn-1 +3n-2 +dn-1 + bn-1 +cn-1 +3n-2
= an-1+2.3n-2 +an-1 +an-2= 2 .an-1+an-2 +2.3n-2.
Vậy ta có hệ thức đệ qui tuyến tính không thuần
nhất
an = 2.an-1 + an-2 + 2.3n-2.
với a0 = 0 và a1 = 0.Giải hệ thức đệ qui này ta có kết
quả như cách 1.
84
Đề thi 2005
Tìm nghiệm tổng quát của hệ thức đệ qui:
an = 6an-1 – 9an-2
b) Tìm nghiệm của hệ thức đệ qui:
an = 6an-1 – 9an-2+2. 4n
thoả điều kiện đầu a0 =12, a1=8
85
Đề thi 2005
Một người gửi 100 triệu đồng vào một quĩ đầu tư vào ngày đầu của một năm . Ngày cuối cùng của năm người đó được hưởng hai khoản tiền lãi. Khoản thứ nhất là 20% tổng số tiền có trong tài khoản cả năm, khoản lãi thứ hai là 45% của tổng số tiền có trong tài khoản của năm trước đó.Gọi Pnlà số tiền có trong tài khoản vào cuối năm thứ n.
Tìm công thức truy hồi cho Pn
Tìm biểu thức của Pntheo n.
86
Đề thi 2004
Một bãi giữ xe được chia thành n lô cạnh nhau theo hàng ngang để xếp xe đạp và xe máy. Mỗi xe đạp chiếm một lô còn mỗi xe máy chiếm hai lô. Gọi Ln là số cách xếp cho đầy n lô.
a)Tìm một công thức đệ qui thoả bởi Ln
b) Tìm biểu thức của Ln theo n.
87
Bài tập về nhà
Giải các hệ thức đệ qui sau:
1)
2)
3)
88
Bài tập về nhà
Giải các hệ thức đệ qui sau:
4)
5)
6)
89
Bài tập về nhà
Giải các hệ thức đệ qui sau:
9)
7)
8)
90
Bài tập về nhà
10) Tìm hệ thức đệ qui cho xn, trong đó xn
là số miền của mặt phẳng bị phân chia bởi
n đường thẳng trong đó không có hai đường
nào song song và không có ba đường nào
đồng qui. Tìm xn .
11) D? thi 2009.
Tìm nghi?m t?ng qu�t c?a h? th?c d? qui:
an = 6an-2 - 9 an-1.
b) Tìm nghi?m th?a di?u ki?n d?u a0 = 1, a1 = 3 c?a
h? th?c d? qui:
an = 6an-2 - 9an-1 + n.3n+1
91