Biểu tượng chim cắt của Kestrel Exams KESTREL EXAMSLUYỆN TẬP ĐỂ ĐẠT
Bản dịch này do AI thực hiện và chưa được người bản ngữ kiểm duyệt. Nếu có khác biệt, bản tiếng Anh là bản chính. Mã nguồn được giữ nguyên bằng tiếng Anh. Ứng dụng luyện tập và tài liệu cho các kỳ thi chứng chỉ của Hoa Kỳ chỉ có bằng tiếng Anh. Read in English
Discrete MathĐọc trong 10 phút

Cách viết một chứng minh quy nạp

Xếp các quân domino, đẩy ngã quân đầu tiên, và đảm bảo mỗi quân với tới được quân kế tiếp. Đó là toàn bộ ý tưởng — và chứng minh bạn phải nộp chỉ là hai phép kiểm tra đó, được viết theo cách người chấm mong đợi.

Luyện tập chủ đề này trong ứng dụng miễn phí →Tất cả bài hướng dẫn Discrete Math

Một hàng domino#

Dựng một hàng domino dài đứng thẳng. Bạn muốn mọi quân đều ngã. Bạn không thể đẩy từng quân một, vì có vô hạn quân.

Vì vậy chúng ta kiểm tra hai điều thay vào đó:

  1. Đẩy ngã quân đầu tiên.
  2. Đảm bảo mỗi quân domino đủ gần để đánh trúng quân sau nó.
1. knock the first one over2. each one hits the next…so they all fall

Hai sự kiện đó cùng nhau đảm bảo cả hàng sẽ ngã, và bạn không bao giờ phải kiểm tra từng quân. Quân đầu ngã vì bạn đã đẩy nó. Quân thứ hai ngã vì quân đầu đánh trúng nó. Quân thứ ba ngã vì quân thứ hai đánh trúng nó — và cứ thế mãi mãi.

Đó hoàn toàn là chứng minh quy nạp. Mọi thứ bên dưới là cùng hai phép kiểm tra đó được viết theo dạng người chấm sẽ chấp nhận.

P(n) nghĩa là gì, và vì sao bạn viết nó ra trước#

Quy nạp chứng minh một mệnh đề thực chất là vô hạn mệnh đề — mỗi số nguyên một mệnh đề. Chúng ta viết P(n) cho “mệnh đề, với số n trong đó”. Đó là một quân domino.

Nếu khẳng định là n số nguyên đầu tiên có tổng là n(n+1)/2, thì P(3) là câu cụ thể “1 + 2 + 3 = 3·4/2”. P(4) là một câu khác. Có một câu cho mỗi n, chính xác là lý do bạn không thể kiểm tra từng câu một.

Trước khi làm bất cứ điều gì khác, hãy viết câu “Gọi P(n) là ___” và điền vào một mệnh đề thật sự — một phương trình, một bất đẳng thức, một khẳng định chia hết. Hầu hết điểm bị mất ở chủ đề này bị mất ở hai dòng đầu, không phải hai dòng cuối. Một khi P(n) đã được viết ra, hai thứ khác bạn cần chỉ là các phép thế:

Bạn cầnCách có được nó
P(n₀) — cái đầu tiênĐặt số bắt đầu vào P(n).
P(k) — điều bạn được giả sửĐặt k vào P(n). Giả sử nó đúng.
P(k+1) — điều bạn phải đạt tớiĐặt k+1 vào P(n) — ở mọi chỗ n xuất hiện, kể cả bên trong công thức ở vế phải.

Dòng cuối đó là nơi các lỗi đại số bắt đầu. Trong một công thức tổng, n xuất hiện hai lần — là số cuối cùng bạn cộng, và bên trong công thức ở vế phải. Cả hai đều thay đổi.

Bộ khung để sao chép mỗi lần#

Hãy sao chép hình dạng này mỗi lần. Các nhãn không phải để trang trí; người chấm tìm chúng, và chứng minh đọc như chưa hoàn tất nếu thiếu chúng.

Bốn phần

Khẳng định. Với mọi n ≥ n₀, P(n).
Chứng minh. Bằng quy nạp theo n.
Bước cơ sở (quân domino đầu tiên). P(n₀) nói rằng [viết ra]. Kiểm tra: [tính cả hai vế]. Vậy P(n₀) đúng.
Bước quy nạp (mỗi quân đánh trúng quân kế tiếp). Cho k ≥ n₀ bất kỳ và giả sử P(k) — tức là, [viết P(k) ra đầy đủ]. Ta chỉ ra P(k+1), tức là, [viết P(k+1) ra đầy đủ]. [Phần làm việc có dùng P(k) ở đâu đó.] Vậy P(k) → P(k+1).
Kết luận. Theo quy nạp, P(n) đúng với mọi n ≥ n₀. ∎

Bốn phần có nhãn. Nếu thiếu một phần, chứng minh là chưa hoàn chỉnh ngay cả khi mọi dòng đại số đều hoàn hảo.

Một từ trong đó là then chốt: bất kỳ (arbitrary). Nó có nghĩa là bạn chọn một k nhưng không giả sử điều gì đặc biệt về nó, nên điều bạn chứng minh đúng với mọi k. Đó là điều biến một lập luận thành vô hạn lập luận.

Ví dụ có lời giải — một tổng#

Khẳng định. Với mọi n ≥ 1,   1³ + 2³ + ⋯ + n³ = [n(n+1)/2]².

Gọi P(n) là phương trình đó.

Bước cơ sở. P(1) nói rằng 1³ = [1·2/2]². Vế trái là 1. Vế phải là 1² = 1. Chúng bằng nhau, nên P(1) đúng. Quân domino đầu tiên đã ngã.

Bước quy nạp. Cho k ≥ 1 và giả sử P(k):

1³ + 2³ + ⋯ + k³ = [k(k+1)/2]²

Ta phải đạt tới P(k+1):

1³ + 2³ + ⋯ + k³ + (k+1)³ = [(k+1)(k+2)/2]²

Bắt đầu từ vế trái của P(k+1) và tách số hạng cuối ra. Đây là nước đi cho giả thiết đi vào — và là bước khéo duy nhất trong cả chứng minh:

1³ + ⋯ + k³ + (k+1)³
= [k(k+1)/2]² + (k+1)³   (đây là chỗ P(k) được dùng)
= k²(k+1)²/4 + (k+1)³
= (k+1)²[ k²/4 + (k+1) ]   (đặt (k+1)² ra ngoài làm thừa số chung)
= (k+1)² · (k² + 4k + 4)/4
= (k+1)²(k+2)²/4
= [(k+1)(k+2)/2]²

Đó chính xác là vế phải của P(k+1). Vậy P(k) → P(k+1). Mỗi quân domino đánh trúng quân kế tiếp. Theo quy nạp, công thức đúng với mọi n ≥ 1. ∎

Mẫu để dùng lại

Viết vế trái của P(k+1) · tách số hạng thứ (k+1) ra · thay phần còn lại bằng công thức P(k) cho bạn · làm đại số cho đến khi nó khớp với vế phải của P(k+1).

Bạn luôn biết mình đang đi đến đâu, vì bạn đã viết P(k+1) ra trước khi bắt đầu. Điều đó khiến đây là phân tích thành thừa số hướng tới một đáp án đã biết, không phải là khám phá.

Ví dụ có lời giải — một khẳng định chia hết#

Khẳng định. Với mọi n ≥ 0,   3 chia hết n³ − n.

Gọi P(n) là “3 chia hết n³ − n”.

Bước cơ sở. P(0): 0³ − 0 = 0, và 3 chia hết 0. Đúng.

Bước quy nạp. Giả sử P(k). Đây là thói quen làm cho điều này thành công: biến từ “chia hết” thành một phương trình. “3 chia hết k³ − k” có nghĩa là k³ − k = 3m với một số nguyên m nào đó. Một phương trình có thể thay thế vào; một từ thì không.

(k+1)³ − (k+1) = k³ + 3k² + 3k + 1 − k − 1
= (k³ − k) + 3k² + 3k
= 3m + 3(k² + k)   (P(k) được dùng ở đây)
= 3(m + k² + k)

Vì m + k² + k là một số nguyên, 3 chia hết (k+1)³ − (k+1). Vậy P(k) → P(k+1). ∎

Lỗi làm mất nhiều điểm nhất#

Nếu bước quy nạp của bạn không bao giờ dùng giả thiết, bạn chưa viết một chứng minh quy nạp — bạn đã chứng minh P(k+1) từ đầu, và toàn bộ cấu trúc chỉ là diễn kịch.

Hãy kiểm tra trực tiếp: chỉ vào dòng mà P(k) đi vào. Trong tổng ở trên, đó là dòng được đánh dấu “đây là chỗ P(k) được dùng”. Trong chứng minh chia hết, đó là chỗ 3m thay cho k³ − k. Nếu bạn không thể chỉ vào một dòng như vậy, chứng minh bị hỏng dù đại số trông gọn gàng đến đâu.

Nửa còn lại của cùng một lỗi

Đừng giả sử P(k+1). Đó là điều bạn đang cố chứng minh, và giả sử nó là lập luận vòng tròn. Bạn giả sử P(k) và không gì khác.

Quân domino đầu tiên đặt ở đâu#

Bước cơ sở trông như phần tầm thường. Nó không phải vậy — nó là cú đẩy bắt đầu mọi thứ, và nếu thiếu nó, một chuỗi các quân domino hoàn toàn tốt chỉ đứng đó.

Đây là một khẳng định có bước quy nạp hoàn hảo và không có bước cơ sở: n số nguyên đầu tiên có tổng là (n² + n + 2)/2. Giả sử nó đúng với k, cộng k+1, và đại số chạy trơn tru. Nhưng P(1) nói rằng 1 = 2, là sai — nên công thức sai với mọi n. Bước quy nạp chỉ luôn nói “nếu một quân domino đổ, quân kế tiếp cũng đổ”. Nếu không quân nào từng đổ, điều đó vẫn đúng và hoàn toàn vô dụng.

Và hãy kiểm tra quân domino đầu tiên thực sự đứng ở đâu. Bất đẳng thức 2ⁿ > n² là sai tại n = 2, 3 và 4, và lần đầu trở nên đúng tại n = 5. Vậy chứng minh bắt đầu tại n = 5, và bước quy nạp chỉ cần đúng với k ≥ 5.

Những chỗ dễ sai#

  • Không bao giờ dùng giả thiết. Lỗi cốt lõi. Hãy chỉ vào dòng mà P(k) đi vào.
  • Giả sử P(k+1). Vòng tròn. Bạn giả sử P(k), và chỉ P(k).
  • Chỉ thay k+1 ở một số chỗ. Mọi n đều thay đổi, kể cả bên trong công thức ở vế phải.
  • Bỏ qua bước cơ sở. Viết thì rẻ, bỏ thì chết người — ví dụ (n² + n + 2)/2 ở trên chính xác là cái giá phải trả.
  • Bắt đầu sai số. Hãy kiểm tra nơi khẳng định lần đầu trở nên đúng. Với 2ⁿ > n² đó là n = 5, không phải n = 1.
  • Để giả thiết chia hết ở dạng chữ. Hãy biến “3 chia hết k³ − k” thành “k³ − k = 3m” để bạn có thể thay vào.
  • Dừng trước đích. Bước kết thúc khi biểu thức của bạn khớp chính xác với vế phải của P(k+1). Hãy viết đích đó ra trước để bạn biết khi nào đã đến nơi.
  • Quên từ “bất kỳ”. Nó là điều làm cho một lập luận bao phủ mọi số.

Tự kiểm tra trong ứng dụng Kestrel Exams miễn phí

Luyện tập Toán rời rạc là miễn phí và dùng được khi không có mạng, với các bài luyện chọn theo chủ đề về quy nạp, quy nạp mạnh, phương pháp chứng minh và logic.

Luyện quy nạp toán học →

Câu hỏi thường gặp#

Hai bước của một chứng minh quy nạp là gì?

Bước cơ sở kiểm tra khẳng định tại số bắt đầu, thường là 0 hoặc 1 — đó là đẩy ngã quân domino đầu tiên. Bước quy nạp chứng minh rằng nếu khẳng định đúng tại một số k nào đó, thì nó cũng đúng tại k+1 — đó là mỗi quân domino đủ gần để đánh trúng quân kế tiếp. Cùng nhau chúng bao phủ mọi số từ điểm bắt đầu trở đi.

Giả thiết quy nạp là gì?

Đó là giả sử rằng P(k) đúng với một k bất kỳ. Bạn được phép giả sử nó, và bạn phải thực sự dùng nó — nếu phần làm việc của bạn ở k+1 không bao giờ quay lại nó, bạn chưa viết một chứng minh quy nạp.

Vì sao tôi không thể bỏ qua bước cơ sở?

Vì bước quy nạp chỉ nói “nếu một quân domino đổ, quân kế tiếp cũng đổ.” Điều đó có thể hoàn toàn đúng trong khi không có quân nào từng đổ. Khẳng định rằng n số nguyên đầu tiên có tổng là (n² + n + 2)/2 có bước quy nạp hoàn hảo và sai với mọi n, vì nó thất bại tại n = 1.

Tôi có luôn bắt đầu từ n = 1 không?

Không. Hãy bắt đầu từ nơi khẳng định lần đầu trở nên đúng. 2ⁿ > n² là sai tại n = 2, 3 và 4 và lần đầu đúng tại n = 5, nên chứng minh của nó bắt đầu tại n = 5 và bước quy nạp chỉ cần đúng với k ≥ 5.

Đề xuất chỉnh sửa

Có chỗ nào chưa rõ? Có chủ đề nào bạn muốn chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có bài hướng dẫn mới: một số bài ở đây ra đời vì có người hỏi.