Luận văn: Phương pháp quy nạp trong các bài toán tổ hợp

Lời cảm ơn<br /> Tôi xin bày tỏ lòng biết ơn sâu sắc đến GS.TSKH Hà Huy Khoái, đã<br /> định hướng chọn đề tài và nhiệt tình hướng dẫn để tôi có thể hoàn thành<br /> luận văn này.<br /> <br /> 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<br /> thầy cô giáo giảng dạy chuyên ngành Phương pháp Toán sơ cấp, trường<br /> Đại học Thăng Long đã giúp đỡ tôi trong suốt quá trình học tập tại trường.<br /> <br /> 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ũ,<br /> động viên để tôi hoàn thành luận văn này.<br /> Hà Nội, tháng 4 năm 2016<br /> Tác giả<br /> <br /> Lê Thị Thọ<br /> <br /> Lời cam đoan<br /> Tôi xin cam đoan, dưới sự chỉ bảo và hướng dẫn của GS.TSKH Hà Huy<br /> Khoái, luận văn chuyên ngành Toán Đại số với đề tài:”Phương pháp quy<br /> 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à<br /> tìm hiểu của bản thân tác giả.<br /> <br /> Trong quá trình nghiên cứu và thực hiện luận văn, tác giả đã kế thừa<br /> những kết quả của các nhà khoa học với sự trân trọng và biết ơn.<br /> Hà Nội, tháng 4 năm 2016<br /> Tác giả<br /> <br /> Lê Thị Thọ<br /> <br /> Thang Long University Library<br /> <br /> Mục lục<br /> <br /> Mở đầu<br /> <br /> 4<br /> <br /> 1 PHƯƠNG PHÁP QUY NẠP TOÁN HỌC<br /> <br /> 7<br /> <br /> 1.1<br /> <br /> Phương pháp quy nạp toán học<br /> <br /> . . . . . . . . . . . . . . .<br /> <br /> 7<br /> <br /> 1.2<br /> <br /> So sánh và đánh giá . . . . . . . . . . . . . . . . . . . . . . 12<br /> <br /> 1.3<br /> <br /> Chứng minh các đồng nhất thức và bất đẳng thức nhờ quy<br /> nạp toán học . . . . . . . . . . . . . . . . . . . . . . . . . . 14<br /> <br /> 1.4<br /> <br /> Bài toán của Fibonacci . . . . . . . . . . . . . . . . . . . . 16<br /> <br /> 1.5<br /> <br /> Một số đồng nhất thức . . . . . . . . . . . . . . . . . . . . 19<br /> <br /> 2 QUY NẠP VÀ CÁC BÀI TOÁN TỔ HỢP<br /> <br /> 22<br /> <br /> 2.1<br /> <br /> Số tập con . . . . . . . . . . . . . . . . . . . . . . . . . . . 22<br /> <br /> 2.2<br /> <br /> Dãy số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23<br /> <br /> 2.3<br /> <br /> Số tập con có thứ tự<br /> <br /> 2.4<br /> <br /> Số tập con có kích thước cho trước . . . . . . . . . . . . . . 26<br /> <br /> 2.5<br /> <br /> Bao hàm - Loại trừ . . . . . . . . . . . . . . . . . . . . . . 29<br /> <br /> 2.6<br /> <br /> Một số bài toán tổ hợp . . . . . . . . . . . . . . . . . . . . 32<br /> <br /> . . . . . . . . . . . . . . . . . . . . . 25<br /> <br /> 2.6.1<br /> 2.6.2<br /> <br /> Nghịch lý anh em sinh đôi và hàm Logarit . . . . . . 35<br /> <br /> 2.6.3<br /> <br /> Cách chia quà . . . . . . . . . . . . . . . . . . . . . 40<br /> <br /> 2.6.4<br /> 2.7<br /> <br /> Nguyên lý chuồng chim bồ câu . . . . . . . . . . . . 32<br /> <br /> Giải một số bài toán tổ hợp . . . . . . . . . . . . . . 41<br /> <br /> Hệ số nhị thức và tam giác Pascal . . . . . . . . . . . . . . 48<br /> 2<br /> <br /> 2.7.1<br /> <br /> Tam giác Pascal . . . . . . . . . . . . . . . . . . . . 50<br /> <br /> 2.7.2<br /> <br /> Công thức trong tam giác Pascal . . . . . . . . . . . 51<br /> <br /> Kết luận<br /> <br /> 55<br /> <br /> Tài liệu tham khảo<br /> <br /> 56<br /> <br /> 3<br /> <br /> Thang Long University Library<br /> <br /> MỞ ĐẦU<br /> 1. Lý do chọn đề tài<br /> Học sinh ở các trường THPT hầu như chưa được học cơ bản về tổ hợp.<br /> 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<br /> 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<br /> việc có hiệu quả trong những ngành như Toán học, Tin học, Kỹ thuật, hay<br /> đơn giản chỉ là để trau dồi tư duy logic, điều mà ai cũng cần trong cuộc<br /> sống. Trong những cố gắng nâng cao trình độ về tổ hợp cho học sinh, một<br /> 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<br /> 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<br /> 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<br /> sinh cảm thấy tổ hợp không quá khó. Khi có những kiến thức cơ bản và<br /> chắc chắn, học sinh sẽ tiếp cận bài toán khó một cách dễ dàng.<br /> Trong tư duy khoa học, phân tích không phải là phương pháp duy nhất.<br /> Ngay trong toán học tính toán, không phải khi nào cũng chứng minh được<br /> 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à<br /> 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<br /> sát và kinh nghiệm còn được sử dụng rộng rãi hơn trong những ngành<br /> khoa học như Vật lý, Hóa học, Sinh học. Trong những ngành đó, bên cạnh<br /> 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.<br /> 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,<br /> kinh nghiệm, tức là nhận thức bằng con đường đi từ cái riêng rẽ đến cái<br /> 4<br /> <br />