Tóm tắt Luận văn Ứng dụng công thức truy hồi giải toán sơ cấp

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TRẦN THỊ THU HÀ ỨNG DỤNG CÔNG THỨC TRUY HỒI GIẢI TOÁN SƠ CẤP Chuyên ngành: Phương pháp toán sơ cấp Mã số : 60.46.01.13 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Đà Nẵng – Năm 2015 Công trình được hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: PGS.TSKH. Trần Quốc Chiến Phản biện 1: TS. Phan Đức Tuấn Phản biện 2: GS.TS. Lê Văn Thuyết Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp Thạc sĩ Khoa học họp tại Đại Học Đà Nẵng vào ngày 12 tháng 12 năm 2015. Có thể tìm hiểu Luận văn tại: - Trung tâm Thông tin-Học liệu, Đại học Đà Nẵng - Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng 1 MỞ ĐẦU 1. Lý do chọn đề tài Tổ hợp là ngành khoa học xuất hiện khá sớm vào đầu thế kỷ XVII, cho đến nay đã được áp dụng trong nhiều lĩnh vực khác nhau như lý thuyết số, hình học, đại số, xác suất thống kê, quy hoạch thực nghiệm Các vấn đề liên quan đến lý thuyết tổ hợp là một bộ phận quan trọng, hấp dẫn của toán học nói chung và toán rời rạc nói riêng. Nó là một nội dung phong phú và được áp dụng nhiều trong thực tế cuộc sống. Trong toán sơ cấp, tổ hợp cũng xuất hiện rất nhiều trong các bài toán hay và khó. Một trong những chủ đề khá hay của lý thuyết tổ hợp đó là công thức truy hồi. Đây là một trong những kỹ thuật đếm cao cấp để giải các bài toán đếm và là công cụ rất hữu hiệu để giải các bài toán khác có liên quan. Vì vậy, tôi đã quyết định chọn đề tài : “Ứng dụng công thức truy hồi giải toán sơ cấp” để làm đề tài luận văn thạc sĩ của mình. 2. Mục tiêu nghiên cứu Nghiên cứu ứng dụng của công thức truy hồi trong giải toán sơ cấp. 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu Công thức truy hồi. 3.2. Phạm vi nghiên cứu Công thức truy hồi, phương pháp giải và ứng dụng trong các bài toán sơ cấp. 4. Phương pháp nghiên cứu Nghiên cứu lý thuyết, phân tích, tổng hợp các dạng toán. 2 5. Ý nghĩa khoa học và thực tiễn của đề tài Đề tài nghiên cứu tính ứng dụng của công thức truy hồi. Giải quyết được các bài toán đặt ra từ thực tế. 6. Cấu trúc luận văn Ngoài phần mở đầu và kết luận, luận văn được chia làm ba chương: Chương 1: Cơ sở lý thuyết Chương 2: Công thức truy hồi Chương 3: Ứng dụng công thức truy hồi giải toán sơ cấp 3 CHƯƠNG 1 CƠ SỞ LÝ THUYẾT 1.1. TỔNG QUAN VỀ TỔ HỢP 1.1.1. Sơ lược về lịch sử 1.1.2. Bài toán tổ hợp a. Cấu hình tổ hợp và các dạng bài toán tổ hợp Cho các tập hợp , , , . Giả sử là sơ đồ sắp xếp các phần tử , , , được mô tả bằng các quy tắc sắp xếp và , , , là các điều kiện ràng buộc lên mỗi sắp xếp theo sơ đồ . Khi đó mỗi sắp xếp các phần tử của , , , thỏa mãn các điều kiện , , , gọi là một cấu hình tổ hợp trên các tập , , , . Với các cấu hình tổ hợp, ta thường gặp bốn dạng bài toán sau: bài toán tồn tại, bài toán đếm, bài toán liệt kê, bài toán tối ưu. b. Bài toán đếm * Nguyên lý cộng và nguyên lý nhân + Nguyên lý cộng. Giả sử { , , , } là một phân hoạch của tập . Khi đó | | = | | + | | + ⋯+ | |. + Nguyên lý nhân. Giả sử một cấu hình tổ hợp được xây dựng qua bước, bước 1 có thể được thực hiện cách, bước 2 được thực hiện cách,, bước được thực hiện cách. Khi đó, số cấu hình tổ hợp là . . . . * Các cấu hình tổ hợp cơ bản + Chỉnh hợp lặp Định nghĩa 1.1. Một chỉnh hợp lặp chập của phần tử khác nhau là một bộ có thứ tự gồm thành phần lấy từ phần tử đã cho. Các thành phần có thể lặp lại. 4 ( , ) = . + Chỉnh hợp không lặp Định nghĩa 1.2. Một chỉnh hợp không lặp chập của phần tử khác nhau là một bộ có thứ tự gồm thành phần lấy từ phần tử đã cho. Các thành phần không được lặp lại. Số tất cả chỉnh hợp không lặp chập của phần tử là ( , ) = . ( − 1). . ( − + 1) = !( − )!. + Hoán vị Định nghĩa 1.3. Một hoán vị của phần tử khác nhau là một cách sắp xếp thứ tự các phần tử đó. Hoán vị có thể coi như trường hợp riêng của chỉnh hợp không lặp chập của , trong đó = . Ta có số hoán vị là ( ) = !. + Tổ hợp Định nghĩa 1.4. Một tổ hợp chập của phần tử khác nhau là một bộ không kể thứ tự gồm thành phần khác nhau lấy từ phần tử đã cho. Nói cách khác, ta có thể coi một tổ hợp chập của phần tử khác nhau là một tập con có phần từ phần tử đã cho. Gọi số tổ hợp chập của phần tử là ( , ), ta có ( , ) = ! ! ( − )!. * Các cấu hình tổ hợp mở rộng + Hoán vị lặp Định nghĩa 1.5. Hoán vị lặp là hoán vị trong đó mỗi phần tử được ấn định một số lần lặp cho trước. Định lý 1.1. Số hoán vị lặp của phần tử khác nhau, trong đó phần tử thứ nhất lặp lần, phần tử thứ hai lặp lần, , phần tử thứ lặp lần là 5 ( ; , , , ) = ! ! ! ! ; với = + + ⋯+ . Hệ quả 1.1 Giả sử có phần tử, trong đó có phần tử kiểu 1, phần tử kiểu 2,, phần tử kiểu . Khi đó số các hoán vị phần tử của là P( ; , , , ) = ! ! ! ! . + Tổ hợp lặp Ví dụ 1.1. Giả sử ta có 3 đầu sách: Toán, Tin, Lý và mỗi đầu sách có ít nhất 6 quyển. Hỏi có bao nhiêu cách chọn ra 6 quyển. Định nghĩa 1.6. Tổ hợp lặp chập từ phần tử khác nhau là một nhóm không phân biệt thứ tự gồm phần tử trích từ phần tử đã cho, trong đó các phần tử có thể được lặp lại. Định lý 1.2. Giả sử có phần tử khác nhau. Khi đó số tổ hợp lặp chập từ phần tử của , ký hiệu ( , ) là ( , ) = ( + − 1, − 1) = ( + − 1, ). * Hàm sinh Định nghĩa 1.7. Cho dãy số thực ( ) = ( , , ) và biến . Khi đó hàm sinh ( ) của dãy ( , , ) là biểu thức có dạng ( ) = + + + ⋯ = . Ví dụ 1.2. Hàm (1 + ) = ( , ) là hàm sinh của dãy ( , 0), ( , 1), , ( , ). 6 Định lý 1.3 i. Nếu ( ) là hàm sinh của dãy ( ) và ℎ( ) là hàm sinh của dãy ( ) thì . ( ) + .ℎ( ) là hàm sinh của dãy ( . + . ) , với mọi số thực và . ii. Nếu ( ) là hàm sinh của dãy ( ) và ℎ( ) là hàm sinh của dãy ( ) thì ( ).ℎ( ) là hàm sinh của dãy . 1.1.3. Giới thiệu phần mềm Maple Sau khi khởi động Maple, trên màn hình hiện cửa sổ làm việc với dấu nhắc [>. · Hàm ({ ( ) = ∗ ( − ) + ∗ ( − ) + ⋯ , ( ) = , ( ) = , }, ) để giải công thức truy hồi ( ) = ∗ ( − 1) + ∗ ( − 2) + ⋯ , (0) = , (1) = , 1.2. PHƯƠNG TRÌNH SAI PHÂN Định nghĩa 1.8. Phương trình sai phân tuyến tính cấp là một hệ thức tuyến tính có dạng ( + ) + ( + − 1) + ⋯+ ( ) = ( ), (1.1) trong đó , , , là các hệ số của phương trình, ≠ 0, ( ) là một hàm số theo . Nếu ( ) ≡ 0 thì (1.1) có dạng ( + ) + ( + − 1) + ⋯+ ( ) = 0. (1.2) và được gọi là phương trình sai phân tuyến tính thuần nhất cấp với hệ số hằng. 7 Nếu ( ) ≠ 0 thì (1.1) được gọi là phương trình sai phân tuyến tính không thuần nhất cấp với hệ số hằng. Hàm số ( ) thỏa mãn (1.1) được gọi là nghiệm tổng quát của phương trình sai phân tuyến tính (1.1). Hàm số ( ) phụ thuộc tham số, thỏa mãn (1.2) được gọi là nghiệm tổng quát của (1.2). Một nghiệm ∗( ) thỏa mãn (1.1) được gọi là một nghiệm riêng của (1.1). Nghiệm tổng quát ( ) của (1.1) có dạng ( ) = ( ) + ∗( ). 8 CHƯƠNG 2 CÔNG THỨC TRUY HỒI 2.1. KHÁI NIỆM CÔNG THỨC TRUY HỒI Ví dụ 2.1. Xét bài toán đếm số tập con ( ) của tập . Gọi ( ) là số tập con của tập có phần tử. Giả sử có phần tử. Cho x là phần tử của . Tách ( ) ra làm hai nhóm và , nhóm gồm các tập con chứa và nhóm gồm các tập con không chứa . Khi đó chính là ( ∖ { }) và tương đương . Như vậy ta có | ( )| = | | + | | = 2. | ( ∖ { })|. Từ đó suy ra công thức truy hồi: ( ) = 2. ( − 1), ∀ . Định nghĩa 2.1. Công thức truy hồi của dãy (0), (1), (2), là phương trình xác định ( ) bằng các phần tử (0), (1), (2), , ( − 1) trước nó. ( ) = (0), (1), (2), , ( − 1) . Điều kiện ban đầu là các giá trị gán cho một số hữu hạn các phần tử đầu. Trong ví dụ 2.1, ta có điều kiện ban đầu là (0) = 1. 2.2. GIẢI CÔNG THỨC TRUY HỒI 2.2.1. Giải công thức truy hồi bằng phương pháp lặp Nội dung dung của phương pháp này là thay thế liên tiếp công thức truy hồi vào chính nó, mỗi lần thay bậc giảm ít nhất 1 đơn vị, cho đến khi đạt giá trị ban đầu. Ví dụ 2.2. Trên mặt phẳng kẻ đường thẳng sao cho không có ba đường nào đồng quy và không có hai đường nào song song. Hỏi mặt phẳng được chia làm mấy phần? 2.2.2. Giải công thức truy hồi tuyến tính hệ số hằng a. Định nghĩa công thức truy hồi tuyến tính hệ số hằng Định nghĩa 2.2 Công thức truy hồi tuyến tính hệ số hằng bậc có dạng ( ) = . ( − 1) + . ( − 2) + ⋯+ . ( − ) + ( ). (2.1) 9 Trong đó , , , là các hằng số, ≠ 0 và ( ) là hàm số theo . Điều kiện ban đầu của (2.1) là giả thiết một số phần tử của dãy có giá trị cho trước. (0) = , (1) = , , ( − 1) = . Định nghĩa 2.3 Nếu ( ) = 0 thì (2.1) được gọi là công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc . Nếu ( ) ≠ 0 thì (2.1) được gọi là công thức truy hồi tuyến tính không thuần nhất hệ số hằng bậc . b. Phương trình đặc trưng của công thức truy hồi tuyến tính thuần nhất hệ số hằng Xét công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc ( ) = . ( − 1) + . ( − 2) + ⋯+ . ( − ). (2.2) Khi đó − . − . −⋯− = 0. (2.3) gọi là phương trình đặc trưng của công thức truy hồi tuyến tính thuần nhất (2.2). Nghiệm của phương trình đặc trưng (2.3) gọi là nghiệm đặc trưng của công thức (2.2). c. Các định lý về nghiệm Định lý 2.1. Cho công thức truy hồi tuyến tính không thuần nhất hệ số hằng bậc . ( ) = . ( − 1) + . ( − 2) + ⋯+ . ( − ) + ( ). (2.4) Nghiệm tổng quát của (2.4) có dạng ( ) = ℎ( ) + ( ), trong đó ( ) là nghiệm riêng nào đó của (2.4) và ℎ( ) là nghiệm tổng quát của công thức truy hồi tuyến tính thuần nhất tương ứng với (2.4). Định lý 2.2. Nếu , , , là các nghiệm của công thức truy hồi tuyến 10 tính thuần nhất hệ số hằng (2.2) thì = . + . + ⋯+ . là nghiệm của (2.2), trong đó , , , là các hằng số tùy ý. Định lý 2.3. Nếu là nghiệm bội của phương trình đặc trưng (2.3) thì , . , , . là các nghiệm của công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc (2.2). Định lý 2.4. Nếu , , , tương ứng là các nghiệm bội , , , của phương trình đặc trưng (2.3) thì nghiệm tổng quát của (2.2) có dạng ( ) = ( ) + ( ) + ⋯+ ( ), trong đó ( ) = , + , . + , . + ⋯+ , . . , ∀ = 1, 2, , và , ( = 0, 1, 2, , − 1) là các hằng số. *** Ghi chú. Nếu có thêm điều kiện ban đầu thì thế nghiệm tổng quát vào các điều kiện ban đầu để xác định các hằng số. Hệ quả định lý 2.4 · Công thức nghiệm của công thức truy hồi tuyến tính thuần nhất hệ hằng bậc hai Cho công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc hai ( ) = . ( − 1) + . ( − 2), (2.5) với , là các hằng số, ≠ 0 và phương trình đặc trưng có dạng − . − =0. (2.6) i. Giả sử phương trình đặc trưng (2.6) có 2 nghiệm phân biệt , thì nghiệm tổng quát của (2.5) có dạng ( ) = . + . , 11 với , là các hằng số. ii. Giả sử phương trình đặc trưng (2.6) có nghiệm kép thì nghiệm tổng quát của (2.5) có dạng ( ) = . + . . , với , là các hằng số. iii. Giả sử phương trình đặc trưng (2.6) có 2 nghiệm phức liên hợp là = + . , = − ( = −1) thì nghiệm tổng quát của (2.5) có dạng ( ) = λ . ( . cos( ) + . sin( )), trong đó λ = + , tan = , ∈ − 2 ; 2 , và , là các hằng số. · Công thức nghiệm của công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc ba Cho công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc ba ( ) = . ( − 1) + . ( − 2)+ . ( − 3), (2.7) trong đó , , là các hằng số và ≠ 0. Phương trình đặc trưng có dạng − . − . − = 0. (2.8) i. Nếu phương trình đặc trưng (2.8) có 3 nghiệm thực phân biệt , , thì nghiệm tổng quát của (2.7) có dạng ( ) = . + . + . , trong đó , , là các hằng số. ii. Nếu phương trình đặc trưng (2.8) có một nghiệm thực bội 2 và một nghiệm đơn thì nghiệm tổng quát của (2.7) có dạng ( ) = ( + . ). + . , trong đó , , là các hằng số. 12 iii. Nếu phương trình đặc trưng (2.8) có một nghiệm thực bội 3 thì nghiệm tổng quát của (2.7) có dạng ( ) = ( + . + . ). , trong đó , , là các hằng số. iv. Nếu phương trình đặc trưng (2.8) có một nghiệm thực và hai nghiệm phức liên hợp = + = λ. (cos + . sin ), = − = λ. (cos − . sin ) thì nghiệm tổng quát của (2.7) có dạng ( ) = . + λ . ( . cos( ) + . sin( )). trong đó , , là các hằng số. c. Nghiệm riêng * Nghiệm riêng của công thức truy hồi tuyến tính không thuần nhất hệ số hằng bậc một Công thức truy hồi tuyến tính không thuần nhất hệ số hằng bậc một có dạng ( ) = . ( − 1) + ( ), (2.9) trong đó ≠ 0, ( ) là hàm theo và ( ) ≠ 0. Nghiệm đặc trưng của phương trình thuần nhất tương ứng của (2.9) là = . Định lý 2.8. Nếu ( ) là đa thức bậc của , ( ) = ( ) thì nghiệm riêng ( ) của (2.9) có dạng: i. ( ) = ( ), nếu ≠ 1, ii. ( ) = . ( ), nếu = 1, trong đó ( ) là dạng đa thức bậc của . Định lý 2.9. Nếu ( ) = . ( , ≠ 0) thì nghiệm riêng ( ) của (2.9) có dạng: i. ( ) = . , nếu ≠ , ii. ( ) = . , nếu = . Định lý 2.10. Nếu ( ) = ( ). ( ≠ 0) và ( ) là đa thức bậc của thì nghiệm riêng của (2.9) có dạng: 13 i. ( ) = ( ). , nếu ≠ , ii. ( ) = . ( ). , nếu = , trong đó ( ) là dạng đa thức bậc của . Định lý 2.11. Nếu ( ) là nghiệm riêng của phương trình ( ) = . ( − 1) + ( ), ( ) là nghiệm riêng của phương trình ( ) = . ( − 1) + ( ), ( ) là nghiệm riêng của phương trình ( ) = . ( − 1) + ( ), thì ( ) = ( ) + ( ) + ⋯+ ( ) là nghiệm riêng của phương trình ( ) = . ( − 1) + ( ) + ( ) + ⋯+ ( ). * Nghiệm riêng của công thức truy hồi tuyến tính không thuần nhất hệ số hằng bậc hai Công thức truy hồi tuyến tính không thuần nhất hệ số hằng bậc hai có dạng ( ) = . ( − 1) + . ( − 2) + ( ), (2.12) trong đó ≠ 0, ( ) là hàm theo và ( ) ≠ 0. Phương trình đặc trưng của (2.12) có dạng − . − = 0. (2.13) Định lý 2.12 Nếu ( ) là đa thức bậc của , ( ) = ( ) thì nghiệm riêng ( ) của (2.12) có dạng: i. ( ) = ( ), nếu (2.13) không có nghiệm = 1, ii. ( ) = . ( ), nếu (2.13) có nghiệm đơn = 1, iii. ( ) = . ( ), nếu (2.13) có nghiệm kép = 1, trong đó (n) là dạng đa thức bậc của . Định lý 2.12. Nếu ( ) = ( ). ( ≠ 0) và ( ) là đa thức bậc của thì nghiệm riêng của (2.12) có dạng: i. ( ) = ( ). , nếu (2.13) không có nghiệm = , 14 ii. ( ) = . ( ). , nếu (2.13) có nghiệm đơn = , iii. ( ) = . ( ). nếu (2.13) có nghiệm kép = , trong đó ( ) là dạng đa thức bậc của . Định lý 2.13. Nếu ( ) là nghiệm riêng của phương trình ( ) = . ( − 1) + . ( − 2) + ( ), ( ) là nghiệm riêng của phương trình ( ) = . ( − 1) + . ( − 2) + ( ), ( ) là nghiệm riêng của phương trình ( ) = . ( − 1) + . ( − 2) + ( ), thì ( ) = ( ) + ( ) + ⋯+ ( ) là nghiệm riêng của phương trình ( ) = . ( − 1) + . ( − 2) + ( ) + ( ) + ⋯+ ( ). Kết luận. Việc tìm nghiệm riêng của công thức truy hồi tuyến tính không thuần nhất hệ số hằng bậc làm tương tự như tìm nghiệm riêng của công thức truy hồi tuyến tính không thuần nhất hệ số hằng bậc một, hai. Xét công thức truy hồi tuyến tính không thuần nhất hệ số hằng bậc (2.2), i. Nếu ( ) là đa thức bậc và 1 là nghiệm đặc trưng bội của công thức (2.2), thì (2.2) có nghiệm riêng dạng ( ) = + . + . + ⋯+ . . , trong đó các hằng số , , , được xác định bằng cách thế ( ) vào (2.2). ii. Nếu ( ) = , là nghiệm đặc trưng bội của (2.2) thì (2.2) có nghiệm riêng dạng ( ) = . . , 15 trong đó hằng được xác định bằng cách thế ( ) vào (2.2). iii. Giả sử ( ) = ( ) + ( ) + ⋯+ ( ). Trong trường hợp này ta tìm nghiệm riêng ( ) ứng với hàm ( ), = 1, 2, , . Khi đó nghiệm riêng ( ) có dạng ( ) = ( ) + ( ) + ⋯+ ( ). d. Phương pháp tổng quát giải công thức truy hồi bằng phương trình đặc trưng * Công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc ( ) = . ( − 1) + . ( − 2) + ⋯+ . ( − ) Các bước giải như sau: Bước 1. Giả sử công thức truy hồi tồn tại nghiệm dạng ( ) = . Tìm phương trình đặc trưng của công thức truy hồi dạng − . − . −⋯− = 0. Bước 2. Tìm nghiệm của phương trình đặc trưng. Bước 3. Suy ra nghiệm tổng quát có dạng ( ) = . + . + ⋯+ . . Bước 4. Từ các điều kiện ban đầu, ta thay vào công thức nghiệm tổng quát, giải hệ phương trình để tìm các hệ số , , , . Từ đó ta thu được kết quả. * Công thức truy hồi tuyến tính không thuần nhất hệ số hằng bậc ( ) = . ( − 1) + . ( − 2) + ⋯+ . ( − )+ ( ). Các bước giải như sau: Bước 1. Tìm nghiệm tổng quát ℎ( ) của công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc tương ứng. Bước 2. Tìm nghiệm riêng ( ) của công thức truy hồi tuyến tính không thuần nhất. Bước 3. Suy ra nghiệm tổng quát của công thức truy hồi cần giải: 16 ( ) = ℎ( ) + ( ). Bước 4. Sử dụng các điều kiện ban đầu thay vào công thức tìm được ở bước 3, ta thu được kết quả. Ví dụ 2.3. Giải công thức truy hồi ( ) = ( − 1) + ; (0) = 0. 2.2.3. Giải công thức truy hồi bằng hàm sinh * Phương pháp giải Bước 1. Để tìm dãy số { }, ta xét hàm sinh sinh bởi dãy { } là ( ) = . . Bước 2. Dựa vào đặc điểm của dãy { } ta tìm được ( ). Bước 3. Đồng nhất thức ta sẽ thu được dãy { }. Ví dụ 2.4. Giải công thức truy hồi = 3 − 2 ; = 1, = 5. Ví dụ 2.5. Giải công thức truy hồi = − + 2 + 3 ; = 2, = 4. 2.2.4. Giải công thức truy hồi bằng maple Ví dụ 2.6. Giải công thức truy hồi −2 − 3 = − 1 + 2 ; = 1, = 0; ≥ 2. Ví dụ 2.7. Giải công thức truy hồi = − 1 + − 1 ; = 0, ≥ 1. 2.2.5. Tuyến tính hóa công thức truy hồi Nội dung của phương pháp này là đưa một công thức truy hồi ở dạng phi tuyến về dạng tuyến tính. Ví dụ 2.8. Tuyến tính hóa công thức truy hồi = + 4 ; = = 2, ∀ ≥ 3. 17 CHƯƠNG 3 ỨNG DỤNG CÔNG THỨC TRUY HỒI GIẢI TOÁN SƠ CẤP 3.1. ỨNG DỤNG ĐỂ GIẢI QUYẾT CÁC BÀI TOÁN TỔ HỢP 3.1.1. Phương pháp giải Thay vì đếm trực tiếp ( ) theo yêu cầu bài toán, ta thiết lập một công thức liên hệ giữa ( ), ( − 1), để từ đó tính được ( ). Ta thực hiện qua các bước sau: Bước 1: Tìm các giá trị ban đầu (0) = , (1) = , ( − 1) = . Bước 2: Thiết lập công thức truy hồi ( ) = . ( − 1) + . ( − 2) + ⋯+ . ( − ) + ( ), Bước 3: Giải công thức truy hồi trên với các điều kiện ban đầu, từ đó ta tìm được ( ). 3.1.2. Các bài toán Bài toán 3.1.1. (Bài toán tháp Hà Nội ) Có ba cọc 1, 2, 3. Ở cọc 1 có đĩa, kích thước khác nhau, xếp chồng lên nhau sao cho đĩa nằm dưới lớn hơn đĩa nằm trên. Hãy chuyển tất cả các đĩa từ cọc 1 sang cọc 3 với điều kiện mỗi lần chỉ được chuyển một đĩa từ cọc này sang cọc khác và luôn đảm bảo đĩa nằm dưới lớn hơn đĩa nằm trên. Hãy tính số lần di chuyển đĩa. Bài toán 3.1.2. (Bài toán lãi suất ngân hàng) Một người có 20000000 đồng Việt Nam, dự định của người này gửi tiền vào tài khoản tiết kiệm của một ngân hàng với lãi suất là 5% trên một năm. Hỏi số tiền của người ấy nhận được là bao nhiêu (cả gốc lẫn lãi) sau 20 năm tiết kiệm? Tổng quát với số năm gửi là ( ≥ 1). Bài toán 3.1.3. Có người ngồi thành một hàng ngang vào chiếc ghế. Hỏi có bao nhiêu cách lập hàng mới cho người đó mà trong mỗi cách 18 lập, mỗi người hoặc giữ nguyên vị trí của mình, hoặc đổi chỗ cho người liền bên trái, hoặc đổi chỗ cho người liền bên phải. Bài toán 3.1.4. Trên mặt phẳng kẻ đường thẳng sao cho không có 3 đường nào đồng quy và không có 2 đường nào song song. Tính số đa giác được tạo thành. Bài toán 3.1.5. Trong một cuộc thi đấu thể thao có huy chương, được phát trong ngày thi đấu. Ngày thứ nhất, người ta phát 1 huy chương và huy chương còn lại. Ngày thứ hai, người ta phát 2 huy chương và huy chương còn lại. Những ngày còn lại được tiếp tục và tương tự như vậy. Ngày sau cùng còn lại huy chương để phát. Hỏi có tất cả bao nhiêu huy chương và được phát trong bao nhiêu ngày? 3.2. ỨNG DỤNG ĐỂ GIẢI QUYẾT CÁC BÀI TOÁN VỀ DÃY SỐ 3.2.1. Tìm công thức tổng quát của dãy số được cho bởi công thức truy hồi Bài toán tìm công thức tổng quát của dãy số cho bởi công thức truy hồi thực chất là bài toán giải công thức truy hồi. a. Dãy số cho bởi công thức truy hồi là một biểu thức tuyến tính Bài toán 3.2.1. Tìm tất cả các dãy số ( ) thỏa mãn: = 3 − 5 và ( ) là một dãy tăng. b. Dãy số cho bởi công thức truy hồi là một hệ biểu thức tuyến tính Nếu dãy số cho bởi công thức truy hồi là một hệ biểu thức tuyến tính có dạng: = ; = = . + . = . + . ( , , , , , ∈ R). 19 Ta giải như sau: Từ phương trình thứ hai của hệ, biến đổi ta được = ( + ) + ( − ) ; = , = + . Giải công thức truy hồi ta tìm được . Thay vào hệ ta tìm được . Bài toán 3.2.2. Tìm , thỏa mãn: = 2; = 0 4 = 2 − 3 2 = 2 + (3.5) c. Dãy số cho bởi công thức truy hồi là một biểu thức tuyến tính với hệ số biến thiên Việc giải công thức truy hồi với hệ số biến thiên rất phức tạp. Trong phần này, ta chỉ xét một số bài toán được giải bằng phương pháp đặt dãy số phụ. Bài toán 3.2.3. Cho dãy số ( ) xác định bởi: = 23 = 2 − 2 ∀ ≥ 1. Xác định công thức tổng quát của . Bài toán 3.2.4. Tìm công thức tổng quát của dãy số (u ) thỏa mãn: = 0, = ( + 1),∀ ≥ 2. Bài toán 3.2.5. Tìm công thức tổng quát của dãy số ( ) thỏa mãn: = 0, = ( ) ( )( ) ( + 1),∀ ≥ 2. Bài toán 3.2.6. Tìm số hạng tổng quát của dãy số ( ) biết rằng: = > 0, = ( ) ( ) ; trong đó ( − 1),∀ ≥ 2, ∈ N∗ cho trước. d. Dãy số cho bởi công thức truy hồi dạng phân tuyến tính với hệ số hằng 20 Dạng 3.2.1. Tìm số hạng tổng quát của dãy số ( ) cho bởi: = , = + ; với ∀ ≥ 2, , , ∈ R∗, ∈ R. Bài toán 3.2.7. Tìm số hạng tổng quát của dãy số ( ) thỏa mãn: = 1, = ,∀ ≥ 2. Bài toán 3.2.8. Tìm số hạng tổng quát của dãy số ( ) thỏa mãn: = 3, = ,∀ ≥ 2 Dạng 3.2.2. Tìm số hạng tổng quát của dãy số ( )cho bởi: = , = + + ,∀ ≥ 1, trong đó , , , , là các số thực cho trước. Bài toán 3.2.9. Tìm số hạng tổng quát của dãy số ( ) thỏa mãn: = 0, = , ∀ ≥ 1. Dạng 3.2.3. Cho ≥ 0. Tìm công thức tổng quát của dãy số ( ) thỏa mãn: = , = + 2 ,∀ ≥ 2 . (3.13) e. Dãy số cho bởi công thức truy hồi dưới dạng khác Bài toán 3.2.10. Tìm công thức tổng quát của dãy số ( ) thỏa mãn: = , = . + . + ,∀ ≥ 2, với − = 1, > 0, > 1. Bài toán 3.2.11. Tìm số hạng tổng quát của dãy số ( ) thỏa mãn: = , = ,∀ ≥ 2, với − = 1, > 0, > 1. 21 Bài toán 3.2.12. Tìm số hạng tổng quát của dãy số ( ) thỏa mãn: = , = , = + ,∀ ≥ 3, với ∈ R; , ∈ R∗. Bài toán 3.2.13. Tìm số hạng tổng quát của dãy số ( ) thỏa mãn: = , = = + 2 − + + (∀ ≥ 3). Bài toán 3.2.14. Tìm số hạng tổng quát của dãy số ( ) thỏa mãn = 1, = , = . (∀ ≥ 3) 3.2.2. Tính tổng của một dãy số Bài toán 3.2.15 Tính tổng = 1 + 3 + 5 + ⋯+ 2 − 1, với mọi ∈ N, ≥ 1. Bài toán 3.2.16 Tính tổng = 1 + 2 + 3 + ⋯+ , với mọi ∈ N, ≥ 1. Bài toán 3.2.17 Tính tổng = 1 + 2 + 3 + ⋯+ , với mọi ∈ N, ≥ 1. Bài toán 3.2.18. Tính tổng = 1.2.3 + 2.3.4 + ⋯+ . ( + 1). ( + 2), ∈ N, ≥ 1. Bài toán 3.2.19. Cho dãy ( ) thỏa mãn: = 23 = 2(2 − 1) + 1 ∀ ≥ 2. Tính tổng của 2001 số hạng đầu tiên của dãy ( ). 3.3. ỨNG DỤNG TRONG SỐ HỌC Bài toán 3.3.1. Cho dãy số ( ) xác định bởi: = 1, = 2, = 2 − + 2 với mọi ≥ 3. Chứng minh rằng: ∀ , . cũng là một số hạng của dãy số. 22 Bài toán 3.3.2. Cho dãy số ( ) thỏa mãn = 1, = 0, = 2 − + 2,∀ ≥ 2 Chứng minh là một số chính phương. Bài toán 3.3.3. Cho dãy số ( ) được xác định như sau: = 2 + √3 − 2 − √3 2√3 ; = 0, 1, 2 a. Chứng minh là số nguyên, ∀ = 0, 1, 2 b. Tìm tất cả các số hạng của dãy chia hết cho 3. Bài toán 3.3.4. Cho dãy số ( ) thỏa mãn: = 2, = 2 + 1 + 2 . a. Tính . b. Tìm phần nguyên của tổng sau: = . Bài toán 3.3.5. Cho dãy số ( ) thỏa mãn các điều kiện sau: i. = 0, = 1, = 0, ii. Với mọi ≥ 3, = ( − 5 + 7)( − 2) − 3 + ( − 5 + 7) − − 2 + 3 . Chứng minh là số chính phương với mọi ≥ 0. 3.4. ỨNG DỤNG GIẢI PHƯƠNG TRÌNH SAI PHÂN Việc giải phương trình sai phân thực chất là giải công thức truy hồi. Bài toán 3.4.1. Giải phương trình sai phân = 17 = 2 − + 2 + 1 + 6. 2 . 23 Bài toán 3.4.2. Giải phương trình sai phân = 1; = 1 2 − 5 + 2 = − 2 + 3. 3.5. ỨNG DỤNG TÍNH TÍCH PHÂN Những bài toán tích phân truy hồi ở bậc THPT thường yêu cầu biểu diễn tích phân theo và là các công thức truy hồi tuyến tính. Giải các công thức truy hồi đó ta tìm được . Bài toán 3.6.1. Cho = cos( )5 − 4cos ( ∈ N, ≥ 3). Chứng minh = 52 − . Tính với = 24 , = 48 . Bài toán 3.6.2. Tính tích phân = cos . cos( ) , = ( ∈ N∗). 24 KẾT LUẬN Đề tài: “Ứng dụng công thức truy hồi giải toán sơ cấp” đã xây dựng được lý thuyết về công thức truy hồi và đưa ra các ứng dụng của công thức truy hồi trong việc giải toán sơ cấp tương đối đầy đủ. Đề tài đã nêu được các phương pháp giải công thức truy hồi như: phương pháp lặp, phương pháp hàm sinh, dùng phương trình đặc trưng, tuyến tính hóa các công thức truy hồi phi tuyến và có thể sử dụng phần mềm tin học Maple. Đề tài đã nghiên cứu được các ứng dụng của công thức truy hồi trong giải toán sơ cấp như: tìm số hạng tổng quát và tính tổng của một dãy số, giải một số phương trình sai phân tuyến tính. Ứng dụng trong một số bài toán số học và các bài tích phân truy hồi. Tuy nhiên, do thời gian và khả năng còn hạn chế nên đề tài chưa nghiên cứu sâu và rộng các phương pháp khác giải công thức truy hồi. Đề tài chưa nghiên cứu được ứng dụng của công thức truy hồi trong việc giải các bài toán phức tạp và các bài toán tin học. Đây là một chủ đề khá hay, là một trong những hướng mở để tôi tiếp tục phát triển.