Phương pháp quy nạp toán học
Quy nạp toán học là phương pháp chứng minh toán học dùng để chứng minh một mệnh đề về bất kì tập hợp nào được xếp theo thứ tự.
Ta thường xét đến 2 loại quy nạp: Quy nạp cấu trúc và quy nạp siêu hạn, ở đây chúng ta chủ yếu đề cập đến quy nạp cấu trúc.
2. Phương pháp quy nạp toán học
Quy nạp toán học là hình thức chúng minh trực tiếp thường được thực hiện theo 2 bước:
- Bước cơ sở: Chứng minh mệnh đề đúng với số tự nhiên đầu tiên.
- Bước quy nạp: Giả định mệnh đề đúng với số tự nhiên bất kì ta chứng minh nó đúng với số tự nhiên tiếp theo.
a. Quy nạp cấu trúc
- Bước cơ sở: Chứng minh mệnh đề đúng với số tự nhiên đầu tiên, thường là n = 0 hoặc n = 1
- Bước quy nạp: Giả sử mệnh đề đúng với n (giả thiết quy nạp), sau đó cũng đúng với n + 1
Chú ý: Việc chọn số tự nhiên ở bước cơ sở ta dựa vào định nghĩa của số đó.
b. Quy nạp siêu hạn
- Quy nạp siêu hạn là mở rộng của quy nạp toán học cho các tập hợp sắp thứ tự tốt.
- Giả sử A(n) là thuộc tính xác định cho tất cả số thứ tự n. Giả sử A(m) đúng cho tất cả m < n thì A(n) cũng đúng. Quy nạp cho ta biết A luôn đúng cho tất cả các số thứ tự.
Quy trình 3 bước:
- Bước cơ sở: Chứng minh A(0) đúng.
- Bước quy nạp: Chứng minh với tất cả các số thứ tự bất kì tiếp theo n + 1
A(n + 1) là hệ quả của A(n).
- Bước giới hạn: Chứng minh rằng với mọi thứ tự giới hạn k, A(k) là hệ quả của A(m) với mọi m < k.
Kết luận
Để chứng minh những mệnh đề liên quan đến số tự nhiên 
\(n \in {\mathbb{N}^*}\) là đúng với mọi \(n\) mà không thể trực tiếp được thì có thể làm như sau:
Bước 1: Kiểm tra mệnh đề đúng với \(n=1\).
Bước 2: Giả thiết mệnh đề đúng với một số tự nhiên bất kì \(n=k\ge 1\) (gọi là giả thiết quy nạp), chứng minh rằng nó cũng đúng với \(n=k+1\).
Ví dụ: Chứng minh mệnh đề: "\({n^3} + 2n\) chia hết cho 3" đúng với mọi \(n \in {\mathbb{N}^*}\).
Hướng dẫn giải
Gọi \({A_n}\) là mệnh đề \({n^3} + 2n\) chia hết cho 3 với mọi \(n \in {\mathbb{N}^*}\).
Ta dùng phương pháp quy nạp toán học chứng minh mệnh đề này đúng.
Với \(n=1\) khi đó \({A_1} = {1^3} + 2.1 = 3 \vdots 3\)
Giả sử \({A_n}\) đúng với \(n = k,k \geqslant 1\), khi đó \({A_k} = \left( {{k^3} + 2.k} \right) \vdots 3\)
Ta cần chứng minh \({A_n}\) đúng với \(n=k+1\), thật vậy ta có:
\(\begin{matrix}
{A_{k + 1}} = {\left( {k + 1} \right)^3} + 2.\left( {k + 1} \right) \hfill \\
= {k^3} + 2k + 3{k^2} + 3k + 3 \hfill \\
= {A_n} + 3\left( {{k^2} + k + 1} \right) \vdots 3 \hfill \\
\Rightarrow {A_{k + 1}} \vdots 3 \hfill \\
\end{matrix}\)
Ví dụ: Chứng minh với mọi \(n \in {\mathbb{N}^*}\) ta có đẳng thức:
\(2 + 5 + 8 + ... + \left( {3n - 1} \right) = \frac{{n\left( {3n + 1} \right)}}{2}\)
Hướng dẫn giải
Với \(n=1\) thì \(2 = \frac{{1.\left( {3.2 + 1} \right)}}{2}\) (đúng)
Giả sử đẩng thức đúng với \(n = k,k \geqslant 1\), khi đó
\(2 + 5 + 8 + ... + \left( {3k - 1} \right) = \frac{{k\left( {3k + 1} \right)}}{2}\)
Ta cần chứng minh đẳng thức đúng với \(n=k+1\) tức là:
\(\begin{matrix}
2 + 5 + 8 + ... + \left( {3k - 1} \right) + \left( {3k + 2} \right) \hfill \\
= \dfrac{{\left( {k + 1} \right)\left( {3k + 4} \right)}}{2} \hfill \\
\end{matrix}\)
Thật vậy ta có:
\(\begin{matrix}
2 + 5 + 8 + ... + \left( {3k - 1} \right) + \left( {3k + 2} \right) \hfill \\
= \dfrac{{k\left( {3k + 1} \right)}}{2} + \left( {3k + 2} \right) \hfill \\
= \dfrac{{3{k^2} + 7k + 4}}{2} \hfill \\
= \dfrac{{\left( {k + 1} \right)\left( {3k + 4} \right)}}{2} \hfill \\
\end{matrix}\)
Điều cần chứng minh.
