Đăng ký Đăng nhập
Trang chủ Luận văn thạc sĩ toán học phương pháp quy nạp trong các bài toán tổ hợp (1)...

Tài liệu Luận văn thạc sĩ toán học phương pháp quy nạp trong các bài toán tổ hợp (1)

.PDF
57
268
145

Mô tả:

Lời cảm ơn Tôi xin bày tỏ lòng biết ơn sâu sắc đến GS.TSKH Hà Huy Khoái, đã định hướng chọn đề tài và nhiệt tình hướng dẫn để tôi có thể hoàn thành luận văn này. Tôi cũng xin bày tỏ lòng biết ơn chân thành tới Phòng Sau đại học, các thầy cô giáo giảng dạy chuyên ngành Phương pháp Toán sơ cấp, trường Đại học Thăng Long đã giúp đỡ tôi trong suốt quá trình học tập tại trường. Nhân dịp này tôi cũng xin gửi lời cảm ơn đến gia đình, bạn bè đã cổ vũ, động viên để tôi hoàn thành luận văn này. Hà Nội, tháng 4 năm 2016 Tác giả Lê Thị Thọ Lời cam đoan Tôi xin cam đoan, dưới sự chỉ bảo và hướng dẫn của GS.TSKH Hà Huy Khoái, luận văn chuyên ngành Toán Đại số với đề tài:”Phương pháp quy nạp trong các bài toán tổ hợp” được hoàn thành bởi sự nhận thức và tìm hiểu của bản thân tác giả. Trong quá trình nghiên cứu và thực hiện luận văn, tác giả đã kế thừa những kết quả của các nhà khoa học với sự trân trọng và biết ơn. Hà Nội, tháng 4 năm 2016 Tác giả Lê Thị Thọ Thang Long University Library Mục lục Mở đầu 4 1 PHƯƠNG PHÁP QUY NẠP TOÁN HỌC 7 1.1 Phương pháp quy nạp toán học . . . . . . . . . . . . . . . 7 1.2 So sánh và đánh giá . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Chứng minh các đồng nhất thức và bất đẳng thức nhờ quy nạp toán học . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4 Bài toán của Fibonacci . . . . . . . . . . . . . . . . . . . . 16 1.5 Một số đồng nhất thức . . . . . . . . . . . . . . . . . . . . 19 2 QUY NẠP VÀ CÁC BÀI TOÁN TỔ HỢP 22 2.1 Số tập con . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2 Dãy số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Số tập con có thứ tự 2.4 Số tập con có kích thước cho trước . . . . . . . . . . . . . . 26 2.5 Bao hàm - Loại trừ . . . . . . . . . . . . . . . . . . . . . . 29 2.6 Một số bài toán tổ hợp . . . . . . . . . . . . . . . . . . . . 32 2.7 . . . . . . . . . . . . . . . . . . . . . 25 2.6.1 Nguyên lý chuồng chim bồ câu . . . . . . . . . . . . 32 2.6.2 Nghịch lý anh em sinh đôi và hàm Logarit . . . . . . 35 2.6.3 Cách chia quà . . . . . . . . . . . . . . . . . . . . . 40 2.6.4 Giải một số bài toán tổ hợp . . . . . . . . . . . . . . 41 Hệ số nhị thức và tam giác Pascal . . . . . . . . . . . . . . 48 2 2.7.1 Tam giác Pascal . . . . . . . . . . . . . . . . . . . . 50 2.7.2 Công thức trong tam giác Pascal . . . . . . . . . . . 51 Kết luận 55 Tài liệu tham khảo 56 3 Thang Long University Library MỞ ĐẦU 1. Lý do chọn đề tài Học sinh ở các trường THPT hầu như chưa được học cơ bản về tổ hợp. Không chỉ quan trọng đối với kỳ thi học sinh giỏi, mà tổ hợp là một phần không thể thiếu cho những ai muốn tiếp tục học tập, nghiên cứu và làm việc có hiệu quả trong những ngành như Toán học, Tin học, Kỹ thuật, hay đơn giản chỉ là để trau dồi tư duy logic, điều mà ai cũng cần trong cuộc sống. Trong những cố gắng nâng cao trình độ về tổ hợp cho học sinh, một việc làm quan trọng là cung cấp cho giáo viên và học sinh những tài liệu tốt về môn này. Yêu cầu đặt ra là tài liệu đó phải trình bầy những kiến thức cơ bản nhất theo cách tự nhiên, bản chất và dễ hiểu nhất, để học sinh cảm thấy tổ hợp không quá khó. Khi có những kiến thức cơ bản và chắc chắn, học sinh sẽ tiếp cận bài toán khó một cách dễ dàng. Trong tư duy khoa học, phân tích không phải là phương pháp duy nhất. Ngay trong toán học tính toán, không phải khi nào cũng chứng minh được chặt chẽ quá trình tính toán hội tụ, mà việc áp dụng dựa trên sự kiện là chúng thường cho các kết quả phù hợp với thực tế. Những kết quả từ quan sát và kinh nghiệm còn được sử dụng rộng rãi hơn trong những ngành khoa học như Vật lý, Hóa học, Sinh học. Trong những ngành đó, bên cạnh phân tích, người ta sử dụng một cách rộng rãi những lập luận quy nạp. Chữ quy nạp có nghĩa là những kết luận được rút ra trên cơ sở quan sát, kinh nghiệm, tức là nhận thức bằng con đường đi từ cái riêng rẽ đến cái 4 tổng quát. Vai trò của kết luận quy nạp là rất lớn. Nó cho những xuất phát điểm để từ đó, bằng con đường phân tích người ta rút ra những lý thuyết sâu hơn. Vì những lý do trên tôi chọn đề tài: Phương pháp quy nạp trong các bài toán tổ hợp. Khi nghiên cứu và thực hiện đề tài bản thân tôi sẽ hiểu rõ hơn về quy nạp toán học và các bài toán tổ hợp. Từ đó có thêm kiến thức để hướng dẫn học sinh học tập tốt môn học này. Chúng tôi không có ý định sưu tầm những bài toán khó, mà gần như ngược lại, phân tích ý tưởng quy nạp dựa trên những bài toán tương đối dễ. Mục tiêu là giúp học sinh hiểu được rằng, quy nạp là phương pháp phát hiện ra các mệnh đề toán học chưa biết, chứ không đơn thuần như quan điểm rộng rãi hiện nay là quy nạp chỉ dùng để chứng minh mệnh đề cho trước, bằng cách chứng minh "đã đúng đến k thì đúng đến k + 1”. 2. Mục đích nghiên cứu Đề tài nhằm nghiên cứu phương pháp chứng minh quy nạp toán học và các bài toán tổ hợp. 3. Nhiệm vụ nghiên cứu Nghiên cứu các bài toán tổ hợp trong chương trình THPT và một số bài toán nâng cao. 4. Đối tượng và phạm vi nghiên cứu Một số bài toán chứng minh bằng quy nạp toán học, các bài toán tổ hợp. 5 Thang Long University Library 5. Phương pháp nghiên cứu Sử dụng các kiến thức toán Đại số. Tổng hợp, phân tích 6. Dự kiến đóng góp mới Trình bầy một cách khoa học và dễ hiểu các nội dung liên quan đến đề tài để đồng nghiệp và học sinh có thể tham khảo. 6 Chương 1 PHƯƠNG PHÁP QUY NẠP TOÁN HỌC 1.1 Phương pháp quy nạp toán học Bây giờ ta tìm hiểu các công cụ quan trọng nhất trong toán rời rạc. Ta bắt đầu bằng câu hỏi: Cộng n số lẻ đầu tiên lại ta thu được số bằng bao nhiêu? Có lẽ cách tốt nhất là ta thử tìm câu trả lời bằng thực nghiệm. Thử với các giá trị n nhỏ, thì thứ ta tìm được là: 1=1 1+3=4 1+3+5=9 1 + 3 + 5 + 7 = 16 1 + 3 + 5 + 7 + 9 = 25 1 + 3 + 5 + 7 + 9 + 11 = 36 1 + 3 + 5 + 7 + 9 + 11 + 13 = 49 7 Thang Long University Library 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 = 81 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 = 100 Dễ dàng nhận thấy ta thu được các số chính phương; thật ra, dường như từ các ví dụ trên ta có tổng của n số lẻ đầu tiên là n2 . Ta đã thấy điều này với 10 giá trị n đầu tiên; liệu ta có chắc chắn điều này đúng với mọi giá trị? Vâng, tôi muốn nói rằng chúng ta có thể chắc chắn, nhưng trong toán học thì tin rằng "chắc chắn đúng" chưa đủ. Làm thế nào chúng ta có thể chứng minh khẳng định trên? Xét tổng với số n tổng quát. Số lẻ thứ n là 2n − 1, nên ta thử chứng minh rằng 1 + 3 + · · · + (2n − 3) + (2n − 1) = n2 . (1.1) Nếu ta tách số hạng cuối cùng, ta còn lại tổng của (n − 1) số lẻ đầu tiên  1 + 3 + · · · + (2n − 3) + (2n − 1) = 1 + 3 + · · · + (2n − 3) + (2n − 1). Bây giờ, tổng trong dấu ngặc lớn là (n − 1)2 , vì nó là tổng của (n − 1) số lẻ đầu tiên. Do đó toàn bộ tổng bằng (n − 1)2 + (2n − 1) = (n2 − 2n + 1) + (2n − 1) = n2 , (1.2) chính là điều ta cần chứng mình. Điều mà ta đã dùng là khẳng định về tổng của n − 1 số lẻ đầu tiên; và ta biện luận (trong (1.2)) rằng điều này chứng minh khẳng định về tổng của n số lẻ đầu tiên. Nói cách khác, điều mà chúng ta thực sự làm là chỉ ra: nếu khẳng định đúng với một giá trị nhất định (n − 1), thì nó cũng đúng với giá trị tiếp theo (n). 8 Điều đó là đủ để kết luận rằng khẳng đúng với mọi n. Ta đã thấy nó đúng với n = 1; nên theo trên, nó cũng đúng với n = 2 (ta đã thấy điều này bằng tích toán trực tiếp, nhưng việc đó không thực sự cần thiết: nó được suy ra trừ trường hợp n = 1). Theo cách tương tự, tính đúng đắn của khẳng định với n = 2 kéo theo nó cũng đúng với n = 3, và đến lượt nó lại kéo theo tính đúng đắn với n = 4, v.v.. Nếu ta lặp lại điều này đủ nhiều, ta thu được tính đúng đắn với giá trị n bất kỳ. Do đó khẳng định trên là đúng với mọi giá trị n. Kỹ thuật chứng minh này được gọi là quy nạp (hoặc đôi khi gọi là quy nạp toán học, để phân biệt với khái niệm trong triết học). Nó được tóm tắt lại như sau. Giả sử rằng ta muốn chứng minh một tính chất của các số nguyên dương. Giả sử thêm ta có thể chứng minh hai điều: (a) số 1 có tính chất đó, và (b) bất cứ khi nào n − 1 có tính chất đó thì n cũng có tính chất đó (n > 1). Nguyên lý quy nạp nói rằng nếu (a) và (b) đúng, thì mọi số tự nhiên có tính chất như vậy. Điều này chính là những gì ta làm ở trên. Ta đã chỉ ra “tổng” của số lẻ đầu tiên là 12 , và tiếp theo ta chỉ ra nếu tổng của n − 1 số lẻ đầu tiên là (n − 1)2 , thì tổng của n số lẻ đầu tiên là n2 , với mọi số nguyên n > 1. Do đó, theo Nguyên lý quy nạp ta có thể kết luận rằng với mọi số nguyên dương n, tổng của n số lẻ đầu tiên là n2 . Thông thường, cách tốt nhất để thử tiến hành chứng minh bằng phương pháp quy nạp là như sau. Đầu tiên ta chứng minh phát biểu đúng với n = 1. (Việc này đôi khi được gọi là trường hợp cơ sở.) Tiếp theo ta thử chứng 9 Thang Long University Library minh phát biểu cho giá trị tổng quát của n, và ta được phép giả sử rằng phát biểu là đúng nếu n được thay bằng n − 1. (Việc này được gọi là giả thiết quy nạp.) Nếu cần thiết, ta cũng có thể dùng tính đúng đắn của phát biểu với n − 2, n − 3, v.v. và một cách tổng quát, với mọi k sao cho k < n. Đôi khi ta nói rằng nếu 1 có tính chất nào đó, và mọi số nguyên n thừa hưởng tính chất đó của n − 1, thì mọi số nguyên dương có tính chất đó. (Cũng giống như nếu người bố của một gia đình có một khoản tài sản, và mọi thế hệ sau này thừa kế tài sản đó từ thế hệ trước, thì gia đình luôn luôn có tài sản này). Thỉnh thoảng ta không bắt đầu với n = 1 mà bắt đầu với n = 0 (nếu điều này có nghĩa) hoặc có thể với một giá trị lớn hơn (chẳng hạn, nếu n = 1 không có ý nghĩa gì với lý do nào đó, hoặc phát biểu không dùng cho trường hợp n = 1). Ví dụ, ta muốn chứng minh rằng n! là một số chẵn nếu n > 1. Ta kiểm tra thấy điều này đúng với n = 2 (thật vậy, 2! = 2 là số chẵn), và n được thừa kế tính chất này từ n − 1 (thật vậy, nếu (n − 1)! là số chẵn, thì n! = n · (n − 1)! cũng là số chẵn). Điều này chứng minh rằng n! là số chẵn với mọi n bắt đầu từ trường hợp cơ sở n = 2. Tất nhiên, khẳng định là sai với n = 1. Bài toán 1.1.1. Chứng minh bằng quy nạp và không bằng quy nạp rằng n(n + 1) luôn là số chẵn với mọi số nguyên dương n. Bài toán 1.1.2. Chứng minh bằng quy nạp rằng tổng của n số nguyên dương đầu tiên là n(n + 1)/2. Bài toán 1.1.3. Nhận xét rằng n(n + 1)/2 là số cái bắt tay giữa n + 1 người. Giả sử rằng tất cả mọi người chỉ đếm số bắt tay với người nhiều tuổi hơn mình (khá là lố bịch, phải không?). Ai là người có số bắt tay nhiều nhất? Có bao nhiêu người có 6 cái bắt tay? (Chúng ta giả sử rằng không có hai người nào bằng tuổi). 10 Dựa vào kết quả của bài tập 1.1.2 chứng minh các kết quả của bạn. Chúng ta thường dùng chữ “v.v.”: để miêu tả một số lập luận mà phải lặp n lần mới thu được kết quả ta cần, nhưng sau khi lập luận một hoặc hai lần, ta nói “v.v.” thay vì tiếp lục lặp lại. Không có gì là sai ở đây, nếu lập luận đủ đơn giản thì ta có một cách trực quan thấy những chỗ mà phép lặp bắt đầu. Nhưng sẽ tốt hơn nếu có thể dùng một số công cụ thay vì “v.v.” trong trường hợp mà kết quả của phép lặp không quá rõ ràng. Cách chính xác để làm điều này là dùng phép quy nạp. Giả sử ta chứng minh công thức tính số tập con của một tập n phần tử (đáp án là 2n ). Nguyên lý quy nạp cho ta biết ta phải kiểm tra khẳng định đúng với n = 0. Việc này là rõ ràng. Tiếp theo, ta giả sử rằng n > 0 và khẳng định đúng với các tập có n − 1 phần tử. Xét tập S có n phần tử, và cố định một phần tử bất kỳ a ∈ S. Ta muốn đếm số tập con của S. Ta chia chúng thành hai lớp: lớp chứa a và lớp không chứa a. Ta đếm chúng một cách tách biệt. Đầu tiên, ta giải quyết với các tập con mà không chứa a. Nếu ta xóa a khỏi S, ta còn lại tập con S 0 có n − 1 phần tử, và các tập con ta quan tâm chính là các tập con của S 0 . Theo giả thiết quy nạp, số tập con như vậy là 2n−1 . Thứ hai, ta xét các tập con chứa a. Nhận xét mấu chốt là mỗi tập con như vậy chứa a và một tập con của S 0 . Ngược lại, nếu ta lấy bất kỳ tập con của S 0 , ta có thể thêm a vào nó để thu được một tập con của S chứa a. Do đó số tập con của S chứa a bằng số tập con của S 0 , mà theo giả thiết quy nạp bằng 2n−1 . Kết luận: Tổng số tập con của S là 2n−1 + 2n−1 = 2 · 2n−1 = 2n . Đ. p. c. m 11 Thang Long University Library 1.2 So sánh và đánh giá Thật tốt nếu có công thức tính các số nhất định (ví dụ, có n! hoán vị của n phần tử), nhưng quan trọng hơn là phải có một ý tưởng sơ bộ về độ lớn những con số này. Ví dụ, số 100! có bao nhiêu chữ số?  Ta bắt đầu với các câu hỏi đơn giản hơn. Số nào lớn hơn, n hay n2 ?  Với n = 2, 3, 4 giá trị n2 là 1, 3, 6, nên nó nhỏ hơn n với n = 2, bằng   nhau với n = 3 và lớn hơn với n = 4. Thật ra, n = n1 < n2 nếu n ≥ 4. Còn nhiều điều để nói hơn: Thương  n n−1 2 = n 2 trở lên lớn tùy ý khi n đủ lớn; ví dụ nếu ta muốn thương này lớn hơn 1000, ta có thể chọn n > 2001. Theo ngôn ngữ của giải tích, ta có  n 2 → ∞ (n → ∞). n Dưới đây là một câu hỏi đơn giản khác: Số nào lớn hơn, n2 hay 2n ? Với giá trị n nhỏ, có thể có các kiểu khác nhau: 12 < 21 , 22 = 22 , 32 > 23 , 42 = 24 , 52 < 25 . Nhưng từ đây trở đi, 2n cất cánh và tăng nhanh hơn n2 . Ví dụ 210 = 1024 lớn hơn nhiều so với 102 = 100. Thật ra 2n /n2 lớn tùy ý với n đủ lớn. Bài toán 1.2.1. (a) Chứng minh rằng 2n > n 3  nếu n ≥ 3. (b) Dùng (a) để chứng minh 2n /n2 lớn tùy ý khi n đủ lớn. Bây giờ ta giải quyết vấn đề ước lượng số 100!, hay tổng quát hơn, n! = 1 · 2 · · · n. Nhân tử 1 đầu tiên không ảnh hưởng gì, nhưng tất cả các nhân tử khác đều ít nhất là 2, nên n! ≥ 2n−1 . Tương tự n! ≤ nn−1 , vì (bỏ qua nhân tử 1) n! là tích của n − 1 nhân tử, mỗi trong số đó đều nhỏ hơn 12 n. (Vì tất cả trừ một trong số chúng nhỏ hơn n, nên tích nhỏ hơn nhiều.) Do vậy ta biết rằng 2n−1 ≤ n! ≤ nn−1 . (1.3) Các cận này cách nhau khá xa, với n = 10, cận dưới là 29 = 512, trong khi cận trên là 109 (một tỉ). Dưới đây là một câu hỏi vẫn chưa được trả lời bằng các ước lượng trong (1.3). Số nào lớn hơn, n! hay 2n ? Nói cách khác, tập với n phần tử có số phép hoán vị nhiều hơn số tập con hay không? Với các giá trị n nhỏ, số tập con thắng nhiều hơn: 21 = 2 > 1! = 1, 22 = 4 > 2! = 2, 23 = 8 > 3! = 6. Nhưng từ đây thì lại đổi chiều: 24 = 16 < 4! = 24, 25 = 32 < 5! = 120. Dễ thấy rằng khi n tăng, n! tăng nhanh hơn 2n : Nếu ta đi từ n tới n + 1, thì 2n tăng với hệ số 2, trong khi n! tăng với hệ số n + 1. Bài toán 1.2.2. Dùng phép quy nạp để chính xác hoá phát biểu trên và chứng minh rằng n! > 2n nếu n ≥ 4. Dưới đây là công thức đưa ra phép xấp xỉ rất tốt cho n!. Ta phát biểu nó mà không chứng minh, vì chứng minh (mặc dù không hoàn toàn khó) cần đến giải tích. Định lý 1.2.1. [Công thức Stirling]  n n √ 2πn. n! ∼ e Ở đây π = 3.14... là diện tích của hình tròn có bán kính bằng 1, e = 2.718... là cơ sở của hàm logarit tự nhiên, và ∼ có nghĩa là phép xấp xỉ theo nghĩa n! √  n n e 2πn → 1 (n → ∞). Cả hai số vô tỉ siêu việt e và π xuất hiện trong cùng một công thức! 13 Thang Long University Library Ta quay trở lại câu hỏi: Số 100! có bao nhiêu chữ số? Theo công thức Stirling ta biết rằng 100! ≈ (100/e)100 · √ 200π. Số chữ số của số này là logarit cơ số 10 của nó được làm tròn. Do đó ta có lg(100!) ≈ 100 lg(100/e) + 1 + lg √ 2π = 157.969... Nên số chữ số trong số 100! là vào khoảng 158 (thật ra đây là giá trị đúng). 1.3 Chứng minh các đồng nhất thức và bất đẳng thức nhờ quy nạp toán học Phương pháp quy nạp toán học cho phép chứng minh các đồng nhất thức và bất đẳng thức mà một hoặc hai vế của chúng phụ thuộc số tự nhiên n. Chẳng hạn, trước tiên có thể kiểm tra rằng đồng nhất thức cần chứng minh đúng khi n = 1, sau đó viết đồng nhất thức khi n = k + 1 và n = k rồi trừ từng vế hai đồng nhất thức nhận được. Nếu làm như vậy mà thấy hiệu các vế trái của các đồng nhất thức bằng hiệu các vế phải, thì do đồng nhất thức đúng với n = k, ta suy ra đồng nhất thức đúng với n = k + 1, và như vậy do quy nạp toán học, đồng nhất thức đúng với mọi giá trị n. Chẳng hạn, ta sẽ chứng minh rằng, với mọi n đồng nhất thức sau đây nghiệm đúng: Bài toán 1.3.1. Chứng minh rằng với mọi số nguyên dương n ta có 1− 1 1 1 1 1 1 1 1 + − + ... + − = + + ... + 2 3 4 2n − 1 2n n + 1 n + 2 2n Chứng minh. 14 (1.3.1) Khi n = 1, đồng nhất thức có dạng 1 − 1 2 = 1 2 đúng. Bây giờ ta viết đồng nhất thức khi n = k và khi n = k + 1 1− 1 1 1 1 1 1 + ... + − = + + ... + , 2 2k − 1 2k k+1 k+2 2k (1.3.1.1) 1 1 1 1 1 1 1 1 1− +...− + − = +...+ + + , (1.3.1.2) 2 2k 2k + 1 2(k + 1) k + 2 2k 2k + 1 2k + 2 Trừ từng vế các đồng nhất thức này cho nhau ta được 1 1 1 1 1 − = + − , 2k + 1 2(k + 1) 2k + 1 2k + 2 k + 1 hay là 2 1 = . 2(k + 1) k + 1 đúng. Điều đó có nghĩa là nếu (1.3.1.1) đúng thì (1.3.1.2) đúng, do đó theo quy nạp toán học đồng nhất thức (1.3.1) đúng với mọi số tự nhiên n.  Hoàn toàn như vậy ta chứng minh được khẳng định sau đây, được gọi là bất đẳng thức Bernoulli: Bài toán 1.3.2. Nếu x > −1 thì mọi số tự nhiên n bất đẳng thức sau đây nghiệm đúng: (1 + x)n ≥ 1 + nx. (1.3.2). Chứng minh. Thật vậy, khi n = 1 ta có bất đẳng thức đúng 1+x≥1+x . Giả sử (1 + x)k ≥ 1 + kx. Vì theo giả thiết 1 + x > 0 nên bất đẳng thức vấn đúng khi nhân cả hai vế với 1 + x ta nhận được (1 + x)k+1 ≥ (1 + kx)(1 + x) . 15 Thang Long University Library hay (1 + x)k+1 ≥ 1 + (k + 1)x + kx2 . Do kx2 ≥ 0 nên từ đó suy ra (1 + x)k+1 ≥ 1 + (k + 1)x . Theo quy nạp toán học ta kết luận được rằng bất đẳng thức (1.3.2) đúng với mọi số tực nhiên n 1.4  Bài toán của Fibonacci Vào thế kỉ XIII, nhà toán học người Italia Leonardo Fibonacci nghiên cứu câu hỏi sau: Một người nông dân nuôi các con thỏ. Sau hai tháng tuổi, mỗi con thỏ sinh ra một thỏ con, và sau đó cứ mỗi tháng lại sinh một con. Giả sử các con thỏ không bao giờ chết, và ta xem là không có thỏ đực. Hỏi người nông dân có bao nhiêu con thỏ sau n tháng nếu ông ta bắt đầu bằng một con thỏ mới sinh? Ta dễ dàng hình dung ra đáp án với các giá trị n nhỏ. Người nông dân có một con thỏ trong tháng đầu tiên và một con thỏ trong tháng thứ hai, vì con thỏ cần đủ hai tháng tuổi trước khi nó biết đẻ. Người nông dân có 2 thỏ trong thang thứ ba, và ba con thỏ trong tháng thứ tư, vì con thỏ đầu tiên sinh ra một con sau tháng thứ hai. Sau 4 tháng, con thỏ thứ hai cũng sinh một con thỏ mới, nên hai con thỏ con được thêm vào. Điều này có nghĩa người nông dân có 5 con thỏ sau tháng thứ 5. Dễ dàng suy ra quy tắc tăng trưởng đàn thỏ với số tháng bất kỳ, nếu ta chú ý rằng số thỏ mới sinh trong mỗi tháng chính bằng số thỏ ít nhất hai tháng tuổi, tức là, những con đã có ở tháng trước. Nói cách khác, để tính số thỏ trong tháng tiếp theo, ta phải cộng thêm số thỏ trong tháng trước 16 đó vào số thỏ trong tháng hiện tại. Việc này giúp ta dễ dàng tính lần lượt số thỏ: 1, 1, 1 + 1 = 2, 2 + 1 = 3, 3 + 2 = 5, 5 + 3 = 8, 8 + 5 = 13, . . . (Có vẻ Fibonacci không thực sự coi câu hỏi của ông như bài toán áp dụng thực tế; ông làm việc với các con số, chú ý rằng việc này sinh ra các con số mới đối với ông, nhưng lại có các tính chất thú vị, như ta sẽ thấy về sau). Để viết điều này thành công thức, ta ký hiệu Fn là số thỏ trong tháng thứ n. Khi đó ta có, với n = 2, 3, 4, . . ., Fn+1 = Fn + Fn−1 . (1.4) ta cũng biết rằng F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5. Để cho tiện, ta ký hiệu F0 = 0; khi đó phương trình (1.4) vẫn đúng với n = 1, giống như định nghĩa của các số này. Điều này có gì đó có vẻ không bình thường: thay vì nói cho ta biết Fn là cái gì (theo công thức), ta chỉ đưa ra quy tắc tính mỗi số Fibonacci từ hai số liền trước, và chỉ rõ hai giá trị đầu tiên. Định nghĩa như thế này được gọi là phép truy hồi. Nó khá giống phép quy nạp (ngoại trừ đây không phải là một kỹ thuật chứng minh, mà là một phương pháp định nghĩa), và đôi khi được gọi là định nghĩa bằng quy nạp. Bài toán 1.4.1. Tại sao ta phải chỉ rõ hai giá trị đầu tiên? Tại sao không phải là một hoặc ba? Trước khi thảo luận thêm về các số này, ta xét một bài toán đếm khác: Một cầu thang có n bậc. Bạn đi lên theo từng bậc một hoặc 2 bậc. Hỏi có bao nhiêu cách để bạn đi lên? Với n = 1, chỉ có một cách. Với n = 2, bạn có 2 lựa chọn: đi hai lần bước đơn hoặc đi một lần bước kép. Với n = 3, ta có ba cách: ba lần bước 17 Thang Long University Library đơn, hoặc một bước đơn rồi một bước kép, hoặc một bước kép rồi một bước đơn. Ta dừng lại và thử đoán đáp án tổng quát! Nếu bạn dự đoán số cách đi lên với n bậc là n cách, bạn đã sai. Trường hợp tiếp theo, n = 4, có 5 cách (1 + 1 + 1 + 1, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, 2 + 2). Nên thay vì dự đoán, ta thử cách sau. Ký hiệu Jn là đáp án. Ta thử hình dung Jn+1 bằng bao nhiêu, giả sử ta biết giá trị của Jk với 1 ≤ k ≤ n. Nếu ta bắt đầu bằng một bước đơn, ta có Jn cách để đi tiếp n bước còn lại. Nếu bắt đầu bằng một bước kép, ta có Jn−1 cách đi lên n − 1 bước còn lại. Nên tất cả có Jn+1 = Jn + Jn−1 . Câu hỏi này cũng tương tự như câu hỏi ta đã dùng để tính dãy số Fibonacci Fn . Điều này có phải có nghĩa là Fn = Jn ? Tất nhiên là không rồi, như ta thấy ở các giá trị ban đầu: Ví dụ, F3 = 2 nhưng J3 = 3. Tuy nhiên, dễ thấy rằng tất cả những gì xảy ra là Jn bị di chuyển thành Fn+1 . Điều này đúng với n = 1, 2, và nên tất nhiên đúng với mọi n, vì các dãy F2 , F3 , F4 , . . . và J1 , J2 , J3 , . . . được tính toán bằng quy tắc giống nhau từ giá trị của hai phần tử ban đầu. Bài toán 1.4.2. Bạn có n đô la để tiêu. Mỗi ngày bạn mua một viên kẹo với giá 1 đô la hoặc một cây kem với giá 2 đô la. Hỏi bạn có bao nhiêu cách tiêu chỗ tiền này? 18 1.5 Một số đồng nhất thức Có rất nhiều công thức thú vì về dãy Fibonacci. Ví dụ, tổng của n số Fibonacci đầu tiên bằng bao nhiêu? Ta có 0 = 0, 0 + 1 = 1, 0 + 1 + 1 = 2, 0 + 1 + 1 + 2 = 4, 0 + 1 + 1 + 2 + 3 = 7, 0 + 1 + 1 + 2 + 3 + 5 = 12, 0 + 1 + 1 + 2 + 3 + 5 + 8 = 20, 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33. Bắt đầu bằng các số này, không khó để nhận ra rằng bằng cách cộng thêm 1 vào vế phải ta thu được dãy số Fibonacci, thật ra, ta được số Fibonacci sau hai bước của số hạng cuối cùng. Ta có F0 + F1 + F2 + · · · + Fn = Fn+2 − 1. Tất nhiên, tại thời điểm này thì đây mới chỉ là một khẳng định, một phát biểu toán học chưa được chứng minh mà ta tin là đúng. Để chứng minh nó, ta dùng phép quy nạp theo n (vì dãy Fibonacci được xác định bằng phép truy hồi, phép quy nạp là tự nhiên, và thường là phương pháp chứng minh duy nhất). Ta đã kiểm tra công thức đúng với n = 0 và 1. Giả sử rằng công thức đúng với n − 1 số Fibonacci đầu tiên. Xét tổng của n số Fibonacci đầu tiên: F0 + F1 + . . . + Fn = (F0 + F1 + . . . + Fn−1 ) + Fn = (Fn+1 − 1) + Fn , 19 Thang Long University Library
- Xem thêm -

Tài liệu liên quan

Tài liệu vừa đăng