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

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.

Nội dung trích xuất từ tài liệu:
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ảoPhần IV [1] TS. Trần Ngọc Hội, Toán rời rạcHệ 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 SlidesBiê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êngMoã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ỏ.SangBà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 ñitớ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átF1 = 1 caàu thang. Tìm moät heä thöùc ñeä qui cho xnF2 =1Fn = Fn-1+Fn-2 v ...