Bài giảng Toán rời rạc: Chương 4 - TS. Nguyễn Viết Đông

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

537
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Toán rời rạc - Chương 4: Hệ thức đệ quy" cung cấp cho người học các kiến thức: ĐỊnh nghĩa, nghiệm tổng quát, nghiệm riêng, hệ thức đệ qui tuyến tính thuần nhất, hệ thức đệ qui tuyến tính không thuần nhất. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Chương 4 - TS. Nguyễn Viết Đông

Tài liệu tham khảo Phần IV [1] TS. Trần Ngọc Hội, Toán rời rạc Hệ thức đệ quy [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 Biên soạn: TS.Nguyễn Viết Đông 1 2 Định nghĩa Định nghĩa Moät heä thöùc ñeä qui tuyeán tính caáp k laø moät Tröôøng hôïp daõy fn= 0 vôùi moïi n thì (1) trôû heä thöùc coù daïng: thaønh: xn = a1xn-1 +… + akxn-k + fn (1) xn = a1xn-1 +… +akxn-k (2) trong ñoù : • ak  0, a1,…, ak-1 laø caùc heä soá thöïc Ta noùi (2) laø moät heä thöùc ñeä qui tuyeán tính • {fn} laø moät daõy soá thöïc cho tröôùc thuaàn nhaát caáp k • {xn} laø daõy aån nhaän caùc giaù trò thöïc. 3 4 1
Nghiệm tổng quát Nghiệm riêng Moãi daõy {xn} thoûa (1) ñöôïc goïi laø moät Cho {xn} là nghiệm tổng quát của (1) và vôùi moïi k nghieäm cuûa (1). giaù trò ban ñaàu y0, y1,…, yk-1, toàn taïi duy nhaát caùc • Nhaän xeùt raèng moãi nghieäm {xn} cuûa (1) ñöôïc giaù trò cuûa k tham soá C1, C2,…,Ck sao cho nghieäm hoaøn toaøn xaùc ñònh bôûi k giaù trò ban ñaàu x0, x1,…, xk-1. {xn} töông öùng thoûa: x0 = y0, x1 = y1,…, xk-1 = yk-1 (*) Hoï daõy soá { xn = xn(C1, C2,…,Ck)} phuï thuoäc vaøo k hoï tham soá C1, C2,…,Ck ñöôïc Khi ñoù, nghieäm {xn} töông öùng ñöôïc goïi nghieäm goïi laø nghieäm toång quaùt cuûa (1) neáu moïi rieâng öùng vôùi ñieàu kieän ban ñaàu (*). daõy cuûa hoï naøy ñeàu laø nghieäm cuûa (1) 5 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ù. Fibonacci (1170-1250) 7 8 2
Một số ví dụ Một số ví dụ Ví dụ 1(Dãy Fibonacci) Giải: Tháng đầu tiên và tháng thứ 2 chỉ có mộtđôithỏ.Sang Bài toán:Một đôi thỏ(gồm một thỏ đực và một tháng thứ 3 đôi thỏ này sẽ đẻ ra một đôi thỏ, vì thế thỏ cái)cứ mỗi tháng đẻ được một đôi thỏ tháng này sẽ có hai đôi thỏ .Với n3 ta có con(cũng gồm một đực và một cái), mỗi đôi Fn = Fn-1+Số đôi thỏ được sinh ra ở tháng thứ n. thỏ con, khi tròn hai tháng tuổi, lại mỗi Do các đôi thỏ được sinh ra ở tháng thứ n-1 chưa tháng đẻ ra một đôi thỏ con và quá trình đẻ con ở tháng thứ n , và ở tháng này mỗi đôi thỏ sinh nở cứ thế tiếp diễn.Tính Fn là số đôi thỏ có ở tháng n-2 sẽ đẻ ra được một đôi thỏ con nên số có ở tháng n? đội thỏ được sinh ra ở tháng thứ n chính bằng Fn-2 9 10 Một số ví dụ Một số ví dụ Như vậy việc giải bài toán Fobonacci dẫn ta Ví dụ2: Moät caàu thang coù n baäc. Moãi böôùc ñi tới việc khảo sát dãy số (Fn), xác định bởi goàm 1 hoaëc 2 baäc. Goïi xn laø soá caùch ñi heát F1 = 1 caàu thang. Tìm moät heä thöùc ñeä qui cho xn F2 =1 Fn = Fn-1+Fn-2 với n >2. 11 12 3
Một số ví dụ Ví dụ Vôùi n = 1, ta coù x1 = 1. 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 Vôùi n = 2, ta coù x2 = 2 caàu thang trong tröôøng hôïp naøy laø xn-2. Vôùi n > 2, ñeå khaûo saùt xn ta chia thaønh hai tröôøng hôïp loaïi Theo nguyeân lyù coäng, soá caùch ñi heát caàu thang laø tröø laãn nhau: xn-1 + xn-2 . Do ñoù ta coù: Tröôøng hôïp 1: Böôùc ñaàu tieân goàm 1 baäc. xn = xn-1 + xn-2 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ø x n-1. 13 14 Example3: The tower of Hanoi puzzle consists of three Một số ví dụ pegs mounted on a board and disks with different sizes. Vaäy ta coù heä thöùc ñeä qui tuyeán tính thuaàn nhaát caáp 2:  xn  xn1  xn2   x1  1, x2  2. How can we move the disks to the 2nd peg, following the 15 rule: larger disks are never placed on top of smaller ones? 16 4
How can we move the disks to the 2nd peg, one in a  Let Hn be the minimum number of moves to complete the time,following the rule: larger disks are never placed puzzle. First we must move the top (n – 1) disks to the 3rd on top of smaller ones? peg, using at least Hn – 1 moves 17 18  We need one more move to take the largest disk to peg 2 Modeling with Recurrence  Then carry (n – 1) smaller disks from 3rd peg to the 2nd Relations peg, using at least Hn – 1 moves .  First, move the top (n – 1) disks to the 3rd peg, using at least Hn – 1 moves  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 19 20 5
 We can prove by induction that Hệ thức đệ qui tuyến tính thuần nhất Hn = 2 Hn – 1 + 1  To solve this recurrence relation, we write Xeùt heä thöùc ñeä qui tuyeán tính thuaàn nhaát Hn + 1 = 2 Hn – 1 + 2 = 2(Hn – 1+ 1) xn = a1xn-1 +… + akxn-k (2)  This is a geometric progression, so the solution is: Hn + 1 = C 2n Since H1 = 1, we have C = 1 and Phöông trình ñaëc tröng cuûa (2) laø phöông trình Hn = 2 n – 1 baäc k ñònh bôûi: E.g. H64 = 18,446,744,073,709,551,615: k - a1k-1 -… - ak = 0 (*) It takes 500 billion years to solve the puzzle !! 21 22 Hệ thức đệ qui tuyến tính thuần nhất Hệ thức đệ qui tuyến tính thuần nhất Tröôøng hôïp k = 1 Ví dụ: Hệ thức đệ qui Phöông trình ñaëc tröng (*) trôû thaønh 2 xn  3xn1  0;   - a1 = 0  x1  1. neân coù nghieäm laø 0 = a1 laø moät heä thöùc ñeä qui tuyeán tính thuaàn nhaát caáp 1 Khi ñoù, (2) coù nghieäm toång quaùt laø: xn  C0n 23 24 6
Hệ thức đệ qui tuyến tính thuần nhất Hệ thức đệ qui tuyến tính thuần nhất Phöông trình ñaëc tröng: 2 - 3 = 0 coù nghieäm Töø ñieàu kieän ban ñaàu x1 = 1, ta coù : laø 0 = 3/2 3 C  1 Suy ra: 2 Do ñoù nghieäm toång quaùt laø: 2 C n 3 3 Do ñoù nghieäm cuûa heä thöùc ñeä qui ñaõ cho laø: xn  C   2 3 n 1 xn    25 2 26 Hệ thức đệ qui tuyến tính thuần nhất 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: b) Neáu (*) coù nghieäm keùp thöïc 0 thì (2) coù 2 - a1 - a2 = 0 (*) nghieäm toång quaùt laø: a) Neáu (*) coù hai nghieäm thöïc phaân bieät 1 vaø 2 thì (2) coù nghieäm toång quaùt laø: xn  ( A  nB)0n xn  A1n  B2n 27 28 7
Hệ thức đệ qui tuyến tính thuần nhất Ví dụ: c) Neáu (*) coù hai nghieäm phöùc lieân hôïp ñöôïc Giaûi caùc heä thöùc ñeä qui sau: vieát döôùi daïng löôïng giaùc : Ví dụ 1 2 xn  3xn1  xn2  0   r (cos   i sin  ) thì (2) coù nghieäm toång quaùt laø: 4 xn1  12 xn  9 xn1  0; Ví dụ 2   x0  2; x1  4. xn  r n ( A cos n  B sin n )  xn2  2 xn1  4 xn  0; Ví dụ 3  29  x1  4; x2  4. 30 Một số ví dụ Một số ví dụ 2 xn  3xn1  xn2  0 1 4 xn1  12 xn  9 xn1  0   2  x0  2; x1  4. Phöông trình ñaëc tröng cuûa (1) laø: Phöông trình ñaëc tröng cuûa (2) laø: 22 - 3 + 1 = 0 (*) 42 - 12 + 9 = 0 coù hai nghieäm thöïc laø 1 = 1 vaø 2 = 1/2. coù nghieäm thöïc keùp laø 0 = 3/2. Do ñoù Do ñoù nghieäm toång quaùt cuûa (1) laø: nghieäm toång quaùt cuûa (2) laø: xn = (A + nB)(3/2)n xn = A + B(1/2)n 31 32 8
Một số ví dụ Một số ví dụ Töø ñieàu kieän ban ñaàu x0 = 2; x1 = 4 ta suy ra:  xn2  2 xn1  4 xn  0  3  A  2  x1  4; x2  4  Phöông trình ñaëc tröng cuûa (3) laø: 3  ( A  B)  4 2 2 - 2 + 4 = 0 (*) Suy raA = 2 vaø B = 2/3 coù hai nghieäm phöùc lieân hôïp laø   1 i 3 Vaäy nghieäm cuûa (2) Ta vieát hai nghieäm treân döôùi daïng löôïng giaùc: laø:   xn = (3 + n)(3/2)n-1   2(cos  i sin ) 33 3 3 34 Do ñoù nghieäm toång quaùt cuûa (3) laø n n xn  2n (C1 cos  C2 sin ) 3 3 Töø ñieàu kieän ban ñaàu x1 = 4; x2 = 4 ta suy ra:  1 3  2( C  C )4  2 1 2 2 Suy ra: C1  1, C2  3  4( 1 C  3 C )  4   2 1 2 2 n n Vậy nghiệm của (3) là : xn  2n (cos  3 sin ) 3 3 35 36 9
Hệ thức đệ qui tuyến tính không Hệ thức đệ qui tuyến tính không thuần nhất thuần nhất Xeùt heä thöùc ñeä qui tuyeán tính khoâng thuaàn nhaát Nghieäm toång xn = a1xn-1 +… + akxn-k + fn (1) quaùt cuûa (2) Nghieäm toång quaùt cuûa (1) = + Heä thöùc ñeä qui tuyeán tính thuaàn nhaát töông öùng laø: Moät nghieäm x = a x +… + a x n 1 n-1 k n-k (2) rieâng cuûa (1) Phöông trình ñaëc tröng cuûa (2) laø: k - a1k-1 -… - ak = 0(*) 37 38 Hệ thức đệ qui tuyến tính không Hệ thức đệ qui tuyến tính không thuần nhất thuần nhất Caùch tìm moät nghieäm rieâng cuûa (1) khi veá Dạng 1: fn = nPr(n), phaûi fn cuûa (1) coù daïng ñaëc bieät nhö sau: Khi ñoù ta xeùt 3 tröôøng hôïp nhoû: • Dạng 1: fn = nPr(n), trong ñoù Pr(n) laø moät ña Trường hợp 1  khoâng laø nghieäm cuûa phöông trình thöùc baäc r theo n;  laø moät haèng soá ñaëc tröng • Dạng 2: fn = Pm(n)cosn + Ql(n)sinn, trong Trường hợp 2  laø nghieäm đơn cuûa phöông trình ñoù Pm(n), Ql(n) laàn löôït laø caùc đa thức baäc m, l ñaëc tröng theo n;  laø haèng soá (  k). Trường hợp 3  laø nghieäm kép cuûa phöông trình ñaëc • Dạng 3 : fn = fn1 + fn2 +…+ fns , trong ñoù tröng caùc fn1, fn2,…, fns thuoäc 2 daïng ñaõ xeùt ôû treân 39 40 10
Hệ thức đệ qui tuyến tính không Hệ thức đệ qui tuyến tính không thuần nhất thuần nhất Trường hợp 1. Trường hợp 2. Neáu  khoâng laø nghieäm cuûa phöông trình ñaëc Neáu  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: tröng (*) thì (1) coù moät nghieäm rieâng daïng: xn = nQr(n) xn = nnQr(n) 41 42 Hệ thức đệ qui tuyến tính không Hệ thức đệ qui tuyến tính không thuần nhất thuần nhất Chú ý: Trường hợp 3. Neáu  laø nghieäm keùp cuûa phöông trình ñaëc 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ø tröng (*) thì (1) coù moät nghieäm rieâng daïng: r+1 heä soá caàn xaùc ñònh. Các hệ số xác xn = n2nQr(n) Ñeå xaùc ñònh caùc heä soá treân ta caàn theá xn, xn-1,…, xn-k vaøo định như thế nà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 43 44 11
Hệ thức đệ qui tuyến tính không Hệ thức đệ qui tuyến tính không thuần nhất thuần nhất Dạng 2: fn = Pm(n)cosn + Ql(n)sinn Trường hợp 1. Khi ñoù ta xeùt 0 = cos isin. Coù 2 tröôøng Neáu 0 = cos  isin khoâng laø nghieäm cuûa hôïp nhoû: phöông trình ñaëc tröng (*) thì (1) coù moät nghieäm rieâng daïng: Trường hợp 1 0 = cos  isin khoâng laø xn = Rk(n)cosn + Sk(n)sinn 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 46 Hệ thức đệ qui tuyến tính không Hệ thức đệ qui tuyến tính không thuần nhất thuần nhất Trường hợp 2. Ghi chú: Neáu 0 = cos  isin laø nghieäm cuûa phöông Rk(n), Sk(n) laø caùc ña thöùc toång quaùt theo n coù trình ñaëc tröng (*) thì (1) coù moät nghieäm rieâng baäc k = max{m,l} vôùi 2k+2 heä soá caàn xaùc ñònh: daïng: Rk(n) = Aknk + Ak-1nk-1 +…+ A0 xn = n(Rk(n)cosn + Sk(n)sinn) Sk(n) = Bknk + Bk-1nk-1 +…+ B0 47 48 12
Hệ thức đệ qui tuyến tính không Ví dụ: thuần nhất a) 2 xn  3xn1  xn2  4n  1.  xn1  6 xn  9 xn1  (18n  12)3n ; Dạng 3 : fn = fn1 + fn2 +…+ fns b)   x0  2; x1  0. Baèng caùch nhö treân ta tìm ñöôïc nghieäm rieâng 4 xn1  12 xn  9 xn1  (2n 2  29n  56)2n1 ; xni (1 i  s) cuûa heä thöùc ñeä qui: c)   x0  1; x1  2. a0xn + a1xn-1 +… + akxn-k = fni n n d) xn2  3xn1  2 xn  cos  (3  3 2)sin 4 4 Khi ñoù xn = xn1 + xn2+…+ xns laø moät nghieäm rieâng cuûa (1) e) xn  4 xn1  3xn2  20  (2  n)2n2  3.4n 49 50 Ví Dụ 1 2 xn  3xn1  xn2  4n  1 (1) 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. Heä thöùc ñeä qui tuyeán tính thuaàn nhaát laø: 2 xn  3xn1  xn2  0 (2) Vì  = 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: Phöông trình ñaëc tröng cuûa (2) laø: xn = n(an + b) (4) Theá (4) vaøo (1) ta ñöôïc: 22 - 3 + 1 = 0 (*) 2n(an+b) -3(n-1)[a(n-1)+b] + (n-2)[a(n-2) + b] = 4n + 1. coù hai nghieäm thöïc laø 1 = 1 vaø 2 = 1/2 Cho n laàn löôït nhaän hai giaù trò n = 0; n = 1 ta ñöôïc heä: Do ñoù nghieäm toång quaùt cuûa (2) laø: a  b  1; xn = C1 + C2(1/2)n  51 3a  b  5. 52 13
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) Töø (3) vaø (5) ta suy ra nghieäm toång quaùt cuûa (1) laø: xn = C1 + C2(1/2)n + n(2n - 1) 53 54 Ví Dụ 2  xn1  6 xn  9 xn1  (18n  12)3n ;   x0  2; x1  0. 55 56 14
Ví Dụ 3 4 xn1  12 xn  9 xn1  (2n 2  29n  56)2n1   x0  1; x1  2 Xeùt heä thöùc ñeä qui: 4 xn1  12 xn  9 xn1  (2n2  29n  56)2n1 1 Heä thöùc ñeä qui tuyeán tính thuaàn nhaát laø: 4 xn1  12 xn  9 xn1  0  2 Phöông trình ñaëc tröng cuûa (2) laø: 42 - 12 + 9 = 0 (*) coù moät nghieäm thöïc keùp laø  = 3/2. Do ñoù nghieäm toång quaùt cuûa (2) laø xn = (C1 + nC2)(3/2)n. (3) 57 58 Baây giôø ta tìm moät nghieäm rieâng cuûa (1). Cho n laàn löôït nhaän ba giaù trò n = -1; n = 0; n = 1 ta ñöôïc heä: Veá phaûi của (1) laø f n  (2n2  29n  56)2n1  3 1 29 3a  2 b  4 c  4 ; coù daïng nPr(n) vôùi  = 2 vaø Pr(n) laø ña thöùc baäc r = 2 theo n.   25 7 1  a  b  c  28; Vì  = 2 khoâng laø nghieäm cuûa phöông trình ñaëc tröng (*) neân (1) coù moät 2 2 2 nghieäm rieâng daïng: 40a  8b  c  87.   xn = (an2 + bn + c)2n (4) Giaûi heä treân ta ñöôïc a = 2; b = 1; c = -1. Theá vaøo (4) ta tìm ñöôïc moät nghieäm Theá (4) vaøo (1) ta ñöôïc : rieâng cuûa (1) laø 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 xn = (2n2 + n - 1)2n (5) 59 60 15
Ví Dụ 4 Töø (3) vaø (5) ta suy ra nghieäm toång quaùt cuûa (1) laø: n n xn2  3xn1  2 xn  cos  (3  3 2)sin 1 4 4 xn = (C1 + nC2)(3/2)n + (2n2+ n -1) 2n (6) Heä thöùc ñeä qui tuyeán tính thuaàn nhaát laø: Thay ñieàu kieän x0 = 1; x1 = -2 vaøo (6) ta ñöôïc: xn2  3xn1  2 xn  0  2 Phöông trình ñaëc tröng cuûa (2) laø: C1  1  1;  3 3 2 - 3 + 2 = 0 (*)  C1  C2  4  2. 2 2 coù hai nghieäm thöïc phaân bieät laø 1 = 1; 2 = 2. Töø ñoù ta coù: C1= 2; C2 = - 6. Do ñoù nghieäm toång quaùt cuûa (2) laø: Theá vaøo (6) ta coù nghieäm rieâng caàn tìm cuûa (1) laø: xn = C1 + C2.2n. (3) xn = (2 - 6n)(3/2)n + (2n2+ n -1) 2n 61 62 Baây giôø ta tìm moät nghieäm rieâng cuûa (1). Theá (4) vaøo (1) ta ñöôïc: Veá phaûi của (1) laø (n  2) (n  2) (n  1) ( n  1) a cos  b sin  3[ a cos  b sin ] n n 4 4 4 4 f n  cos  (3  3 2)sin n n n n 4 4 2(a cos  b sin )  cos  (3  3 2)sin 4 4 4 4 coù daïng cosn + sinn vôùi  = /4 Cho n laàn löôït nhaän hai giaù trò n = 0; n = -1; ta ñöôïc heä:   Vì 0  cos  i sin  2 2 4 4  (2  3 ) a  (1  3 )b  1;  2 2 khoâng laø nghieäm cuûa phöông trình ñaëc tröng (*) neân (1) coù moät nghieäm  rieâng daïng: (3 2  3)a  2 b  2 2  3.   2 2 Giaûi heä treân ta ñöôïc a = 1; b = -1. Theá vaøo (4) ta tìm ñöôïc moät nghieäm rieâng n n xn  a cos  b sin  4 cuûa (1) laø 4 4 n n xn  cos  sin 5 63 4 4 64 16
Ví Dụ 5 Töø (3) vaø (5) ta suy ra nghieäm toång quaùt cuûa (1) laø: xn  4 xn1  3xn2  20  (2  n)2n2  3.4n 1 Heä thöùc ñeä qui tuyeán tính thuaàn nhaát laø: n n xn  C1  C2 .2n  cos  sin xn  4 xn1  3xn2  0 1 4 4 Phöông trình ñaëc tröng cuûa (2) laø: 2 - 4 + 3 = 0 (*) coù hai nghieäm thöïc phaân bieät laø 1 = 1; 2 = 3. Do ñoù nghieäm toång quaùt cuûa (2) laø: xn = C1 + C2. 3n. (3) 65 66 Baây giôø ta tìm moät nghieäm rieâng cuûa (1). Lyù luaän töơng töï nhö treân ta tìm ñöôïc: Veá phaûi của (1) laø Moät nghieäm rieâng cuûa (1’) laø xn1 = -10n f n  20  (2  n)2n2  3.4n coù daïng ôû Tröôøng hôïp 4. Moät nghieäm rieâng cuûa (1’’) laø xn2 = n2n Xeùt caùc heä thöùc ñeä qui: Moät nghieäm rieâng cuûa (1’’’) laø xn3 = 4n+2 xn  4 xn1  3xn2  20 1 Suy ra moät nghieäm rieâng cuûa (1) laø: xn  4 xn1  3xn2  (2  n)2 n2 1 xn1 = -10n + n2n + 4n+2 (4) Töø (3) vaø (4) ta suy ra nghieäm toång quaùt cuûa (1) laø: xn  4 xn1  3xn2  3.4n 1 xn = C1 + C2.3n - 10n + n2n + 4n+2 67 68 17
Đáp án: 1,5đ Vídụ(Bài 4 Đề thi2007) 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 : a) Tìm nghiệm tổng quát của hệ thức đệ qui: (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 an = an- 1 + 6 an-2 10An – 50 n + 5B – 9A = 0 hay A = 5 , B = 9 (0,5đ) b) Tìm nghiệm thỏa điều kiện đầu a 0 = 1, Do đó nghiệm tổng quát có dạng: an = c 3n + d (–2) n + (5n2 a1 = 5 của hệ thức đệ qui: + 9n) 3n Các điều kiện ban đầu cho: an = a n – 1 + 6 a n – 2 + 50n 3 n – 1 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đ) 69 70 Đápán. (2 điểm) Vídụ(Đềthi2006). Cho X= 0,1, 2. Mỗi chuỗi ký tự a)1 điểm _ Số các từ có chiều dài n mà a1 = 0 là Ln-1 có dạng a1a2...an với a1, a2,..,an  X (n nguyên _ Số các từ có chiều dài n mà a1 = 1 là Ln-1 dương)được gọi là một từ có chiều dài n trên X. _ Số các từ có chiều dài n mà a1 = 2 : Gọi Ln là số các từ có chiều dài n trên X không + Có Ln-2 từ mà a2 = 0 chứa 2 số 2 liên tiếp. + Có Ln-2 từ mà a2 = 1 a) Tìm một công thức truy hồi cho Ln. Vậy Ln = 2Ln-1 + 2Ln-2 (n > 3) b)Tìm biểu thức của Ln theo n. 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 x  2 x  2  0  x  1  3 2 71 72 18
Đềthi2006 Nghiệm tổng quát : a)Tìm nghiệm tổng quát của hệ thức đệ qui : Ln  A(1  3)  B(1  3) n n an= 4an-1- 4 an-2  2 3 b)Tìm nghiệm của hệ thức đệ qui: A   A  B  1  2 3   an= 4an-1- 4 an-2+3. 2n+1 (1  3) A  (1  3) B  3  2  3  B  2 3 thoả điều kiện đầu:a0=4,a1=4 2 3 2  3  Ln  (1  3) n  ( )(1  3) n 2 3 2 3 73 74 Đềthi2006 Đềthi2006 Đáp án Do đó nghiệm tổng quát có dạng a) Phương trình đặc trưng x2-4x+4 = 0 có nghiệm an =A 2n +Bn2n +3n22n kép x = 2nên nghiệm tổng quát có dạng Sử dụng ĐKĐ an = (A+nB) 2n (0,5đ) a0 = A = 4 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. a1 =2A+2B +6 = 4 .Nên B = -5 Ta có Cn22n =4C(n-1)22n-1-4C(n-2)22n-2+3.2n+1  C = 3 (0,5đ) 75 76 19
Đềthi 2006 Đềthi 2006 Cho X={0,1,2}.Gọi an là số các từ có chiều Đáp án (2,5 điểm) dài n trên X trong đó số 1 không xuất hiện a)1 điểm liên tiếp và số 2 không xuất hiện liên 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. a) Chứng minh rằng an thoả hệ thức đệ qui: Ta có bn = an-1 ; cn = bn-1 +dn-1 ;dn= bn-1+cn-1 an= 2an-1+an-2 với n>2. Do đó an = bn + cn +dn = an-1 +bn-1+dn-1+bn-1+cn-1 b)Tìm biểu thức của an theo n. = an-1+an-2+(dn-1+bn-1+cn-1) = an-1+an-2+an-1 = 2an-1+an-2 77 78 Đềthi 2006 Đềthi 2006 b)1,5 điểm. Các từ có chiều dài 1 là 0,1,2 nên a1 =3. Do đó nghiệm tổng quát là Các từ có chiều dài 2 thoả yêu cầu là: an  A(1  2)n  B(1  2)n 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 Trong đó A và B xác định bởi x2 – 2x – 1 = 0 có hai nghiệm là A B 1 x  1 2 A(1  2)  B(1  2)  3 79 80 20