Mục lụcMỞ ĐẦU 21 PHƯƠNG PHÁP QUY NẠP 41.1 Nguyên lý quy nạp . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1.1 Suy diễn và quy nạp . . . . . . . . . . . . . . . . . . . . . . 51.1.2 Một số ví dụ về suy luận quy nạp . . . . . . . . . . . . . . 51.1.3 Nguyên lý quy nạp toán học . . . . . . . . . . . . . . . . . . 71.2 Phương pháp chứng minh quy nạp . . . . . . . . . . . . . . . . . . 81.2.1 Các bước trong phương pháp chứng minh quy nạp . . . . . 91.2.2 Bước quy nạp được xây dựng trên P[k] . . . . . . . . . . . 121.2.3 Bước quy nạp được xây dựng trên P[k+1] . . . . . . . . . 131.3 Một số dạng khác của nguyên lý quy nạp toán học . . . . . . . . . 131.4 Vận dụng phương pháp quy nạp để giải các bài toán phổ thông . 161.4.1 Phương pháp quy nạp trong số học . . . . . . . . . . . . . 161.4.2 Phương pháp quy nạp trong đại số . . . . . . . . . . . . . . 231.4.3 Phương pháp quy nạp trong giải tích . . . . . . . . . . . . 281.4.4 Phương pháp quy nạp trong hình học . . . . . . . . . . . . 351.5 Một số bài tập tự giải . . . . . . . . . . . . . . . . . . . . . . . . . . 412 PHƯƠNG PHÁP PHẢN CHỨNG 432.1 Phương pháp chứng minh bằng phản chứng . . . . . . . . . . . . . 452.1.1 Cơ sở logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.1.2 Mệnh đề phủ định điều cần chứng minh . . . . . . . . . . . 462.1.3 Các bước suy luận trong chứng minh phản chứng . . . . . 482.2 Vận dụng phương pháp phản chứng để giải các bài toán phổ thông 492.2.1 Phương pháp phản chứng trong số học . . . . . . . . . . . 492.2.2 Phương pháp phản chứng trong đại số . . . . . . . . . . . . 532.2.3 Phương pháp phản chứng trong giải tích . . . . . . . . . . 632.2.4 Phương pháp phản chứng trong hình học . . . . . . . . . . 732.3 Một số bài tập tự giải . . . . . . . . . . . . . . . . . . . . . . . . . . 79Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 831MỞ ĐẦUChứng minh là một trong những nét đặc trưng làm cho toán học khác biệtvới các môn khoa học khác. Hiểu và vận dụng các phương pháp, kỹ thuật chứngminh là yêu cầu bắt buộc đối với các em học sinh nói chung và đặc biệt là cácem học sinh giỏi nói riêng. Có rất nhiều phương pháp và kỹ thuật chứng minh:Từ chứng minh trực tiếp tới chứng minh gián tiếp, từ chứng minh bằng quynạp tới chứng minh bằng phản chứng, Phép chứng minh phản chứng và phépchứng minh quy nạp đã xuất hiện từ rất lâu và chúng là những phương phápchứng minh kinh điển, quan trọng nhất của toán học.Chúng ta biết rằng, toán học được xây dựng dựa trên một hệ thống lý thuyếtgồm các tiên đề và định nghĩa. Hệ thống lý thuyết này được xây dựng bằng conđường suy diễn. Trong suốt 2000 năm, hình mẫu của phương pháp suy diễn xâydựng các lý thuyết toán học là của nhà hình học cổ Hy Lạp Euclid đưa ra vàothế kỷ III trước công nguyên. Sau Euclid đã xuất hiện các mô hình hình họcmới. Tuy nhiên, phép suy diễn không phải là con đường duy nhất của tư duykhoa học, kể cả tư duy toán học. Nhà toán học vĩ đại Euclid đã viết: "Trongthực tế, nhiều tính chất của các số đã biết đều được tìm ra bằng phép quy nạpvà được tìm thấy rất lâu trước khi sự đúng đắn của chúng được chứng minh chặtchẽ. Cũng có rất nhiều tính chất quen thuộc với chúng ta nhưng hiện thời chúngta còn chưa chứng minh được. Chỉ có con đường quan sát và tư duy quy nạpmới có thể dẫn chúng ta đến chân lý." Như vậy chỉ các quan trắc thực tế là conđường chủ yếu dẫn đến những chân lý khoa học mới. Ví dụ như nhà toán họcngười Mỹ J. Garfulkel đã dùng máy tính điện tử tính toán trên 700 tam giác cụthể để tìm ra nhiều hệ thức liên hệ mới giữa các yếu tố trong tam giác mà sauđó, ông hay các nhà toán học khác đã chứng minh được tính đúng đắn của mộtsố hệ thức, còn các hệ thức khác hiện nay vẫn được coi là các giả thuyết. Nhưvậy trong Toán học cũng như trong các ngành khoa học khác, một kết quả mớithường được tìm bằng phép quy nạp, dựa vào nhiều quan trắc, nhận xét. Ở đâyta hiểu quy nạp là quá trình đi từ những cái cụ thể đến những cái tổng quát.2MỞ ĐẦUTrong toán học có rất nhiều bài toán nếu chúng ta chứng minh hay giải nótheo một cách thông thường thì không đi tới kết quả, hay những khẳng địnhtoán học dường như rất hiển nhiên nhưng ta không có cách nào để chứng minh.Khi đó phương pháp chứng minh bằng phản chứng là một công cụ đắc lực, quantrọng để ta nghĩ tới. Một ví dụ kinh điển nhất về phép chứng minh phản chứngthuộc về Euclid với phép chứng minh: "Tồn tại vô số số nguyên tố". Euclid đãphủ định điều cần chứng minh tức là "tồn tại hữu hạn số nguyên tố" và từ giảthiết đó sau một loạt các diễn giải, ông suy ra điều mâu thuẫn. Điều mâu thuẫnđó chứng tỏ điều phủ định là sai, khi đó ông khẳng định điều cần chứng minhlà đúng.Trong chương trình toán phổ thông, hai phương pháp chứng minh quy nạpvà chứng minh phản chứng cũng được đề cập tới. Tuy nhiên sách tham khảo vềnhững vấn đề trên rất ít. Tại các kì thi học sinh giỏi toán cấp quốc gia, quốctế có rất nhiều bài phải sử dụng tới hai phương pháp này để giải. Khi giải toánkhông phải lúc nào chúng ta cũng nghĩ tới hai phương pháp đặc biệt trên nên cónhiều học sinh gặp vướng mắc với những bài toán dạng này. Vậy câu hỏi đặt ralà: Phương pháp chứng minh quy nạp và phương pháp chứng minh phản chứnglà thế nào? Chúng ta phải vận dụng hai phương pháp đó như thế nào trong việcgiải các bài toán?Luận văn" Phương pháp quy nạp và phương pháp phản chứngvới các bài toán phổ thông "trình bày một số khái niệm cơ bản, các bước thực hiện trong phương pháp chứngminh quy nạp, chứng minh phản chứng. Từ đó đưa ra các bài toán trong số học,đại số, giải tích, hình học vận dụng hai phương pháp trên để giải.Luận văn gồm hai chương.Chương 1. Phương pháp quy nạpChương này tác giả trình bày về nguyên lý quy nạp toán học, các bước trongchứng minh quy nạp, một số dạng khác của nguyên lý quy nạp, và vận dụngphương pháp chứng minh quy nạp để giải một số bài toán ở phổ thông.Chương 2. Phương pháp phản chứngTrong chương này tác giả trình bày khái niệm, cơ sở logic, các bước trong chứngminh phản chứng và các bài toán ở chương trình phổ thông vận dụng phươngpháp này để giải.3Chương 1PHƯƠNG PHÁP QUY NẠPToán học được xây dựng trên một tập hợp các tiên đề và định nghĩa. Nhữngtiên đề, định nghĩa này là nền tảng cơ bản cho các định lý. Tất cả các định lýđược sáng tạo ra, được chứng minh nhờ sử dụng các tiên đề, định nghĩa hay cácđịnh lý được chứng minh trước đó. Ngược lại, lý thuyết ở hầu hết các ngànhkhoa học khác [ví dụ như định luật Newton về chuyển động trong vật lý ],thường được xây dựng dựa trên kết quả thực nghiệm và có thể không bao giờđược chứng minh là đúng. Các thực nghiệm và quan trắc không đủ để chứng tỏrằng mệnh đề toán học là đúng. Ví dụ như nhà toán học Fermat [1601 - 1665]dự đoán rằng khi n là một số nguyên lớn hơn 2 thì phương trình xn+ yn= znkhông có nghiệm nguyên dương. Các nhà toán học đã cố gắng rất nhiều đểtìm ra một phản ví dụ [tức là một tập các nghiệm nguyên dương] nhưng đềuthất bại. Phải mất hơn ba thế kỷ để tìm lời giải nhưng các nhà toán học vẫnkhông thành công. Tới năm 1994 nhà toán học người Anh Andrew Wiles đã tìmra lời giải. Sẽ là một sai lầm nếu như ta kết luận hoặc dự đoán một mệnh đềtoán học đúng chỉ đơn thuần bằng thực nghiệm. Ví dụ ta có thể dự đoán rằngn2− n + 41 là số nguyên tố với mọi số tự nhiên n. Ta có thể dễ dàng thấy khin = 1, n2−n + 41 = 41 là số nguyên tố, khi n = 2 thì n2−n + 41 = 43 là số nguyêntố. Cứ tiếp tục thử nghiệm cho tới khi n = 10 hoặc n = 20 ta cũng không tìmđược phản ví dụ. Tuy nhiên dễ thấy rằng mệnh đề là sai, vì khi cho n = 41 thìn2− n + 41 = 412không là số nguyên tố. Như vậy những kết quả thực nghiệmlà không đủ để đảm bảo tính đúng đắn cho mệnh đề và chúng cũng không thểkiểm tra được mệnh đề trong tất cả các trường hợp. Ví dụ ta dự đoán tổng củan số tự nhiên lẻ đầu tiên là 1 + 3 + 5 + + [2n − 1] = n2. Tất nhiên ta dễ dàngkiểm tra được mệnh đề là đúng trong một vài giá trị n đầu tiên [như với 100 sốđầu tiên chẳng hạn]. Nhưng chúng ta cũng không thể kết luận mệnh đề là đúng.Có thể nó sai ở một vài giá trị nào đó mà ta không biết. Vậy chúng ta phải kiểm4Chương 1. PHƯƠNG PHÁP QUY NẠPtra mệnh đề bằng cách nào? Công cụ đắc lực ở đây chính là quy nạp toán học.Trong chương này chúng ta sẽ cùng tìm hiểu về phương pháp quy nạp toánhọc và những ứng dụng của nó trong giải toán.1.1 Nguyên lý quy nạp1.1.1 Suy diễn và quy nạpTrong lao động, học tập và sinh hoạt người ta phải suy luận, đánh giá nhữnghoạt động của mình. Thực tế có hai hướng chính để suy luận và đưa ra kết quảtrước một vấn đề cần giải quyết. Những suy luận đó là suy diễn và quy nạp.Suy diễn là quá trình đi từ "tính chất" của tập thể [cái chung] suy ra "tínhchất" của cá thể [cái riêng], hay từ quy tắc chung, tổng quát áp dụng vào từngtrường hợp cụ thể, riêng lẻ.Ví dụ như ta biết một kết luận chung rằng: " Số tự nhiên mà có tổng các chữ sốcủa nó chia hết cho 3 thì số đó cũng chia hết cho 3 ". Như vậy ta suy ra số 2013cũng chia hết cho 3 vì nó có tổng các chữ số là 2 + 0 + 1 + 3 = 6 chia hết cho 3.Quy nạp là quá trình đi từ "tính chất" của một số cá thể [cái riêng] suy ra"tính chất" của tập thể [cái chung], hay từ một vài trường hợp cụ thể rút rakết luận chung, tổng quát. Do đó quá trình này không phải lúc nào cũng đúng.Ví dụ khi quan sát thấy một số kim loại như: sắt, đồng, chì, vàng, bạc, đềucó thể rắn, người ta đã quy nạp và rút ra kết luận: " Mọi kim loại đều là chấtrắn". Đây là kết luận sai lầm vì thủy ngân là một kim loại nhưng không phải làchất rắn.Phần này ta sẽ nghiên cứu cách suy luận quy nạp thế nào là đúng và áp dụngchính xác những suy luận này để giải các bài toán về số học, đại số, hình họcvà giải tích trong chương trình phổ thông.1.1.2 Một số ví dụ về suy luận quy nạpTrước khi đi vào nguyên lý cụ thể ta xét một số ví dụ mà cách giải thực hiệntừ trường hợp cụ thể tiến tới tổng quát hóa.Ví dụ 1.1. Chứng minh rằng tổng n số tự nhiên lẻ đầu tiên bằng n2.Lời giải.Ta biết rằng số lẻ thứ nhất là 1, số lẻ thứ hai là 3, số lẻ thứ ba là 5, Nhưvậy số lẻ thứ k là [2k − 1] với k = 1, 2, 3, Ta kí hiệu S[n] là tổng của n số tự nhiên lẻ đầu tiên.5Chương 1. PHƯƠNG PHÁP QUY NẠPTa thấy rằngVới n = 1, S[1] = 1 = 12, kết luận của bài toán đúng.Với n = 2, S[2] = 1 + 3 = 22, kết luận của bài toán đúng.Với n = 3, S[3] = 1 + 3 + 5 = 32, kết luận của bài toán đúng.Ta có thể tiếp tục kiểm tra cho các trường hợp tiếp theo. Nhưng những số lẻlà vô cùng nhiều nên ta không có khả năng kiểm tra hết được từng giá trị. Vậycó cách nào khác không để suy luận từ một số trường hợp mà sẽ đúng với mọitrường hợp?Ta thấy rằng những trường hợp giá trị ở sau đều có thể suy ra kết luận từ giátrị trước bằng mối quan hệ S[n] = S[n − 1] + 2n − 1, [n ≥ 2].Nếu ta đã tính được S[n − 1] = [n −1]2thì ta cóS[n] = S[n − 1] + 2n −1 = [n − 1]2+ 2n − 1 = n2.Như vậy, cứ số trước đã có kết quả đúng thì số sau cũng đúng. Ta có n = 3 kếtluận đúng thì n = 4 kết luận đúng, sau đó n = 5, Suy ra bài toán đúng với mọi giá trị của n.Ví dụ 1.2. Chứng minh rằng với mọi số nguyên đồng [tiền Việt Nam] lớn hơn6 có thể đổi ra tiền lẻ không dư bằng những đồng tiền gồm những tờ 2 đồng hoặc5 đồng [1 đồng ở đây bằng 1000 đồng trong thực tế].Lời giải. Đẳng thức sau đây nói lên 7 đồng, 8 đồng thì gồm tờ 2 đồng và 5đồng như thế nào:7 = 5 + 2;8 = 2 + 2 + 2 + 2.Nếu ta thêm vào hai vế của các đẳng thức trên tờ 2 đồng, thì9 = 7 + 2;10 = 8 + 2.Tiếp tục thêm 2 đồng vào hai đẳng thức sau cùng, ta có11 = 9 + 2;12 = 10 + 2.Ta còn tiếp tục làm được như trên với bất cứ một số nguyên dương nào kháclớn hơn 6. Ta thấy rằng ở bước trước có hai đẳng thức và suy ra bước sau cũngcó hai đẳng thức. Như vậy với mọi số n nguyên đồng nào dù là số chẵn hoặc sốlẻ thì n −2 đồng cũng rơi vào một trong hai trường hợp trước đó đã đổi được ra6Chương 1. PHƯƠNG PHÁP QUY NẠPhai loại tiền 2 đồng và 5 đồng. Suy ra nó cũng đổi được thành các đồng 2 đồngvà 5 đồng.Như vậy khẳng định của bài toán là đúng.1.1.3 Nguyên lý quy nạp toán họcCơ sở của nguyên lý quy nạp toán học là tiên đề thứ 5 [còn gọi là tiên đề quynạp] của hệ tiên đề PEANO về tập hợp số tự nhiên được xây dựng từ cuối thếkỉ 19.• Tiên đề 1. 1 là số tự nhiên.• Tiên đề 2. Với mọi số tự nhiên a, có một số tự nhiên a* đi liền sau a.• Tiên đề 3. Số 1 không đi liền sau số tự nhiên nào. Nói cách khác, với mọi sốtự nhiên a ta chỉ có a* khác 1.• Tiên đề 4. Nếu a*=b* thì a=b. Số tự nhiên đi liền sau a là duy nhất.• Tiên đề 5. [Tiên đề quy nạp] Giả sử M là một tập hợp các số tự nhiên cótính chất: M chứa 1, và nếu M chứa a thì M cũng chứa a*. Khi đó tập M trùngvới tập hợp các số tự nhiên .Mệnh đề là một câu trọn nghĩa [một khẳng định] mà nội dung của nó phảnánh đúng hoặc sai thực tế khách quan.Những ví dụ trên cho ta thấy rằng mỗi bài toán là một mệnh đề đúng hoặcsai. Mỗi mệnh đề như vậy lại phụ thuộc vào một biến số tự nhiên n. Một cáchtổng quát ta kí hiệu P [n] là mệnh đề toán học phụ thuộc vào n, với n là số tựnhiên. Như vậy, thực chất của các ví dụ đã xét là chứng minh dãy mệnh đề sauđúng [hoặc sai]P [1], P [2], P[3], , P [n], Một số bài toán phát biểu dưới dạng: Chứng minh rằng với mọi số tự nhiênn, P[n] đúng. Như vậy, những bài toán loại này đều liên quan tới tập số tựnhiên.Một tính chất của tập số tự nhiên người ta công nhận như một tiên đề vàthường gọi là tiên đề thứ tự.Tiên đề thứ tự. Mọi tập khác rỗng các số tự nhiên đều có phần tử nhỏ nhất.Cho mỗi số tự nhiên n ứng với một khẳng định P [n]. Thay vì ta phải đi kiểmtra vô hạn các mệnh đề thì người ta sử dụng nguyên lý toán học sau là đủ.Định lý 1.1. [Nguyên lý quy nạp toán học.] Cho n0≥ 1 là một số tự nhiêncố định và P[n] là một mệnh đề có nghĩa với mọi số tự nhiên n ≥ n0. Giả sử haiđiều kiện sau được thỏa mãn:7Chương 1. PHƯƠNG PHÁP QUY NẠP[i] P [n0] là mệnh đề đúng và[ii] Nếu mệnh đề P [k] đúng với mỗi số tự nhiên k ≥ n0kéo theo mệnh đềP [k + 1] cũng đúng.Khi đó mệnh đề P[n] đúng với mọi số tự nhiên n ≥ n0.Chứng minh. Gọi A là tập hợp các số tự nhiên n ≥ n0mà P[n] không đúng.Giả sử A = ∅, khi đó sẽ tồn tại một số tự nhiên m ≥ n0mà P[m] không đúng.Ta lấy số tự nhiên nhỏ nhất mtrong A màP [m] không đúng. [1.1]Điều này thực hiện được do tiên đề thứ tự. Theo giả thiết [i] thì P [n0] đúngnên m> n0suy ra m− 1 ≥ n0. Vì m− 1 /∈ A [do mlà số nhỏ nhất thuộc A],nên theo định nghĩa của tập A thì P [m−1] đúng. Khi đó theo giả thiết [ii] thìP [m] = P [[m− 1] + 1] cũng đúng. [1.2]Từ [1.1] và [1.2] suy ra mâu thuẫn. Điều này chứng tỏ A = ∅.Vậy P [n] đúng với mọi số tự nhiên n ≥ n0. Phương pháp dùng nguyên lý quy nạp toán học để giải toán, người ta gọi làphương pháp quy nạp toán học.Chú ý 1.1. Ta cần phân biệt rõ các khái niệm• "Phép quy nạp" là một phương pháp tư duy dùng để tìm tòi, dự đoán, pháthiện các kiến thức mới.• "Phương pháp quy nạp toán học" ta gọi tắt "Phương pháp quy nạp" là mộtphương pháp chứng minh các khẳng định chứa chữ n ∈ N [tập hợp các số tựnhiên].Ta cũng có thể sử dụng phương pháp quy nạp để chứng minh những khẳngđịnh đối với các số nguyên.Nhiều khẳng định mà có thể được chứng minh bằng phương pháp quy nạp cũngcó thể được chứng minh bằng các phương pháp khác đôi khi ngắn gọn hơn.1.2 Phương pháp chứng minh quy nạpDựa theo nguyên lý quy nạp toán học ta đưa ra các bước trong chứng minhtheo phương pháp quy nạp toán học.8Chương 1. PHƯƠNG PHÁP QUY NẠP1.2.1 Các bước trong phương pháp chứng minh quy nạpGiả sử khẳng định P [n] xác định với mọi n ≥ n0, [n, n0∈ Z+]. Để chứng minhP [n] đúng với mọi n ≥ n0bằng phương pháp quy nạp, ta cần thực hiện ba bước:Bước 1. Cơ sở quy nạp. Ta kiểm tra mệnh đề có đúng với n = n0không?Nghĩa là kiểm tra P [n0] có đúng không? Nếu bước cơ sở đúng ta chuyển sangbước thứ hai.Bước 2. Quy nạp. Chứng minh rằng nếu với mỗi k ≥ n0[k ∈ Z+], P[k] làmệnh đề đúng thì suy ra P [k + 1] cũng đúng.Bước 3. Kết luận. P [n] đúng với mọi n ≥ n0.Ví dụ 1.3. Tính tổng của n số tự nhiên đầu tiên.Lời giải. Kí hiệu S[n] là tổng của n số tự nhiên đầu tiên, nghĩa làS[n] = 1 + 2 + 3 + + n.Ta tính một số tổng tại những giá trị ban đầu.n 1 2 3 4 5 6 7 8S[n] 1 3 6 10 15 21 28 36Ta thấy quy luật: Tích của hai số liên tiếp ở hàng trên bằng 2 lần số ở hàngdưới [số có vị trí cùng cột với số thứ nhất trong 2 số liên tiếp ở hàng trên]. Như1.2 = 2.1, 2.3 = 2.3, 3.4 = 2.6, 4.5 = 2.10, 5.6 = 2.15, 6.7 = 2.21, Do đó ta có thể dự đoán công thức phải tìm làS[n] = 1 + 2 + 3 + + n =n[n + 1]2. [1.3]Biểu thức [1.3] được gọi là giả thiết quy nạp. Muốn chắc chắn công thức nàyđúng ta phải chứng minh bằng phương pháp quy nạp thông qua hai bước:1. Bước cơ sở. Với n = 1 công thức [1.3] đúng như cách tính ở trên.2. Bước quy nạp. Giả sử n = k ≥ 1 [k ∈ Z+], S[k] đúng tức là S[k] =k[k + 1]2.Ta phải chứng minh [1.3] cũng đúng với n = k + 1.Thật vậy,S[k + 1] = S[k] + [k + 1]=k[k + 1]2+ [k + 1] =k[k + 1]2+2[k + 1]2=[k + 1][k + 2]2.Do đó công thức [1.3] cũng đúng với n = k + 1.Theo nguyên lý quy nạp toán học công thức [1.3] đúng với mọi n ≥ 1.Vậy 1 + 2 + 3 + + n =n[n + 1]2.9Chương 1. PHƯƠNG PHÁP QUY NẠPVí dụ 1.4. Tính tổng các lập phương của n số tự nhiên đầu tiên.Lời giải. Ta đặt công thức T [n] = 13+ 23+ 33+ + n3.Ta cũng đi tính một số giá trị ban đầu:n 1 2 3 4 5 6T[n] 1 9 36 100 225 441Nhìn vào bảng trên ta khó có thể tìm ra quy luật cho T[n].Nhưng với kinh nghiệm và kết quả đã tính ở bài trước ta có bảng như sau:n 1 2 3 4 5 6S[n] 1 3 6 10 15 21T[n] 1 9 36 100 225 441Ở đây S[n] = 1 + 2 + + n.Từ bảng trên ta thấy rằng có thểT [n] = S2[n] : 1 = 12, 9 = 32, 36 = 62, Công thức tính S[n] đã biết ở bài toán 1.3, khi đó ta có công thức cho giả thiếtquy nạp làT [n] = 13+ 23+ 33+ + n3=n[n + 1]22. [1.4]Chứng minh công thức [1.4] bằng phương pháp quy nạp theo n :1. Bước cơ sở. Với n = 1 công thức [1.4] đúng [theo bảng trên].2. Bước quy nạp. Giả sử [1.4] đúng với n = k ≥ 1 [k ∈ Z+], ta phải chứng minh[1.4] cũng đúng với n = k + 1.Thật vậy,T [k + 1] = 13+ 23+ 33+ + k3+ [k + 1]3= T [k] + [k + 1]3=k[k + 1]22+ [k + 1]3= [k + 1]2k24+ k + 1= [k + 1]2k2+ 4k + 44=[k + 1][k + 2]22.Vậy [1.4] đúng với n = k + 1. Theo nguyên lý quy nạp toán học suy ra [1.4]đúng với mọi số tự nhiên n.Do đó ta có13+ 23+ 33+ + n3=n[n + 1]22.10Chương 1. PHƯƠNG PHÁP QUY NẠPChú ý 1.2.Trong quá trình quy nạp nếu không thực hiện đầy đủ cả hai bước: Cơ sở quynạp và quy nạp thì có thể dẫn tới sai lầm, chẳng hạn:• Do bỏ bước cơ sở quy nạp nên ta đưa ra khẳng định không đúng.Ta xét bài toán: Chứng minh rằng mọi số tự nhiên đều bằng số tự nhiên liềnsau nó.Chứng minh bài toán theo phương pháp quy nạp như sau:Giả sử mệnh đề đúng với n = k, [k ∈ N]. Khi đó ta có: k = k + 1.Ta sẽ chứng minh mệnh đề đúng với n = k + 1, nghĩa là phải chứng minh:k + 1 = k + 2. Thật vậy,k + 1 = [k + 1] + 1 = k + 2.Như vậy khẳng định đúng với n = k thì nó cũng đúng với n = k + 1, do đó theoquy nạp toán học nó đúng với mọi số tự nhiên n. Hệ quả của bài toán này làtất cả các số tự nhiên đều bằng nhau! Điều này vô lý.Vậy cách chứng minh sai ở đâu? Dễ thấy rằng khi ta áp dụng nguyên lí quynạp toán học nhưng đã bỏ qua kiểm tra trường hợp n = 1. Ta thấy với n = 1 thìkhẳng định của bài toán sai vì 1 = 2.Bước kiểm tra ban đầu có một ý nghĩa đặc biệt là tạo ra cơ sở để thực hiệnquy nạp. Bước thứ hai đưa ra nguyên tắc cho việc mở rộng tự động vô hạn trêncơ sở các điều kiện ban đầu, đây là nguyên tắc đi từ trường hợp riêng này sangtrường hợp riêng khác: từ k đến k + 1.Bài toán trên khi chưa kiểm tra điều kiện ban đầu thì không có cơ sở để thựchiện quy nạp, vì thế việc kiểm tra phần quy nạp không có ý nghĩa gì.• Khi ta chỉ chứng minh được một số điều kiện ban đầu mà bỏ qua phần quynạp thì mới chỉ đưa ra được cơ sở chứ chưa có nguyên tắc nào để mở rộng cơ sởđó. Do đó điều ta khẳng định có thể sẽ bị sai.Ta xét ví dụ sau: Nhà Toán học Pháp P.Fermat [1601 - 1665] đã cho rằngcác số dạng 22n+ 1 đều là số nguyên tố với n là số nguyên không âm.Khi đó, P.Fermat chỉ xét 5 số đầu tiên:Với n = 0 cho 220+ 1 = 2 + 1 = 3 là số nguyên tố.n = 1 cho 221+ 1 = 22+ 1 = 5 là số nguyên tố.n = 2 cho 222+ 1 = 24+ 1 = 17 là số nguyên tố.n = 3 cho 223+ 1 = 28+ 1 = 257 là số nguyên tố.n = 4 cho 224+ 1 = 216+ 1 = 65537 là số nguyên tố.11Chương 1. PHƯƠNG PHÁP QUY NẠPNhưng vào thế kỷ 18, Euler đã phát hiện với n = 5 khẳng định trên khôngđúng, bởi vì:225+ 1 = 4294967997 = 641 × 6700417 là hợp số.Rõ ràng vì bỏ qua bước quy nạp nên khẳng định của P.Fermat không đúng.Vậy phương pháp chứng minh bằng quy nạp toán học cần phải thực hiện haibước như phân tích ở phần trên. Khó khăn chủ yếu chúng ta gặp trong bướcquy nạp toán học là khi mệnh đề giả sử đã đúng cho P [k] và phải chứng minhcho P [k + 1] cũng đúng. Thông thường người ta phải tìm mối liên hệ giữa P [k]và P [k + 1] để suy ra kết quả phải chứng minh.1.2.2 Bước quy nạp được xây dựng trên P[k]Phần này ta xét khả năng biến đổi quy nạp trực tiếp từ khẳng định đúngP[k] sang khẳng định đúng P[k+1].Ví dụ 1.5. Chứng minh rằng với mọi số tự nhiên n, thì12+ 22+ 32+ + n2=n[n + 1][2n + 1]6[1.5]Lời giải. Ta chứng minh bằng phương pháp quy nạp theo n.ĐặtS[n] = 12+ 22+ 32+ + n2.1. Bước cơ sở. Với n = 1 thì S[1] = 12= 1 =1.2.36, công thức [1.5] đúng.2. Bước quy nạp. Giả sử [1.5] đúng với n = k ≥ 1 [k ∈ N], tức làS[k] = 12+ 22+ 32+ + k2=k[k + 1][2k + 1]6.Khi đóS[k + 1] = 12+ 22+ + k2+ [k + 1]2= S[k] + [k + 1]2=k[k + 1][2k + 1]6+ [k + 1]2= [k + 1]k[2k + 1] + 6[k + 1]6= [k + 1]2k[k + 1] + k + 4[k + 1] + 26=[k + 1][k + 2][2[k + 1] + 1]6.Do đó [1.5] đúng với n = k + 1.Theo nguyên lý quy nạp toán học [1.5] đúng với mọi số tự nhiên n.12Chương 1. PHƯƠNG PHÁP QUY NẠP1.2.3 Bước quy nạp được xây dựng trên P[k+1]Bước quy nạp toán học cần khẳng định P [k + 1] được suy ra từ P[k].Nhưng nhiều khi việc biến đổi trực tiếp từ P [k] sang P [k + 1] gặp rất nhiều khókhăn hoặc không có hướng chính xác để biến đổi. Khi đó ta phải làm ngược lạiđể biểu diễn P[k + 1] thành những mệnh đề P [k] và tiến hành quy nạp.Ví dụ 1.6. Chứng minh rằng số zn= 32n+1+ 40n −67 chia hết cho 64 với mọisố nguyên không âm n.Lời giải.1. Bước cơ sở. Với n = 0 ta có z0= 31−67 = −64 chia hết cho 64, mệnh đề đúng.2. Bước quy nạp. Giả sử znchia hết cho 64.Khi đózn+1= 32[n+1]+1+ 40[n + 1] − 67= 32n+3+ 40n − 27= 9[32n+1+ 40n − 67] − 320n + 576= 9.zn− 64[5n − 9].Vế phải của đẳng thức sau cùng chia hết cho 64, vậy với n+1 mệnh đề vẫn đúng.Theo nguyên lý quy nạp bài toán đúng với mọi số nguyên không âm n.1.3 Một số dạng khác của nguyên lý quy nạp toán họcĐiều kiện thứ nhất trong nguyên lý quy nạp toán học cho ta cơ sở mở rộngbắt đầu từ giá trị n0. Điều kiện thứ hai cho ta mệnh đề khẳng định P[n] đúngtại n0+ 1, n0+ 2, Thực tế nhiều khi trong bước quy nạp phải đòi hỏi hai giátrị n = k − 1 và n = k của mệnh đề trước khi suy ra đúng với n = k + 1. Trongtrường hợp này bước cơ sở phải kiểm tra không những chỉ với n0, mà cả n0+ 1.Tổng quát hơn ta có các định lý sau:Định lý 1.2. Cho P [n] là một mệnh đề có nghĩa với mọi số tự nhiên n ≥ 1. Giảsử hai điều kiện sau được thỏa mãn:[i] P[1] là mệnh đề đúng và[ii] Nếu các mệnh đề P [1], P [2], , P [k] đúng với mỗi số tự nhiên k ≥ 1 kéotheo mệnh đề P [k + 1] cũng đúng.Khi đó mệnh đề P[n] đúng với tất cả các số tự nhiên n ≥ 1.13Chương 1. PHƯƠNG PHÁP QUY NẠPChứng minh. Gọi A là tập hợp các số tự nhiên n ≥ 1 mà P [n] không đúng.Giả sử A = ∅, khi đó sẽ tồn tại một số tự nhiên m mà P [m] không đúng. Ta lấysố tự nhiên nhỏ nhất mtrong A màP [m] không đúng. [1.6]Điều này thực hiện được do tiên đề thứ tự. Theo giả thiết [i] thì P [1] đúng nênm> 1 suy ra m−1 ≥ 1. Vì k := m−1 /∈ A [do mlà số nhỏ nhất thuộc A], nêntheo định nghĩa của tập A thì P[k] đúng. Tương tự k −1 /∈ A và P [k −1] đúng,cứ lặp lại như thế, ta thu được một dãy P [1], P [2], . . . , P[k] là những mệnh đềđúng. Khi đó theo giả thiết [ii] thìP [m] = P [k + 1] cũng đúng. [1.7]Từ [1.6] và [1.7] suy ra mâu thuẫn. Điều này chứng tỏ A = ∅.Vậy P [n] đúng với mọi số tự nhiên n ≥ n0. Ví dụ 1.7. Cho x +1xlà một số nguyên [x = 0]. Chứng minh rằngx2013+1x2013cũng là một số nguyên.Lời giải. Ta dùng phương pháp quy nạp để chứng minh mệnh đề sau:"Nếu x +1xlà một số nguyên [x = 0] thì với mọi số nguyên dương n, xn+1xncũng là một số nguyên."1. Bước cơ sở. Khi n = 1 mệnh đề hiển nhiên đúng.2. Bước quy nạp. Giả sử mệnh đề đúng với mọi số nguyên dương n có giá trị từ1 đến k, nghĩa là x +1x, x2+1x2, . . . , xk+1xklà những số nguyên.Ta cần chứng minh xk+1+1xk+1cũng là số nguyên.Thật vậy,xk+1+1xk+1=x +1xxk+1xk−xk−1+1xk−1.Theo giả thiết quy nạp x +1x, xk+1xk, xk−1+1xk−1đều là các số nguyên.Vậy xk+1+1xk+1cũng là số nguyên. Theo định lý 1.2, mệnh đề được chứng minh.Từ mệnh đề, dễ dàng suy ra x2013+1x2013cũng là một số nguyên.Định lý 1.3. Cho n0là một số tự nhiên cố định và P[n] là một mệnh đề cónghĩa với mọi số tự nhiên n. Giả sử hai điều kiện sau được thỏa mãn:[i] P [1], P [2], , P[n0] là những mệnh đề đúng;14Chương 1. PHƯƠNG PHÁP QUY NẠP[ii] Nếu các mệnh đề P [k −n0+ 1], P [k −n0+ 2], , P[k] đúng với mỗi k ≥ n0[k ∈ N], kéo theo mệnh đề P[k + 1] cũng đúng.Khi đó mệnh đề P[n] đúng với mọi số tự nhiên n.Chứng minh. Gọi A là tập hợp các số tự nhiên n mà P [n] không đúng.Giả sử A = ∅, khi đó sẽ tồn tại một số tự nhiên m mà P [m] không đúng. Ta lấysố tự nhiên nhỏ nhất mtrong A màP [m] không đúng. [1.8]Điều này thực hiện được do tiên đề thứ tự. Theo giả thiết [i] thì P [1] đúng nênm> 1 suy ra m− 1 ≥ 1. Đặt k := m− 1, ta sẽ chứng minhP [m] = P [k + 1] cũng đúng. [1.9]Thật vậy, nếu k < n0thì k + 1 ≤ n0nên theo giả thiết [i], ta có P [m] = P [k + 1]đúng. Nếu k ≥ n0thì do k = m−1 /∈ A [vì mlà số nhỏ nhất thuộc A], nên theođịnh nghĩa của tập A thì P [k] đúng. Tương tự k −1 /∈ A và P [k −1] đúng, cứ lặplại như thế sau n0−1 bước, ta thu được một dãy P[k−n0+1], P[k−n0+2], . . . , P[k]là những mệnh đề đúng. Khi đó theo giả thiết [ii], ta có P [m] = P [k + 1] đúng.Vậy ta luôn có [1.9].Do đó từ [1.8] và [1.9] suy ra mâu thuẫn. Điều này chứng tỏ A = ∅.Vậy P [n] đúng với mọi số tự nhiên n ≥ n0. Ví dụ 1.8. Cho x1và x2là nghiệm của phương trình x2− 27x + 14 = 0 và n làsố nguyên dương. Chứng minh rằng tổng Sn= xn1+ xn2không chia hết cho 715.Lời giải. Theo công thức Viet, ta có x1+ x2= 27 và x1x2= 14.1. Bước cơ sở: Các số S1= 27, S2= x21+ x22= [x1+ x2]2− 2x1x2= 701 vàS3= x31+ x32= [x1+ x2][x1+ x2]2− 3x1x2= 27687 đều không chia hết cho 715.Suy ra mệnh đề của bài toán đúng với n = 1, 2, 3.2. Bước quy nạp: Giả sử mệnh đề đúng với n = k − 2, n = k − 1, n = k, [k ≥ 3].Ta cần chứng minh mệnh đề đúng với n = k + 1. Thật vậy,xk+11+ xk+12= [x1+ x2]xk1+ xk2− x1x2xk−11+ xk−12= [x1+ x2][x1+ x2]xk−11+ xk−12− x1x2xk−21+ xk−22− x1x2xk−11+ xk−12= 2727xk−11+ xk−12− 14xk−21+ xk−22− 14xk−11+ xk−12= 715xk−11+ xk−12− 378xk−21+ xk−22.15Chương 1. PHƯƠNG PHÁP QUY NẠPVì xk−21+ xk−22không chia hết cho 715,378 không chia hết cho 715 và 378 = 2.33.7, 715 = 5.11.13nên xk+11+ xk+12không chia hết cho 715.Khi đó mệnh đề đúng với n = k + 1.Vậy theo định lý 1.3, khẳng định của bài toán đúng với mọi n nguyên dương.Nhận xét 1.1. Ta thấy định lý 1.2 giả thiết quy nạp mạnh hơn định lý 1.3 trongbước quy nạp. Trong thực tế áp dụng định lý 1.2 dễ hơn định lý 1.3.Đôi lúc trong thực tế, khi giải toán chúng ta gặp trường hợp dãy mệnh đề bắtđầu từ P[0] hoặc P [n0], [n0là một số tự nhiên nào đó]. Khi đó ta vẫn áp dụngcác định lý như bình thường. Ta sẽ xét ví dụ sau đây.Ví dụ 1.9. Cho v0= 2, v1= 3 và với mỗi số tự nhiên k có đẳng thức sauvk+1= 3vk− 2vk−1[k ≥ 1, k ∈ N].Chứng minh rằngvn= 2n+ 1. [1.10]Lời giải.1. Bước cơ sở. Với n = 0 và n = 1 công thức [1.10] cho kết quả đúng.2. Bước quy nạp. Giả sử công thức [1.10] đúng với n = k, và n = k − 1, [k ≥ 1]nghĩa là vk= 2k+ 1 và vk−1= 2k−1+ 1, khi đóvk+1= 32k+ 1− 22k−1+ 1= 2k+1+ 1,nên công thức [1.10] đúng với n = k + 1.Theo định lý 1.3 suy ra vn= 2n+ 1 đúng với mọi số tự nhiên n.1.4 Vận dụng phương pháp quy nạp để giải các bài toán phổthôngQuy nạp toán học là một phương pháp khá phổ biến và thông dụng. Nó đượcứng dụng rất nhiều trong số học, đại số, giải tích và hình học. Chúng ta hãycùng đi xét một số bài toán vận dụng phương pháp quy nạp để giải sau đây.1.4.1 Phương pháp quy nạp trong số họcTa xét một số bài toán về phép chia hết và tính chất các số.Bài toán 1.1. Chứng minh rằng với mọi số nguyên dương n, thìSn= [n + 1][n + 2] [n + n] chia hết cho 2n.16Chương 1. PHƯƠNG PHÁP QUY NẠPLời giải.1. Bước cơ sở. Với n = 1, ta có S1= 1 + 1 = 2 chia hết cho 21= 2.Mệnh đề đúng với n = 1.2. Bước quy nạp. Giả sử mệnh đề đúng với n = k ≥ 1, [k ∈ Z+], nghĩa làSk= [k + 1][k + 2] [k + k] chia hết cho 2k.Ta phải chứng minh mệnh đề đúng với n = k + 1. Thật vậy,Sk+1= [k + 1 + 1][k + 1 + 2] [k + 1 + k −1][k + 1 + k][k + 1 + k + 1]= [k + 2][k + 3] [k + k][k + k + 1][2k + 2]= 2[k + 1][k + 2][k + 3] [k + k][k + k + 1]= 2Sk.[2k + 1].Theo giả thiết quy nạp Skchia hết cho 2k, suy ra Sk+1chia hết cho 2k+1.Theo nguyên lý quy nạp toán học Snchia hết cho 2nvới mọi n nguyên dương.Bài toán 1.2. [Định lý Fermat] Nếu p là một số nguyên tố, thì với mọi sốnguyên dương n hiệu np− n chia hết cho p.Lời giải. Khẳng định trên được chứng minh bằng quy nạp theo n.1. Bước cơ sở. Với n = 1 ta có 1p− 1 = 0 chia hết cho p.Khẳng định đúng với n = 1.2. Bước quy nạp. Giả sử khẳng định đúng với n = a ≥ 1, [a ∈ Z+], nghĩa là ap−achia hết cho p. Ta cần chứng minh [a + 1]p− [a + 1] cũng chia hết cho p.Khai triển [a + 1]pbằng nhị thức Newton ta có[a + 1]p− [a + 1] = ap+ p.ap−1+ C2pap−2+ C3pap−3+ . . . + pa + 1 − [a + 1]= [ap− a] + pap−1+ C2pap−2+ C3pap−3+ . . . + Cp−2pa2+ pa.Vì các hệ số Ckp=p[p − 1][p − 2] . . . [p −k + 1]1.2.3 . . . k, [2 ≤ k ≤ p −2] đều chia hết chop và ap− a chia hết cho p [theo giả thiết quy nạp] nên suy ra [a + 1]p− [a + 1]cũng chia hết cho p.Theo nguyên lý quy nạp toán học ta có với mọi số nguyên dương n số np−nchia hết cho số nguyên tố p. Định lý được chứng minh.Bài toán 1.3. Chứng minh rằng7 + 77 + 777 + + 777 7n chữ số 7=78110n+1− 9n − 10. [1.11]Lời giải. Đặt Sn= 7 + 77 + 777 + + 777 7n chữ số 7.17Chương 1. PHƯƠNG PHÁP QUY NẠP1. Bước cơ sở. Với n = 1, S1= 7, còn vế phải781[102− 9.1 − 10] =781.81 = 7.Vậy [1.11] đúng với n = 1.2. Bước quy nạp. Giả sử [1.11] đúng với n = k ≥ 1 [k ∈ N], nghĩa làSk=781[10k+1− 9k −10].Ta cần phải chứng minhSk+1=781[10k+2− 9[k + 1] −10].Thật vậy,Sk+1= Sk+ 777 7k+1 chữ số= Sk+ 7.10k+ 7.10k−1+ + 7.102+ 7.10 + 7= Sk+ 71 + 10 + 102+ + 10k.Nhưng vì 1 + 10 + 102+ + 10k=10k+1− 110 − 1nênSk+1=781[10k+1− 9k −10] + 7.10k+1− 110 − 1=78110k+1− 9k −10 + 9.10k+1− 9=78110.10k+1− 9k −19=78110k+2− 9[k + 1] −10.Suy ra đẳng thức [1.11] đúng với n = k + 1.Theo nguyên lý quy nạp toán học [1.11] đúng mọi n nguyên dương.Một số ví dụ về chứng minh đẳng thức và tính tổng số học.Bài toán 1.4. Cho số tự nhiên n ≥ 1. Chứng minh rằng1.2 + 2.3 + + n[n + 1] =n[n + 1][n + 2]3. [1.12]Lời giải. Đặt T [n] = 1.2 + 2.3 + + n[n + 1].1. Bước cơ sở. Với n = 1 thì T[1] = 1.2 =1.2.33. Đẳng thức [1.12] đúng với n = 1.2. Bước quy nạp. Giả sử đẳng thức [1.12] đúng với n = k ≥ 1, [k ∈ N]. Khi đóT [k] = 1.2 + 2.3 + + k[k + 1] =k[k + 1][k + 2]3.Ta phải chứng minh đẳng thức [1.12] đúng với n = k + 1. Thật vậy,T [k + 1] = 1.2 + 2.3 + + k[k + 1] + [k + 1][k + 2]=k[k + 1][k + 2]3+ [k + 1][k + 2]= [k + 1][k + 2]k3+ 1=[k + 1][k + 2][k + 3]3.18Chương 1. PHƯƠNG PHÁP QUY NẠPVậy đẳng thức [1.12] đúng với n = k + 1.Theo nguyên lý quy nạp thì đẳng thức [1.12] đúng với mọi số tự nhiên n.Bài toán 1.5. Chứng minh rằng với mọi số tự nhiên n, thì0.0! + 1.1! + 2.2! + 3.3! + + n.n! = [n + 1]! −1. [1.13]Lời giải. Đặt S[n] = 0.0! + 1.1! + 2.2! + 3.3! + + n.n!.1. Bước cơ sở. Với n = 1 thì S[1] = 0.0! + 1.1! = 2! −1 = 1.Đẳng thức [1.13] đúng với n = 1.2. Bước quy nạp. Giả sử đẳng thức [1.13] đúng với n = k ≥ 1 [k ∈ N]. Khi đóS[k] = 0.0! + 1.1! + 2.2! + 3.3! + + k.k! = [k + 1]! − 1.Ta phải chứng minh đẳng thức [1.13] đúng với n = k + 1.Thật vậy,S[k + 1] = 0.0! + 1.1! + 2.2! + 3.3! + + k.k! + [k + 1][k + 1]!= [k + 1]! −1 + [k + 1][k + 1]!= [k + 1]![k + 1 + 1] − 1= [k + 2]! −1.Suy ra đẳng thức [1.13] đúng với n = k + 1.Theo nguyên lý quy nạp đẳng thức [1.13] đúng với mọi số tự nhiên n.Bài toán 1.6. Hãy tính tổng sau với n là số tự nhiên,11.2.3+12.3.4+13.4.5+ . . . +1n[n + 1][n + 2].Lời giải. Đặt Tn=11.2.3+12.3.4+13.4.5+ . . . +1n[n + 1][n + 2].Ta có:11.2.3=1[1 + 3]4[1 + 1][1 + 2]11.2.3+12.3.4=2[2 + 3]4.[2 + 1][2 + 2]11.2.3+12.3.4+13.4.5=3[3 + 3]4.[3 + 1][3 + 2] Từ đó ta có thể giả thiếtTn=n[n + 3]4[n + 1][n + 2]. [1.14]19Chương 1. PHƯƠNG PHÁP QUY NẠPTa chứng minh giả thiết trên bằng phương pháp quy nạp.1. Bước cơ sở. Với n = 1 thì T1=11.2.3=1[1 + 3]4[1 + 1][1 + 2].Vậy công thức [1.14] đúng với n = 1.2. Bước quy nạp. Giả sử [1.14] đúng với n = k ≥ 1 [k ∈ N], nghĩa là cóTk=ki=11i[i + 1][i + 2]=k[k + 3]4[k + 1][k + 2].Ta cần chứng minh công thức [1.14] đúng với n = k + 1.Thật vậy,Tk+1=k+1i=11i[i + 1][i + 2]=ki=11i[i + 1][i + 2]+1[k + 1][k + 2][k + 3]=k[k + 3]4[k + 1][k + 2]+1[k + 1][k + 2][k + 3]=k[k + 3][k + 3]4[k + 1][k + 2][k + 3]+44[k + 1][k + 2][k + 3]=k3+ 6k2+ 9k + 44[k + 1][k + 2][k + 3]=[k + 1]2[k + 4]4[k + 1][k + 2][k + 3]=[k + 1][k + 4]4[k + 2][k + 3].Công thức [1.14] đúng với n = k + 1 nên theo nguyên lý quy nạp nó đúng vớimọi số tự nhiên n.Vậy11.2.3+12.3.4+13.4.5+ +1n[n + 1][n + 2]=n[n + 3]4[n + 1][n + 2].Với những bài toán về dãy số thì công thức tính tổng và số hạng tổng quátcủa các dãy này ta có thể chứng minh bằng phương pháp quy nạp. Ta sẽ đi xétmột số bài toán sau.Bài toán 1.7. [Vô địch quốc gia Việt Nam, 1989] Với n = 0, 1, 2, ··· , ta gọi{xn} và {yn} là hai dãy số được xác định một cách đệ quy như sau:x0= 1, x1= 4, xn+2= 3xn+1− xn;y0= 1, y1= 2, yn+2= 3yn+1− yn.Chứng minh rằng x2n− 5y2n+ 4 = 0 với mọi số nguyên không âm n.20Chương 1. PHƯƠNG PHÁP QUY NẠPLời giải. Từ giả thiết ta tính được x2= 11 và y2= 5.Trước tiên, ta chứng minh bằng quy nạp theo n rằng[xn+1, yn+1] =3xn+ 5yn2,xn+ 3yn2, [n ≥ 0]. [1.15]1. Bước cơ sở. Với n = 0 thì [x1, y1] =3.1+5.12,1+3.12= [4, 2].Với n = 1 thì [x2, y2] =3.4+5.22,4+3.22= [11, 5].Vậy [1.15] đúng khi n = 0 và n = 1.2. Bước quy nạp. Giả sử [1.15] đúng khi n = k và n = k + 1, với k ≥ 0 [k ∈ Z].Theo bài ra ta có[xk+3, yk+3] = [3xk+2− xk+1, 3yk+2− yk+1].Từ đó suy ra[xk+3, yk+3] =3.3xk+1+ 5yk+12−3xk+ 5yk2, 3.xk+1+ 3yk+12−xk+ 3yk2=32[3xk+1− xk] +52[3yk+1− yk],12[3xk+1− xk] +32[3yk+1− yk]=12[3xk+2+ 5yk+2],12[xk+2+ 3yk+2].Như vậy [1.15] đúng với n = k + 2. Theo định lý 1.3 ta có [1.15] đúng với mọisố nguyên không âm n.Tiếp theo, ta chứng minh x2n− 5y2n+ 4 = 0 bằng quy nạp theo n.Khi n = 0 thì ta có 1 −5 + 4 = 0. Công thức đúng với n = 0.Giả sử công thức này đúng với n = k, [k ≥ 0, k ∈ Z], tức là x2k− 5y2k+ 4 = 0.Ta chứng minh công thức đúng với n = k + 1. Thật vậy,x2k+1− 5y2k+1+ 4 =3xk+ 5yk22− 5xk+ 3yk22+ 4=4x2k− 20y2k4+ 4 = x2k− 5y2k+ 4 = 0.Theo nguyên lý quy nạp ta có x2n− 5y2n+ 4 = 0 với mọi số nguyên n ≥ 0.Ở phần quy nạp trong dãy số này ta quan tâm tới dãy số Fibonacci, dãy sốcó nhiều ứng dụng và tính chất hay. Dãy số Fibonacci được định nghĩa như sau:F0= 0, F1= 1 và với mọi n ≥ 2 thì Fn= Fn−2+ Fn−1.Ta có dãy số Fibonacci cụ thể: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .Ta xét các ví dụ sau đây trên dãy số Fibonacci.Bài toán 1.8. Chứng minh rằng nếu n ≥ 1 thì Fn≤74n−1.21Chương 1. PHƯƠNG PHÁP QUY NẠPLời giải. Ta kí hiệu P [n] là mệnh đề Fn≤74n−1với n ≥ 1.1. Bước cơ sở. Với n = 1 thì F1= 1 =740.Với n = 2 thì F2= 1 √n. [1.18]Lời giải.1. Bước cơ sở. Với n = 2 ta có 1 +1√2>√2, hiển nhiên đúng.Bất đẳng thức đúng với n = 2.2. Bước quy nạp. Giả sử [1.18] đúng với n = k ≥ 2 [k ∈ Z+], khi đó1√1+1√2+ . . . +1√k>√k. [1.19]Ta cần chứng minh bất đẳng thức [1.18] đúng với n = k + 1, nghĩa là1√1+1√2+ . . . +1√k+1√k + 1>√k + 1. [1.20]Thật vậy, ta có1√1+1√2+ . . . +1√k+1√k + 1>√k +1√k + 1[theo [1.19]].Mặt khác,√k +1√k + 1>√k + 1 ⇐⇒1√k + 1>√k + 1 −√k. [1.21]Chia cả 2 vế của bất đẳng thức [1.21] cho√k + 1 −√k > 0 ta được1√k + 1[√k + 1 −√k]> 1⇐⇒√k + 1 +√k√k + 1> 1⇐⇒1 +√k√k + 1> 1 [Hiển nhiên đúng].Vậy bất đẳng thức [1.18] đúng với n = k + 1 nên theo nguyên lý quy nạp nóđúng với mọi số nguyên n > 1.Bài toán 1.13. Chứng minh rằng với mọi n nguyên dương, a là số thực khôngâm, thìa + 1 +a + 2 + +√a + n < a + 3. [1.22]25