tailieunhanh - Bài giảng Toán rời rạc - Phần 4: Hệ thức đệ quy (TS. Nguyễn Viết Đông)

Bài giảng Toán rời rạc - Phần 4: Hệ thức đệ quy (TS. Nguyễn Viết Đông) cung cấp cho học viên những kiến thức về định nghĩa hệ thức đệ quy, nghiệm tổng quát, nghiệm riêng, mục đích giải hệ thức đệ qui, 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 chi tiết nội dung bài giảng! | Phần IV Hệ thức đệ quy Biên soạ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 . 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 a1xn 1 akxn k fn 1 trong ñoù ak 0 a1 ak-1 laø caùc heä soá thöïc fn laø moät daõy soá thöïc cho 3 tröôùc Đị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ï 5 naøy ñeàu laø nghieäm cuûa 1 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 6 goïi nghieäm 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 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 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ó 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