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

Trang chủ » Hệ Thức đệ Quy Tuyến Tính Thuần Nhất » Bài Giảng Toán Rời Rạc: Chương 4 - TS. Nguyễn Viết Đông

Có thể bạn quan tâm

OPTADS360 intTypePromotion=1 zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn tailieu.vn NÂNG CẤP Đăng Nhập | Đăng Ký Chủ đề »
  • Đề thi toán cao cấp 2
  • Đại số tuyến tính
  • Toán rời rạc
  • Xác suất thống kê
  • Phương trình vi phân
    • Toán cao cấp
    • Toán kinh tế
  • HOT
    • CEO.27: Bộ Tài Liệu Dành Cho StartUp...
    • LV.26: Bộ 320 Luận Văn Thạc Sĩ Y...
    • FORM.04: Bộ 240+ Biểu Mẫu Chứng Từ Kế...
    • CEO.24: Bộ 240+ Tài Liệu Quản Trị Rủi...
    • CEO.29: Bộ Tài Liệu Hệ Thống Quản Trị...
    • FORM.07: Bộ 125+ Biểu Mẫu Báo Cáo...
    • LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên...
    • TL.01: Bộ Tiểu Luận Triết Học
    • CMO.03: Bộ Tài Liệu Hệ Thống Quản Trị...
    FORM.08: Bộ 130+ Biểu Mẫu Thống Kê Trong Doanh...
TUYỂN SINH YOMEDIA ADSENSE Trang Chủ » Khoa Học Tự Nhiên » Toán học 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.

AMBIENT/ Chủ đề:
  • Bài giảng Toán rời rạc
  • Toán rời rạc
  • Nghiệm tổng quát
  • Hệ thức đệ quy
  • 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

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

Đă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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6.  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
  7. 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
  8. 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
  9. 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
  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 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
  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 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. Đá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
  19. Đề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
  20. Đề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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

  • Bài giảng Toán rời rạc - Chương 2: Quan hệ hai ngôi

    pdf 21 p | 2670 | 171

  • Bài giảng Toán rời rạc - Chương 1: Quan hệ

    ppt 37 p | 826 | 142

  • Bài giảng Toán rời rạc: Chương 5 - Nguyễn Đức Nghĩa

    pdf 78 p | 324 | 60

  • Bài giảng Toán rời rạc - Chương 4: Bài toán tối ưu tổ hợp

    pdf 93 p | 446 | 47

  • Bài giảng Toán rời rạc - Chương 5: Đại số Boole

    pdf 12 p | 281 | 42

  • Bài giảng Toán rời rạc - Chương 4: Đồ thị

    ppt 114 p | 212 | 36

  • Bài giảng Toán rời rạc: Chương 2 - Nguyễn Viết Hưng, Trần Sơn Hải

    ppt 64 p | 208 | 19

  • Bài giảng Toán rời rạc - Chương 1: Cơ sở logic (Phạm Thế Bảo)

    pdf 99 p | 94 | 8

  • Bài giảng Toán rời rạc - Chương 4: Đại Số Bool (Phạm Thế Bảo)

    pdf 78 p | 81 | 7

  • Bài giảng Toán rời rạc: Chương 6 - Nguyễn Đức Nghĩa

    pdf 83 p | 135 | 7

  • Bài giảng Toán rời rạc - Chương 2: Phép đếm (Phạm Thế Bảo)

    pdf 68 p | 40 | 6

  • Bài giảng Toán rời rạc: Chương 2 - ThS. Trần Quang Khải

    pdf 27 p | 50 | 4

  • Bài giảng Toán rời rạc: Chương 5 - Nguyễn Quỳnh Diệp

    pdf 84 p | 38 | 4

  • Bài giảng Toán rời rạc: Chương 4 - Nguyễn Quỳnh Diệp

    pdf 71 p | 47 | 3

  • Bài giảng Toán rời rạc: Chương 2 - Nguyễn Quỳnh Diệp

    pdf 44 p | 39 | 3

  • Bài giảng Toán rời rạc: Chương 5 - Dr. Ngô Hữu Phúc

    pdf 50 p | 11 | 3

  • Bài giảng Toán rời rạc: Chương 4 - TS. Đặng Xuân Thọ

    pdf 50 p | 47 | 2

  • Bài giảng Toán rời rạc: Chương 5 - ThS. Trần Quang Khải

    pdf 14 p | 23 | 2

Thêm tài liệu vào bộ sưu tập có sẵn: Đồng ý Thêm vào bộ sưu tập mới: *Tên bộ sưu tập Mô Tả: *Từ Khóa: Tạo mới Báo xấu
  • Hãy cho chúng tôi biết lý do bạn muốn thông báo. Chúng tôi sẽ khắc phục vấn đề này trong thời gian ngắn nhất.
  • Không hoạt động
  • Có nội dung khiêu dâm
  • Có nội dung chính trị, phản động.
  • Spam
  • Vi phạm bản quyền.
  • Nội dung không đúng tiêu đề.
Hoặc bạn có thể nhập những lý do khác vào ô bên dưới (100 ký tự): Vui lòng nhập mã xác nhận vào ô bên dưới. Nếu bạn không đọc được, hãy Chọn mã xác nhận khác.. Đồng ý LAVA AANETWORK THÔNG TIN
  • Về chúng tôi
  • Quy định bảo mật
  • Thỏa thuận sử dụng
  • Quy chế hoạt động
TRỢ GIÚP
  • Hướng dẫn sử dụng
  • Upload tài liệu
  • Hỏi và đáp
HỖ TRỢ KHÁCH HÀNG
  • Liên hệ
  • Hỗ trợ trực tuyến
  • Liên hệ quảng cáo
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

Đang xử lý... Đồng bộ tài khoản Login thành công! AMBIENT

Từ khóa » Hệ Thức đệ Quy Tuyến Tính Thuần Nhất