Quy nạp toán học

Để chứng minh P(n) với mọi số nguyên $n\ge n_0$: Kiểm tra trường hợp cơ sở $n_0$, rồi giả sử P(k) đúng và chứng minh $P(k+1)$. Hai bước đi cùng nhau: Bước cơ sở khởi đầu chuỗi, bước suy diễn truyền tính đúng sang số tiếp theo.

Lĩnh vực: Logic & toán rời rạc

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Bài giảng dùng khái niệm này

• Phân tích độ phức tạpCTDL & Giải thuật

Giải thích kỹ thuật

Giả thiết quy nạp không phải kết luận đã chứng minh. Nó chỉ được dùng trong bước suy diễn để đi từ k tới $k+1$. Quy nạp mạnh cho phép giả sử mọi trường hợp từ $n_0$ đến k đúng.

Cách này hữu ích với có nhiều bài toán con. Trước khi áp dụng, kiểm tra mọi bài toán con đều nhỏ hơn bài toán hiện tại và các trường hợp cơ sở đã đủ.

Ví dụ

$1+2+\dots +n=\frac{n(n+1)}{2}$: Đúng ở $n=1$. Cộng thêm $k+1$ vào công thức tại k để thu được công thức tại $k+1$.

Khi nào cần dùng?

Chứng minh thuật toán , công thức tổng và bất biến.

Câu hỏi ôn lại

Chỉ chứng minh $P(k)\to P(k+1)$ đã đủ chưa?

Xem đáp án

Chưa. Cần trường hợp cơ sở đúng để bắt đầu chuỗi.

Thuật ngữ liên quan

• Tổ hợp & giai thừa
• Vị từ & lượng từ
• Tập hợp