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
Moät heä thöùc ñeä qui tuyeán tính caáp k laø moät
heä thöùc coù daïng:
xn = a1xn1 +… + akxnk + fn
(1)
trong ñoù :
•
ak (cid:0)
0, a1,…, ak-1 laø caùc heä soá
thöïc
•
{fn} laø moät daõy soá thöïc cho
tröôùc
•
{xn} laø daõy aån nhaän caùc giaù trò
thöïc.
3
ị
Đ nh nghĩa
Tröôøng hôïp daõy fn= 0 vôùi moïi n thì (1) trôû thaønh:
xn = a1xn-1 +… +akxn-k (2)
Ta noùi (2) laø moät heä thöùc ñeä qui tuyeán tính thuaàn nhaát caáp k
4
ệ
ổ Nghi m t ng quát
Ø Moãi daõy {xn} thoûa (1) ñöôïc goïi laø moät nghieäm cuûa (1). • Nhaän xeùt raèng moãi nghieäm {xn} cuûa (1) ñöôïc hoaøn toaøn xaùc ñònh bôûi k giaù trò ban ñaàu x0, x1,…, xk-1.
Ø Hoï daõy soá { xn = xn(C1, C2, …,Ck)} phuï thuoäc vaøo k hoï tham soá C1, C2,…,Ck ñöôïc goïi laø nghieäm toång quaùt cuûa (1) neáu moïi daõy cuûa hoï naøy 5 ñeàu laø nghieäm cuûa (1)
ệ
Nghi m riêng
ổ
ệ
ủ
vôùi
Cho {xn} là nghi m t ng quát c a (1) và 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
•
Giaûi moät heä thöùc ñeä qui laø ñi tìm nghieäm toång quaùt cuûa noù.
•
Neáu heä thöùc ñeä qui coù keøm theo ñieàu kieän ban ñaàu, ta phaûi tìm nghieäm rieâng thoûa ñieàu kieän ban ñaàu ñoù. 7
Fibonacci (11701250)
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à ộ ẻ ượ ứ ỗ c m t đôi m t th cái)c m i tháng đ đ ỗ ộ ộ ự ồ th con(cũng g m m t đ c và m t cái), m i ỗ ổ ạ i m i đôi th con, khi tròn hai tháng tu i, l ỏ 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
i:ả
ỉ
ứ
ộ
ỏ
ộ
ỏ
ẽ ẻ
ở
ỏ
ứ tháng th n. ư ứ ở tháng th n1 ch a tháng này m i đôi th
ỏ ượ c sinh ra ở ượ
ộ
ỗ ỏ c m t đôi th con nên
ỏ ượ
ứ
ằ
ở
c sinh ra
tháng th n chính b ng Fn
Gi ầ 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ế ỏ ớ (cid:0) 3 ta có ẽ tháng này s có hai đôi th .V i n ố c sinh ra Fn = Fn1+S đôi th đ ỏ ượ Do các đôi th đ ứ ở ẻ đ con tháng th n , và ẽ ẻ ở tháng n2 s đ ra đ có số ộ đ i th đ 2
10
ụ
ộ ố M t s ví d
ả
i bài toán Fobonacci d n ta
ệ ả
ị
ớ
ư ậ ẫ Nh v y vi c gi ở ố ệ ớ i vi c kh o sát dãy s (Fn), xác đ nh b i t F1 = 1 F2 =1 Fn = Fn1+Fn2 v i n >2.
11
ụ
ộ ố M t s ví d
Ví d 2: ụ Moät caàu thang coù n baäc. Moãi böôùc ñi goàm 1 hoaëc 2 baäc. Goïi xn laø soá caùch ñi heát caàu thang. Tìm moät heä thöùc ñeä qui cho xn
12
ụ
ộ ố M t s ví d
Vôùi n = 1, ta coù x1 = 1.
Vôùi n = 2, ta coù x2 = 2
Vôùi n > 2, ñeå khaûo saùt xn ta chia thaønh hai tröôøng hôïp loaïi tröø laãn nhau: Tröôøng hôïp 1: Böôùc ñaàu tieân goàm 1 baäc. Khi ñoù, caàu thang coøn n-1 baäc neân soá caùch ñi heát caàu thang trong tröôøng hôïp naøy laø xn-1.
13
Ví dụ
Tröôøng hôïp 2: Böôùc ñaàu tieân goàm 2 baäc. Khi ñoù, caàu thang coøn n-2 baäc neân soá caùch ñi heát caàu thang trong tröôøng hôïp naøy laø xn-2. Theo nguyeân lyù coäng, soá caùch ñi heát caàu thang laø xn-1 + xn-2 . Do ñoù ta coù:
xn = xn-1 + xn-2
14
ụ
ộ ố M t s ví d
Vaäy ta coù heä thöùc ñeä qui tuyeán tính thuaàn nhaát caáp 2:
=
+
2
(cid:0) - -
=
=
(cid:0)
x n 2.
x n x 1
x n 1 x 21,
(cid:0)
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
n 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
Modeling with Recurrence Relations
n First, move the top (n – 1) disks to the 3rd peg, using at
least Hn – 1 moves
n one more move to take the largest disk to peg 2 n carry (n – 1) smaller disks from 3rd peg to the 2nd
peg, using at least Hn – 1 moves .
Hn = 2Hn – 1 + 1
Thus n In fact we can prove by induction that
Hn = 2 Hn – 1 + 1
20
n We can prove by induction that
Hn = 2 Hn – 1 + 1
n To solve this recurrence relation, we write
Hn + 1 = 2 Hn – 1 + 2 = 2(Hn – 1+ 1)
n 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
ế
ệ ứ ệ
ầ
H th c đ qui tuy n tính thu n nh tấ Xeùt heä thöùc ñeä qui tuyeán tính thuaàn nhaát
xn = a1xn-1 +… + akxn-k
(*)
(2) Phöông trình ñaëc tröng cuûa (2) laø phöông trình baäc k ñònh bôûi: (cid:0) k - a1(cid:0) 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 ñaëc tröng (*) trôû
thaønh
(cid:0) - a1 = 0
neân coù nghieäm laø (cid:0) 0 = a1 Khi ñoù, (2) coù nghieäm toång quaùt laø:
Cl=
nx
n 0
23
ệ ứ ệ
ế
ầ
H th c đ qui tuy n tính thu n nh tấ
ụ ệ ứ ệ Ví d : H th c đ qui
3
0;
2
x n
= 1
- (cid:0) -
x n =
(cid:0)
1.
x 1
laø moät heä thöùc ñeä qui tuyeán tính thuaàn nhaát caáp 1
(cid:0)
24
ế
ệ ứ ệ
ầ
H th c đ qui tuy n tính thu n nh tấ Phöông trình ñaëc tröng: 2(cid:0) - 3 = 0 coù nghieäm laø (cid:0) 0 = 3/2
Do ñoù nghieäm toång quaùt laø:
nx
n 3 � � = � � C 2 � �
25
ệ ứ ệ
ế
ầ
H th c đ qui tuy n tính thu n nh tấ
Töø ñieàu kieän ban ñaàu x1 = 1, ta coù :
1
C =
Suy ra:
n
1
3 C * = 2 2 3 Do ñoù nghieäm cuûa heä thöùc ñeä qui ñaõ cho laø: 3 � �= � � nx 2 � �
-
26
ệ ứ ệ
ế
ầ
H th c đ qui tuy n tính thu n nh tấ Tröôøng hôïp k = 2:
Phöông trình ñaëc tröng (*) trôû
thaønh:
(cid:0) 2 - a1(cid:0) - a2 = 0
(*)
=
+
a) Neáu (*) coù hai nghieäm thöïc phaân bieät (cid:0) 1 vaø (cid:0) 2 thì (2) coù nghieäm toång quaùt laø: l A
l B
nx
n 1
n 2
27
ệ ứ ệ
ế
ầ
H th c đ qui tuy n tính thu n nh tấ
b) Neáu (*) coù nghieäm keùp thöïc (cid:0) 0 thì (2) coù nghieäm toång quaùt laø:
=
+ A nB l
(
nx
) n 0
28
ầ
ế
ệ ứ ệ
=
l
i
H th c đ qui tuy n tính thu n nh tấ c) Neáu (*) coù hai nghieäm phöùc lieân hôïp ñöôïc vieát döôùi daïng löôïng giaùc : j r (cos
j sin )
+
thì (2) coù nghieäm toång quaùt laø: = n r A
j n
B
( cos
j n sin
)
nx
(cid:0)
29
Ví d :ụ
0
2
3
x n
x n
x n
= 2
+ 1
Giaûi caùc heä thöùc ñeä qui sau: Ví d 1ụ
- - -
4
12
9
0;
x n
= 1
Ví d 2ụ
- (cid:0) -
+ x n =
(cid:0)
x + n 1 = 2;
4.
x 0
x 1
(cid:0)
2
4
0;
x n
= x n
- (cid:0)
Ví d 3ụ
+ 2 =
+ + 1 =
(cid:0)
4;
4.
x n x 1
x 2
(cid:0) 30
ụ
ộ ố M t s ví d
2
3
) ( 0 1
x n
x n
x n
+ 1
= 2
Phöông trình ñaëc tröng cuûa (1) laø: 2(cid:0) 2 3(cid:0)
(*)
+ 1 = 0 coù hai nghieäm thöïc laø (cid:0) 1 = 1 vaø (cid:0) 2 = 1/2. Do ñoù nghieäm toång quaùt cuûa (1) laø: xn = A + B(1/2)n
- - -
31
ụ
ộ ố M t s ví d
4
12
9
0
x n
= 1
(
)
- (cid:0) -
2
+ x n =
(cid:0)
x + n 1 = 2;
4.
x 0
x 1
Phöông trình ñaëc tröng cuûa (2) laø:
4(cid:0) 2 12(cid:0)
+ 9 = 0
(cid:0)
coù nghieäm thöïc keùp laø (cid:0) 0 = 3/2. Do ñoù nghieäm toång quaùt cuûa (2) laø:
xn = (A + nB)(3/2)n
32
ụ
ộ ố M t s ví d
Töø ñieàu kieän ban ñaàu x0 = 2; x1 = 4 ta suy ra: = A
2
(cid:0)
(cid:0)
=
+ A B
)
(
4
(cid:0)
3 2
Suy raA = 2 vaø B = 2/3
Vaäy nghieäm cuûa (2) laø:
xn = (3 + n)(3/2)n1
(cid:0) (cid:0)
33
ụ
ộ ố M t s ví d
2
0
4
= x n
x n
(
)
- (cid:0)
3
+ + 1 =
+ 2 =
(cid:0)
4
4;
x 2
x n x 1 Phöông trình ñaëc tröng cuûa (3) laø: (cid:0) 2 2(cid:0)
+ 4 = 0
3i
(*) l = (cid:0) 1
coù hai nghieäm phöùc lieân hôïp laø Ta vieát hai nghieäm treân döôùi daïng p löôïng giaùc: l =
(cid:0)
i
2(cos
3
p sin ) 3
(cid:0)
34
+
C
n 2 (
cos
sin
)
C 1
2
p n 3
Do ñoù nghieäm toång quaùt cuûa (3) laø p n = x n 3 Töø ñieàu kieän ban ñaàu x1 = 4; x2 = 4 ta suy ra:
+
(cid:0)
C
2(
= ) 4
C 1
2
1 2
3 2
=
3
C 1
C= 21,
(cid:0) (cid:0) Suy ra: (cid:0)
C
4(
= ) 4
+ C 1
2
1 2
3 2
n
(cid:0) - (cid:0) (cid:0)
=
+
2 (cos
3 sin
)
x n
p n 3
p n 3
ủ ệ ậ V y nghi m c a (3) là :
35
36
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t
Xeùt heä thöùc ñeä qui tuyeán tính khoâng thuaàn nhaát
xn = a1xn1 +… + akxnk + fn (1)
Heä thöùc ñeä qui tuyeán tính thuaàn nhaát töông öùng laø:
xn = a1xn1 +… + akxnk (2)
Phöông trình ñaëc tröng cuûa (2) laø:
(cid:0) k a1(cid:0) k1 … ak = 0 (*)
37
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t
Nghieäm toång quaùt
Nghieäm toång quaùt cuûa (2)
+
cuûa (1) =
Moät nghieäm rieâng cuûa (1)
38
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t Caùch tìm moät nghieäm rieâng cuûa (1) khi veá phaûi fn cuûa (1) coù daïng ñaëc bieät nhö sau:
k(cid:0) ).
• Dạng 1: fn = (cid:0) nPr(n), trong ñoù Pr(n) laø moät ña thöùc baäc r theo n; (cid:0) laø moät haèng soá • Dạng 2: fn = Pm(n)cosn(cid:0) + Ql(n)sinn(cid:0) , trong ñoù Pm(n), Ql(n) laàn löôït laø caùc đa th cứ baäc m, l theo n; (cid:0) laø haèng soá ((cid:0) (cid:0) • Dạng 3 : fn = fn1 + fn2 +…+ fns ,
trong ñoù caùc fn1, fn2,…, fns thuoäc 2 daïng ñaõ xeùt ôû treân
39
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t
Dạng 1: fn = (cid:0) nPr(n),
Khi ñoù ta xeùt 3 tröôøng hôïp nhoû:
ườ
ợ (cid:0) khoâng laø nghieäm cuûa
ng h p 1
Tr phöông trình ñaëc tröng
ườ
ợ ng h p 2
(cid:0) laø nghieäm đ n ơ cuûa
Tr phöông trình ñaëc tröng
ườ
ợ ng h p 3
(cid:0) laø nghieäm kép cuûa
Tr phöông trình ñaëc tröng
40
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t
ườ
ợ ng h p 1
Tr Neáu (cid:0) khoâng laø nghieäm cuûa phöông trình ñaëc tröng (*) thì (1) coù moät nghieäm rieâng daïng:
.
xn = (cid:0) nQr(n)
41
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t
ợ ườ ng h p 2 Tr . Neáu (cid:0) laø nghieäm ñôn cuûa phöông trình ñaëc tröng (*) thì (1) coù moät nghieäm rieâng daïng:
xn = n(cid:0) nQr(n)
42
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t
ợ ườ ng h p 3. Tr Neáu (cid:0) laø nghieäm keùp cuûa phöông trình ñaëc tröng (*) thì (1) coù moät nghieäm rieâng daïng:
xn = n2(cid:0) nQr(n)
43
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t
Chú ý:
Qr(n) = Arnr + Ar-1nr-1 +…+ A0 laø ña thöùc toång quaùt coù cuøng baäc r vôùi Pr(n), trong ñoù Ar, Ar-1,…, A0 laø r+1 heä soá caàn xaùc ñònh. ệ ố Các h s xác ị đ nh nh th nào ?
ư ế
Ñeå xaùc ñònh caùc heä soá treân ta caàn theá xn, xn-1,…, xn-k vaøo (1) vaø cho n nhaän r + 1 giaù trò nguyeân naøo ñoù hoaëc ñoàng nhaát caùc heä soá töông öùng ôû hai veá ñeå ñöôïc moät heä phöông trình. Caùc heä soá treân laø nghieäm cuûa heä phöông trình naøy
44
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t
Dạng 2: fn = Pm(n)cosn(cid:0) + Ql(n)sinn(cid:0) Khi ñoù ta xeùt (cid:0) 0 = cos(cid:0) isin(cid:0) . Coù 2 tröôøng hôïp nhoû:
(cid:0) (cid:0)
(cid:0)
ườ
isin(cid:0)
ng h p 1
(cid:0)
ườ
isin(cid:0) laø
ng h p 2
45
ợ (cid:0) 0 = cos(cid:0) (cid:0) Tr khoâng laø nghieäm cuûa phöông trình ñaëc tröng ợ (cid:0) 0 = cos(cid:0) (cid:0) Tr nghieäm cuûa phöông trình ñaëc tröng
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t
ườ
Tr
.
isin(cid:0)
ợ ng h p 1 Neáu (cid:0) 0 = cos(cid:0) (cid:0) khoâng laø nghieäm cuûa phöông trình ñaëc tröng (*) thì (1) coù moät nghieäm rieâng daïng: xn = Rk(n)cosn(cid:0)
+ Sk(n)sinn(cid:0)
(cid:0)
46
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t
ườ
Tr
isin(cid:0)
(cid:0)
ợ ng h p 2. Neáu (cid:0) 0 = cos(cid:0) laø nghieäm cuûa phöông trình ñaëc tröng (*) thì (1) coù moät nghieäm rieâng daïng:
xn = n(Rk(n)cosn(cid:0)
+ Sk(n)sinn(cid:0) )
(cid:0)
47
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t
Ghi chú:
Rk(n), Sk(n) laø caùc ña thöùc toång quaùt theo n coù baäc k = max{m,l} vôùi 2k+2 heä soá caàn xaùc ñònh:
Rk(n) = Aknk + Ak1nk1 +…+ A0
Sk(n) = Bknk + Bk1nk1 +…+ B0
48
ệ ứ ệ
ầ
ế H th c đ qui tuy n tính không ấ thu n nh t
i (cid:0)
Dạng 3 : fn = fn1 + fn2 +…+ fns Baèng caùch nhö treân ta tìm ñöôïc nghieäm rieâng xni (1(cid:0) s) cuûa heä thöùc ñeä qui:
a0xn + a1xn1 +… + akxnk = fni
Khi ñoù xn = xn1 + xn2+…+ xns laø moät nghieäm rieâng cuûa (1)
49
Ví d :ụ
a)
- - -
1. + n
+ n 4 (18
n 12)3 ;
+ x 3 n 1 + x 6 n
x n x 9 n
= 2 = 1
(cid:0) - -
b)
+ 1 =
=
(cid:0)
2;
0.
x 2 n x n x 0
x 1
(cid:0)
n
+ 2
n
+ n
4
12
9
(2
29
1 56)2 ;
x n
= 1
- (cid:0) - -
c)
+ x n = -
(cid:0)
x + n 1 = 1;
2.
x 0
x 1
(cid:0)
+
3
2
cos
(3 3 2)sin
x n
x n
= x n
2
+ + 1
d)
p n 4
p n 4
- - -
n
+
+ n 2
n
4
3
20 (2
)2
3.4
x n
x n
x n
+ 1
= 2
e)
- - - - -
50
Ví D 1ụ
(1)
+ n
2
3
4
1
x n
x n
x n
+ 1
= 2
Heä thöùc ñeä qui tuyeán tính thuaàn nhaát laø:
- - -
(2)
2
3
0
x n
x n
x n
+ 1
= 2
Phöông trình ñaëc tröng cuûa (2) laø:
2(cid:0) 2 3(cid:0)
+ 1 = 0
(*)
coù hai nghieäm thöïc laø (cid:0) 1 = 1 vaø (cid:0) 2 = 1/2 Do ñoù nghieäm toång quaùt cuûa (2) laø:
xn = C1 + C2(1/2)n
- - -
51
Baây giôø ta tìm moät nghieäm rieâng cuûa (1). Veá phaûi c a (1) la
ủ ø fn = 4n+1 coù daïng Pr(n) laø ña thöùc baäc r = 1 theo n.
Vì (cid:0) = 1 laø nghieäm ñôn cuûa phöông trình ñaëc tröng (*) neân (1) coù moät nghieäm rieâng daïng:
xn = n(an + b) (4)
Theá (4) vaøo (1) ta ñöôïc:
2n(an+b) 3(n1)[a(n1)+b] + (n2)[a(n2) + b] = 4n + 1.
+ =
Cho n laàn löôït nhaän hai giaù trò n = 0; n = 1 ta ñöôïc heä:
a b
(cid:0)
1; + =
(cid:0)
a b
3
5.
(cid:0) 52
Giaûi heä treân ta ñöôïc a = 2; b = -1. Theá vaøo (4) ta tìm ñöôïc moät nghieäm rieâng cuûa (1) laø:
xn = n(2n 1) (5)
xn = C1 + C2(1/2)n + n(2n 1)
Töø (3) vaø (5) ta suy ra nghieäm toång quaùt cuûa (1) laø:
53
54
Ví D 2ụ
+ n
6
9
(18
n 12)3 ;
+ x n
x n
= 1
(cid:0) - -
+ 1 =
=
(cid:0)
2;
0.
x n x 0
x 1
(cid:0)
55
56
57
n
1
+ 2
n
+ n
4
12
9
(2
29
56)2
x n
= 1
+ x n = -
Ví D 3ụ - (cid:0) - - (cid:0)
x + n 1 = 1;
2
x 0
x 1
(cid:0)
Xeùt heä thöùc ñeä qui:
n
1
+ 2
(
n
+ n
4
12
9
(2
29
56)2
) 1
x n
+ x n
x n
+ 1
= 1
- - -
Heä thöùc ñeä qui tuyeán tính thuaàn nhaát laø:
(
)
2
4
12
9
0
x n
+ x n
x n
+ 1
= 1
- -
Phöông trình ñaëc tröng cuûa (2) laø:
4(cid:0) 2 12(cid:0) + 9 = 0 (*)
coù moät nghieäm thöïc keùp laø (cid:0) = 3/2.
Do ñoù nghieäm toång quaùt cuûa (2) laø
xn = (C1 + nC2)(3/2)n. (3)
58
ủ Baây giôø ta tìm moät nghieäm rieâng cuûa (1). ø Veá phaûi c a (1) la
2
1
=
+
+
n
n
(2
29
56)2n
nf
-
coù daïng (cid:0) nPr(n) vôùi (cid:0) = 2 vaø Pr(n) laø ña thöùc baäc r = 2 theo n.
Vì (cid:0) = 2 khoâng la ø nghieäm cuûa p h ö ô n g t rìn h ñ a ë c t rö n g (*) n e â n (1 ) c o ù m o ä t n g h ie ä m rie â n g d a ïn g :
xn = (an2 + bn + c)2n (4)
Th e á (4 ) v a ø o (1 ) t a ñ ö ô ïc :
4[a(n+1)2 + b(n+1) + c)2n+1 12[an2 + bn + c] 2n + 9[a(n1)2 + b(n1) + c] 2n1 = (2n2 + 29n +56)2n1
59
Ch o n la à n lö ô ït n h a ä n ba g ia ù t rò n = -1; n = 0; n = 1 t a ñ ö ô ïc h e ä :
+
+
=
a
b
c
3
;
(cid:0)
3 2
1 4
29 4
(cid:0)
+
+
=
(cid:0) (cid:0)
a
b
c
28;
(cid:0)
+
1 2 + =
(cid:0)
a
25 2 40
7 2 b c 8
87.
(cid:0)
(cid:0) (cid:0)
Gia û i h e ä t re â n t a ñ ö ô ïc a = 2; b = 1; c = -1. Th e á v a ø o (4 ) t a t ìm ñ ö ô ïc m o ä t n g h ie ä m rie â n g cu û a (1 ) la ø
xn = (2n2 + n 1)2n (5)
60
Tö ø (3 ) v a ø (5 ) t a s u y ra n g h ie ä m t o å n g q u a ù t c u û a (1 ) la ø :
xn = (C1 + nC2)(3/2)n + (2n2+ n 1) 2n (6)
- =
Th a y ñ ie à u k ie ä n x0 = 1; x1 = -2 v a ø o (6 ) t a ñ ö ô ïc :
1 1;
C 1
(cid:0)
(cid:0)
+
C
+ = - 4
2.
(cid:0)
C 1
2
3 2
3 2
(cid:0) (cid:0)
Tö ø ñ o ù t a c o ù : C1= 2; C2 = 6.
Th e á v a ø o (6 ) t a c o ù n g h ie ä m rie â n g ca à n t ìm c u û a (1 ) la ø :
xn = (2 6n)(3/2)n + (2n2+ n 1) 2n
61
Ví D 4ụ
(
+
3
2
cos
(3 3 2)sin
) 1
x n
x n
= x n
2
+ + 1
p n 4
p n 4
- - -
(
)
+
3
0
2
2
= x n
x n
+ + 1
2
- He ä t h ö ù c ñ e ä q u i t u y e á n t ín h t h u a à n n h a á t la ø : x n
Ph ö ô n g t rìn h ñ a ë c t rö n g cu û a (2 ) la ø :
(cid:0) 2 3(cid:0) + 2 = 0 (*)
coù hai nghieäm thöïc phaân bieät laø (cid:0) 1 = 1; (cid:0) 2 = 2.
Do ñ o ù n g h ie ä m t o å n g q u a ù t c u û a (2 ) la ø :
xn = C1 + C2.2n. (3)
62
Ba â y g iô ø t a t ìm m o ä t n g h ie ä m rie â n g cu û a (1 ).
=
ủ Ve á p h a û i c a (1 ) la
f
cos
(3 3 2)sin
n
p n 4
- -
ø p n 4
coù daïng (cid:0) cosn(cid:0) + (cid:0) sinn(cid:0) vôùi (cid:0) = (cid:0) /4
p
Vì
i
cos
p sin
l = 0
4
4
(cid:0)
=
+
(
)
a
b
cos
sin
4
x n
p n 4
p n 4
khoâng la ø nghieäm cuûa p h ö ô n g t rìn h ñ a ë c t rö n g (*) n e â n (1 ) co ù m o ä t n g h ie ä m rie â n g d a ïn g :
63
+
+
+ p
+
n
n
n
p n
(
(
(
(
+
+
Th e á (4 ) v a ø o (1 ) t a ñ ö ô ïc :
a
b
b
cos
sin
a 3[ cos
sin
]
p 2) 4
1) 4
1) 4
p
=
+
+
-
b
p cos
)
(3 3 2)sin
a 2( cos
sin
p n 4
n 4
n 4
p 2) 4 p n 4
- -
Ch o n la à n lö ô ït n h a ä n h a i g ia ù t rò n = 0; n = -1; t a ñ ö ô ïc h e ä :
(cid:0)
+ - a
(2 3
)
(1 3
= b )
1;
2 2
2 2
- (cid:0) (cid:0)
(cid:0)
a
(3
3)
2 2 3.
2 2
2 = b 2
(cid:0) - - - (cid:0) (cid:0)
=
Gia û i h e ä t re â n t a ñ ö ô ïc a = 1; b = -1. Th e á v a ø o (4 ) t a t ìm ñ ö ô ïc m o ä t n g h ie ä m rie â n g c u û a (1 ) la ø
(
)
cos
sin
5
x n
p n 4
p n 4
-
64
n
=
+
Tö ø (3 ) v a ø (5 ) t a s u y ra n g h ie ä m t o å n g q u a ù t c u û a (1 ) la ø :
+ C C
cos
sin
x n
1
2.2
p n 4
p n 4
-
65
Ví D 5ụ
n
+
+ n 2
(
n
4
3
20 (2
)2
3.4
) 1
x n
x n
x n
+ 1
= 2
- - - - -
(
3
0
4
x n
x n
x n
+ 1
= 2
- - - He ä t h ö ù c ñ e ä q u i t u y e á n t ín h t h u a à n n h a á t la ø : ) 1
Ph ö ô n g t rìn h ñ a ë c t rö n g cu û a (2 ) la ø :
(cid:0) 2 4(cid:0) + 3 = 0 (*)
coù hai nghieäm thöïc phaân bieät laø (cid:0) 1 = 1; (cid:0) 2 = 3. Do ñ o ù n g h ie ä m t o å n g q u a ù t c u û a (2 ) la ø :
xn = C1 + C2. 3n. (3)
66
Ba â y g iô ø t a t ìm m o ä t n g h ie ä m rie â n g cu û a (1 ).
ủ ø Ve á p h a û i c a (1 ) la
n
n
=
+ 2
n
+ 20 (2
)2
3.4
nf
- -
c o ù d a ïn g ô û Trö ô ø n g h ô ïp 4 .
Xe ù t c a ù c h e ä t h ö ù c ñ e ä q u i:
3
20
4
1
x n
x n
x n
= 2
(cid:0) - - -
n
2
( (
) )
n
4
3
(2
)2
1
x n
x n
x n
+ 1 + 1
= 2
n
- (cid:0) (cid:0) - - - -
(
)
4
3
3.4
1
x n
x n
x n
+ 1
= 2
(cid:0) (cid:0) (cid:0) - - -
67
ơ
Lyù luaän tö ng töï nhö treân ta tìm ñöôïc:
Moät nghieäm rieâng cuûa (1’) laø xn1 = 10n
Moät nghieäm rieâng cuûa (1’’) laø xn2 = n2n
Moät nghieäm rieâng cuûa (1’’’) laø xn3 = 4n+2
Suy ra moät nghieäm rieâng cuûa (1) laø:
xn1 = 10n + n2n + 4n+2 (4)
xn = C1 + C2.3n 10n + n2n + 4n+2
Töø (3) vaø (4) ta suy ra nghieäm toång quaùt cuûa (1) laø:
68
ề
Víd (ụ Bài 4 Đ thi2007)
ổ
ệ
ủ
ệ ứ
ệ
ề
ỏ
ầ a 0 =
ệ a) Tìm nghi m t ng quát c a h th c đ qui: an = an 1 + 6 an2 ệ b) Tìm nghi m th a đi u ki n đ u ủ ệ ứ ệ 1, a1 = 5 c a h th c đ qui: an = a n – 1 + 6 a n – 2 + 50n 3 n – 1
69
ặ
ư
ổ
ạ
ng trình đ c tr ng r 2 – ệ
ệ r – 6 = 0 có 2 nghi m r 1 = an = c 3n + d (–
ặ
ệ
ệ
n(An+B)3n :
ệ
ạ
ổ
c 3n + d (–2) n +
ệ
ầ
Đáp án: 1,5đ ươ a) Ph 3, r2 = –2 nên nghi m t ng quát có d ng: 2)n (0,5đ) ạ b) Ta tìm nghi m đ c bi t có d ng (An2 +Bn) 3n = (A(n–1)2 + B(n–1)) 3n 1 + 6 (A(n–2)2 + B(n–2)) 3n 2 + 50n 3n1 10An – 50 n + 5B – 9A = 0 hay A = 5 , B = 9 (0,5đ) Do đó nghi m t ng quát có d ng: an = (5n2 + 9n) 3n ề Các đi u ki n ban đ u cho: a 0 = c + d = 1, a1 = 3c – 2 d + 42 = 5 gi
ng trình trên ta đ
ả ệ ươ i h ph
c
ượ c = –7, d = 8 (0,5đ)
70
{
ỗ
Víd (Đ thi2006).
} 0,1, 2 ớ
có d ng a1a2...an v i a1, a2,..,an
ượ
ọ
c g i là m t t ố
ỗ Cho X= . M i chu i ký X (n ề ộ ừ có chi u dài ề có chi u dài n trên
ừ ế
ố
ồ
ộ ể
(cid:0)
ụ ề ạ ự t ươ ng)đ nguyên d ọ n trên X. G i Ln là s các t ứ 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 ừ ố _ S các t ừ ố _ S các t + Có Ln2 t + Có Ln2 t
có chi u dài n mà a1 = 0 là Ln1 có chi u dài n mà a1 = 1 là Ln1 có chi u dài n mà a1 = 2 : mà a2 = 0 mà a2 = 1
ậ
ề ề
có chi u dài 1 là : 0,1,2. L1 = 3; có chi u dài 2 là : 00,01,02,10,11,12,20,21 . L2 = 8; ướ
�
ệ ứ ệ c L0 = 1 thì h th c đ quy tho v i n >1 - = 2 2 x x 3
ả ớ =� x 1
2 0
ư
V y Ln = 2Ln1 + 2Ln2 (n > 3) b)1 đi mể ừ Các t ừ Các t Ta quy ươ Ph
ặ ng trình đ c tr ng
-
72
n
n
ệ =
+
A
B
ổ Nghi m t ng quát : + (1
3)
(1
3)
L n
-
+
=
(cid:0)
+ =
1
(cid:0)
A
= B
(cid:0)� A B � + (1
3)
+ - (1
3)
3
3
=
A �(cid:0) � B
(cid:0) (cid:0) (cid:0)
3 2 2 3 - + 2 2 3
+
3
n
n
=
+
+
(cid:0) (cid:0)
�
(1
3)
(
)(1
3)
L n
3 2 2 3
- + 2 2 3
-
73
ề
Đ thi2006
ổ
ệ
ệ
ủ
ứ
ủ ệ ứ ệ
ệ
ả ề
ầ
ệ a)Tìm nghi m t ng quát c a h th c đ qui : an= 4an1 4 an2 b)Tìm nghi m c a h th c đ qui: an= 4an1 4 an2+3. 2n+1 ệ tho đi u ki n đ u:a0=4,a1=4
74
ề
Đ thi2006
ệ
ươ
ng trình đ c tr ng x24x+4 = 0 có nghi m
ạ
β
ủ
ệ
ng trình đ c
ư
ệ
ặ ươ ướ ạ i d ng Cn22n.
Đáp án ư ặ a) Ph ổ ệ 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 tr ng nên ta tìm nghi m riêng d Ta có Cn22n =4C(n1)22n14C(n2)22n2+3.2n+1 (cid:0)
C = 3 (0,5đ)
75
ề
Đ thi2006
ạ
ử ụ
ổ ệ 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
ề ọ
ừ
Cho X={0,1,2}.G i an là s các t
Đ thi 2006 ố ố
ệ
ề ấ ệ
ế
ấ
ả ệ
ứ
ằ
ệ a) Ch ng minh r ng an tho h th c đ
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.ế ứ qui:
ớ ứ ủ
ể
an= 2an1+an2 v i n>2. b)Tìm bi u th c c a an theo n.
77
ề
Đ thi 2006
ọ
ứ
ố ừ
ầ ượ
t là s t
ớ x1x2…xn ng v i
Đáp án (2,5 đi m)ể a)1 đi mể G i bn,cn,dn l n l x1= 0, x1=1, x1= 2. Ta có bn = an1 ; cn = bn1 +dn1 ;dn= bn1+cn1 Do đó an = bn + cn +dn = an1 +bn1+dn1+bn 1+cn1 = an1+an2+(dn1+bn1+cn1) = an1+an2+an1 = 2an1+an2
78
ề
Đ thi 2006
ề
ả
ầ
tho yêu c u
ả ớ
ệ
ặ
là: ướ c a0=1thì ng trình đ c
b)1,5 đi m.ể ừ Các t có chi u dài 1 là 0,1,2 nên a1 =3. ề ừ Các có chi u dài 2 t 00,01,02,10,12,20,21 nên a2 =7.Ta qui ươ ệ ứ h th c đ qui tho v i n >1. Ph ư tr ng x2 – 2x – 1 = 0 có hai nghi m là
x = (cid:0) 1
ệ 2
79
ề
Đ thi 2006
ệ
ổ
Do đó nghi m t ng quát là
n
n
=
+
+
A
B
(1
2)
(1
2)
na
ở
ị
Trong đó A và B xác đ nh b i
+ =
1
A B +
+
-
A
B
(1
2)
(1
= 2) 3
-
80
ề
Đ thi 2006
Suy ra
+
1
2
1
2
=
=
A
B
,
2
n
n
+ 1
+ 1
=
+
+
-
(1
2)
(1
2)
a n
1 2
2 1 2
-
81
ề
Đ thi 2008
ố
ề
ự
• Tìm s các chu i ký t
ỗ ọ
ứ chi u dài n ch a chu i ự ượ c ch n đ
ng pháp đ i l p).
ố ậ ứ
ươ ỗ
ỗ
ỗ con 11 hay 22, trong đó các ký t trong {0, 1, 2}. ả i 1.(Ph ố ư ề
ượ
ả
• Cách gi ọ G i an là s chu i không ch a chu i con 11 và 22. Gi
i nh đ 2006 ta đ
c
n
n
+ 1
+ 1
=
+
+
(1
2)
(1
2)
na
1 2
1 2
-
82
ề
Đ thi 2008
n
+ 1
(1
2)
ỗ 1 2
ố ừ
ứ
x1x2…xn ng
ự ứ th 2 là 1 thì ự
ớ
ỗ
ề
phía sau đ u
ỗ ứ ư ậ ố Nh v y s chu i ch a chu i con 11 hay 22 là 1 + + + = n n n 1 na (1 3 2) 3 2 ả ự ế Cách gi i 2 (Tr c ti p) ọ ầ ượ t là s t G i bn,cn,dn l n l ớ v i x1= 0,x1=1,x1=2. Khi đó: an = bn +cn +dn . bn = an1 . cn = bn1 + 3n2 +dn1(vì khi ký t ọ ế ợ k t h p v i m i chu i n 2 ký t th a).ỏ
- - -
83
ề
Đ thi 2008
ự
ươ
:
ng t
ệ ứ ệ
ế
ầ
ả ệ ứ ệ
i h th c đ qui này ta có
ả ư
T dn = bn1 +cn1+3n2 . Do đó: an = an1 +bn1 +3n2 +dn1 + bn1 +cn1 +3n2 = an1+2.3n2 +an1 +an2= 2 .an1+an2 +2.3n2. ậ V y ta có h th c đ qui tuy n tính không thu n nh t ấ an = 2.an1 + an2 + 2.3n2. ớ v i a0 = 0 và a1 = 0.Gi k tế qu nh cách 1.
84
ề
Đ thi 2005
ệ ứ
ủ
ệ
ổ
ệ a) Tìm nghi m t ng quát c a h th c đ
qui:
ủ ệ ứ ệ
ả ề
an = 6an1 – 9an2 ệ b) Tìm nghi m c a h th c đ qui: an = 6an1 – 9an2+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
ề
ả
ổ
ả
ố ả ố ề ứ ả
ủ
ủ ổ ướ
ứ
a)
ồ
b)
ể
ầ ư ồ ủ ầ ộ vào ngày đ u c a m t năm . Ngày cu i cùng ượ ưở ườ ủ i đó đ ng hai kho n ti n c h c a năm ng ứ ấ 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
ộ
ạ
ữ
ượ
xe đ
ạ
ạ
ể ế ộ
ỗ
ế
ố
ọ
ầ
ả ở
ứ ủ
c chia thành n lô c nh M t bãi gi 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ậ
2
ả Gi ệ ứ ệ i các h th c đ qui sau:
n
n
2
5
2
+ 2
3;
x n
= - 2
x n =
+ x n 1 =
(cid:0) - - - - 1) (cid:0)
1,
3.
x 0
x 1
+
(cid:0)
+ n
4
5
12
8;
1
= 2
=
= -
- (cid:0) - - 2) (cid:0)
0,
x n 5.
x n x 0
x n x 1
(cid:0)
+
+
=
+
n
2
5
2
(35
n 51)3 ;
x n
(cid:0)
x + n =
x n =
(cid:0) 3)
2 3,
+ 1 0.
x 0
x 1
(cid:0)
88
Bài t pậ
ả Gi ệ ứ ệ i các h th c đ qui sau:
2
2;
= x n
- (cid:0)
+ 2 =
(cid:0) 4)
+ x + n 1 = 0.
1,
x n x 0
x 1
(cid:0)
16
64
n 128.8 ;
= x n
(cid:0) -
+ 2 =
5) (cid:0)
2,
+ x + n 1 = 32.
x n x 0
x 1
(cid:0)
+
cos
sin
.
x n
x n
= - x n
2
+ + 1
3 2
p n 3
3 2
p n 3
- - 6)
89
Bài t pậ
ả Gi ệ ứ ệ i các h th c đ qui sau:
8
15
+ n 1 2.5 ;
= x n
(cid:0) -
+ 2 = -
7) (cid:0)
1,
2.
x n x 0
+ x + n 1 = - x 1
(cid:0)
16
64
n 128.8 ;
= x n
(cid:0) -
+ 2 =
8) (cid:0)
2,
+ x + n 1 = 32.
x n x 0
x 1
(cid:0)
n
+ 2
n
3
2
+ 20
2
n 3
x n
x n
x n
+ 1
= 2
- 9) - - -
90
Bài t pậ
ị
ệ ứ ệ ặ
ng nào
ườ
ề
ủ ệ ứ ệ
ệ
ề
ệ
ệ
ầ
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 đ ồ song song và không có ba đ ng nào đ ng qui. Tìm xn . 11) Đ thi 2009. ổ a) Tìm nghi m t ng quát c a h th c đ qui: an = 6an2 – 9 an1. ỏ b) Tìm nghi m th a đi u ki n đ u a0 = 1, a1 = 3
c a ủ ệ ứ ệ h th c đ qui: an = 6an2 – 9an1 + n.3n+1
91
Bài t p ậ
ề
ệ
ổ
12) Đ thi 2010. ủ ệ ứ ệ a) Tìm nghi m t ng quát c a h th c đ
qui:
ề
ệ
ệ
ầ
ủ
an = 6an2 + an1. ỏ b) Tìm nghi m th a đi u ki n đ u a0 = 8, ệ ứ ệ a1 = 3 c a h th c đ qui: an = 6an2 + an1 + 10n( 2) n 3 ( 2) n 1
92
