Phương pháp quy nạp toán học: Cách chứng minh quy nạp và bài tập

Phương pháp quy nạp toán học là một trong những phương pháp chứng minh quan trọng và mạnh mẽ nhất trong Toán học, được sử dụng để chứng minh các mệnh đề phụ thuộc vào số tự nhiên n. Phương pháp quy nạp toán học gồm hai bước: Bước cơ sở (kiểm tra mệnh đề đúng với n = n₀) và Bước quy nạp (chứng minh nếu mệnh đề đúng với n = k thì cũng đúng với n = k + 1). Bài viết dưới đây sẽ giúp bạn nắm vững nguyên lý, các bước thực hiện và ứng dụng của phương pháp này.

1. Phương pháp quy nạp toán học là gì?

Trước khi tìm hiểu chi tiết về phương pháp quy nạp toán học, cần hiểu rõ khái niệm:

1.1. Định nghĩa

Phương pháp quy nạp toán học (Mathematical Induction) là phương pháp chứng minh một mệnh đề P(n) đúng với mọi số tự nhiên n ≥ n₀, bằng cách:

• Chứng minh mệnh đề đúng với giá trị đầu tiên
• Chứng minh tính “lan truyền” từ n sang n + 1

1.2. Ý tưởng trực quan

Hình ảnh domino: Nếu ta có một dãy quân domino xếp thẳng hàng:

• Điều kiện 1: Quân đầu tiên đổ
• Điều kiện 2: Nếu quân thứ k đổ thì quân thứ k + 1 cũng đổ

⟹ Kết luận: Tất cả các quân domino đều đổ

1.3. Lịch sử

Phương pháp quy nạp được sử dụng từ thời cổ đại, nhưng được hình thức hóa bởi nhà toán học Blaise Pascal (thế kỷ 17) và được đặt tên bởi Augustus De Morgan (thế kỷ 19).

1.4. Phạm vi áp dụng

Loại mệnh đề	Ví dụ
Đẳng thức	1 + 2 + … + n = n(n+1)/2
Bất đẳng thức	2ⁿ > n với n ≥ 1
Tính chia hết	n³ − n chia hết cho 6
Công thức dãy số	Công thức tổng quát uₙ
Tính chất hình học	Số đường chéo đa giác n cạnh

2. Nguyên lý quy nạp toán học

Cơ sở lý thuyết của phương pháp quy nạp toán học:

2.1. Phát biểu nguyên lý

Nguyên lý quy nạp toán học: Cho P(n) là mệnh đề phụ thuộc vào số tự nhiên n. Nếu:

1. P(n₀) đúng (với n₀ là số tự nhiên nào đó)
2. ∀k ≥ n₀: P(k) đúng ⟹ P(k+1) đúng

Thì P(n) đúng với mọi n ≥ n₀.

2.2. Ký hiệu logic

\[ [P(n_0) \land (\forall k \geq n_0: P(k) \Rightarrow P(k+1))] \Rightarrow \forall n \geq n_0: P(n) \]

2.3. Giải thích nguyên lý

Từ hai điều kiện trên:

• P(n₀) đúng (theo điều kiện 1)
• P(n₀) đúng ⟹ P(n₀+1) đúng (theo điều kiện 2)
• P(n₀+1) đúng ⟹ P(n₀+2) đúng (theo điều kiện 2)
• …

Cứ như vậy, P(n) đúng với mọi n ≥ n₀.

2.4. Tại sao cần cả hai bước?

Thiếu bước	Hậu quả	Ví dụ phản chứng
Thiếu bước cơ sở	Không có điểm bắt đầu	“n² = n + 1”: đúng khi k ⟹ k+1 nhưng không có n nào thỏa mãn
Thiếu bước quy nạp	Không có tính lan truyền	Kiểm tra P(1), P(2), P(3) đúng không đảm bảo P(100) đúng

2.5. Tiên đề Peano

Nguyên lý quy nạp tương đương với Tiên đề Peano thứ 5 về tập số tự nhiên:

“Nếu tập S ⊆ ℕ thỏa mãn: 1 ∈ S và (k ∈ S ⟹ k+1 ∈ S) thì S = ℕ”

3. Các bước chứng minh bằng quy nạp

Quy trình thực hiện phương pháp quy nạp toán học:

3.1. Sơ đồ các bước

Bước 1: Kiểm tra cơ sở (Base Case)

Chứng minh P(n₀) đúng (thường n₀ = 0 hoặc n₀ = 1)

Bước 2: Giả thiết quy nạp (Inductive Hypothesis)

Giả sử P(k) đúng với k ≥ n₀ tùy ý

Bước 3: Chứng minh quy nạp (Inductive Step)

Chứng minh P(k+1) đúng (sử dụng giả thiết P(k) đúng)

Bước 4: Kết luận

Theo nguyên lý quy nạp, P(n) đúng với mọi n ≥ n₀

3.2. Mẫu trình bày

Mẫu chuẩn:

“Chứng minh bằng quy nạp theo n:

Bước 1 (Cơ sở): Với n = n₀, ta có [kiểm tra P(n₀)]… Vậy P(n₀) đúng.

Bước 2 (Quy nạp): Giả sử P(k) đúng với k ≥ n₀, tức là [viết P(k)].

Ta cần chứng minh P(k+1) đúng, tức là [viết P(k+1)].

Thật vậy, [tiến hành chứng minh, sử dụng giả thiết quy nạp]…

Vậy P(k+1) đúng.

Kết luận: Theo nguyên lý quy nạp, P(n) đúng với mọi n ≥ n₀.”

3.3. Ví dụ minh họa cơ bản

Ví dụ: Chứng minh: \( 1 + 2 + 3 + … + n = \frac{n(n+1)}{2} \) với mọi n ≥ 1

Lời giải:

Đặt P(n): \( 1 + 2 + … + n = \frac{n(n+1)}{2} \)

Bước 1 (Cơ sở): Với n = 1:

• VT = 1
• VP = 1(1+1)/2 = 1

VT = VP, nên P(1) đúng. ✓

Bước 2 (Quy nạp): Giả sử P(k) đúng với k ≥ 1, tức là:

\[ 1 + 2 + … + k = \frac{k(k+1)}{2} \quad (*) \]

Ta chứng minh P(k+1) đúng, tức là:

\[ 1 + 2 + … + k + (k+1) = \frac{(k+1)(k+2)}{2} \]

Thật vậy:

\[ 1 + 2 + … + k + (k+1) = \frac{k(k+1)}{2} + (k+1) \quad \text{(theo (*))} \]

\[ = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2} \]

Vậy P(k+1) đúng. ✓

Kết luận: Theo nguyên lý quy nạp, đẳng thức đúng với mọi n ≥ 1. ∎

3.4. Bảng tóm tắt

Bước	Nội dung	Lưu ý
1. Cơ sở	Kiểm tra P(n₀)	Thường n₀ = 1 hoặc n₀ = 0
2. Giả thiết	Giả sử P(k) đúng	k là số tự nhiên tùy ý ≥ n₀
3. Chứng minh	CM P(k+1) từ P(k)	Phải sử dụng giả thiết quy nạp
4. Kết luận	P(n) đúng ∀n ≥ n₀	Viện dẫn nguyên lý quy nạp

4. Quy nạp toán học mạnh (Quy nạp hoàn toàn)

Biến thể mạnh hơn của phương pháp quy nạp toán học:

4.1. Phát biểu

Nguyên lý quy nạp mạnh: Nếu:

1. P(n₀) đúng
2. ∀k ≥ n₀: [P(n₀) ∧ P(n₀+1) ∧ … ∧ P(k)] ⟹ P(k+1)

Thì P(n) đúng với mọi n ≥ n₀.

4.2. Sự khác biệt

Quy nạp thường	Quy nạp mạnh
Giả sử P(k) đúng	Giả sử P(n₀), P(n₀+1), …, P(k) đều đúng
Dùng P(k) để CM P(k+1)	Dùng tất cả P(i) với i ≤ k để CM P(k+1)
Phù hợp với công thức truy hồi 1 bước	Phù hợp với công thức truy hồi nhiều bước

4.3. Khi nào dùng quy nạp mạnh?

• Dãy số Fibonacci: uₙ = uₙ₋₁ + uₙ₋₂
• Chứng minh mọi số nguyên > 1 phân tích được thành tích số nguyên tố
• Bài toán chia kẹo, bài toán đổi tiền

4.4. Ví dụ quy nạp mạnh

Ví dụ: Chứng minh mọi số nguyên n ≥ 2 đều phân tích được thành tích các số nguyên tố.

Lời giải:

Bước 1 (Cơ sở): n = 2 là số nguyên tố nên phân tích được (chính nó). ✓

Bước 2 (Quy nạp mạnh): Giả sử mọi số nguyên từ 2 đến k đều phân tích được thành tích các số nguyên tố.

Xét n = k + 1:

• Nếu k + 1 là số nguyên tố: đã phân tích được (chính nó).
• Nếu k + 1 là hợp số: k + 1 = a × b với 2 ≤ a, b ≤ k.

Theo giả thiết quy nạp, a và b đều phân tích được thành tích số nguyên tố.

Do đó k + 1 = a × b cũng phân tích được.

Kết luận: Mọi số nguyên n ≥ 2 đều phân tích được thành tích số nguyên tố. ∎

4.5. Quy nạp với nhiều cơ sở

Đôi khi cần kiểm tra nhiều giá trị cơ sở:

Ví dụ: Dãy Fibonacci uₙ = uₙ₋₁ + uₙ₋₂ cần kiểm tra cả u₁ và u₂.

5. Chứng minh đẳng thức bằng quy nạp

Ứng dụng phương pháp quy nạp toán học chứng minh đẳng thức:

5.1. Các dạng đẳng thức thường gặp

Dạng	Ví dụ
Tổng số tự nhiên	\( \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \)
Tổng bình phương	\( \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \)
Tổng lập phương	\( \sum_{i=1}^{n} i^3 = \frac{n^2(n+1)^2}{4} \)
Tổng cấp số nhân	\( \sum_{i=0}^{n} r^i = \frac{r^{n+1}-1}{r-1} \)
Tổng lồng nhau	\( \sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1} \)

5.2. Kỹ thuật chứng minh

Mẹo quan trọng: Khi chứng minh P(k+1), tách riêng số hạng thứ (k+1):

\[ \sum_{i=1}^{k+1} f(i) = \sum_{i=1}^{k} f(i) + f(k+1) = [\text{áp dụng giả thiết}] + f(k+1) \]

5.3. Ví dụ: Tổng bình phương

Đề bài: Chứng minh \( 1^2 + 2^2 + … + n^2 = \frac{n(n+1)(2n+1)}{6} \) với mọi n ≥ 1

Lời giải:

Bước 1 (Cơ sở): Với n = 1:

• VT = 1² = 1
• VP = 1·2·3/6 = 1

VT = VP ✓

Bước 2 (Quy nạp): Giả sử đẳng thức đúng với n = k:

\[ 1^2 + 2^2 + … + k^2 = \frac{k(k+1)(2k+1)}{6} \quad (*) \]

Chứng minh đúng với n = k + 1:

\[ 1^2 + 2^2 + … + k^2 + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \]

\[ = \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} = \frac{(k+1)[k(2k+1) + 6(k+1)]}{6} \]

\[ = \frac{(k+1)(2k^2 + 7k + 6)}{6} = \frac{(k+1)(k+2)(2k+3)}{6} \]

\[ = \frac{(k+1)[(k+1)+1][2(k+1)+1]}{6} \]

Đây chính là công thức với n = k + 1. ✓

Kết luận: Đẳng thức đúng với mọi n ≥ 1. ∎

5.4. Bảng công thức tổng quan trọng

Tổng	Công thức
\( \sum_{i=1}^{n} i \)	\( \frac{n(n+1)}{2} \)
\( \sum_{i=1}^{n} i^2 \)	\( \frac{n(n+1)(2n+1)}{6} \)
\( \sum_{i=1}^{n} i^3 \)	\( \left[\frac{n(n+1)}{2}\right]^2 \)
\( \sum_{i=1}^{n} (2i-1) \)	\( n^2 \)
\( \sum_{i=0}^{n} 2^i \)	\( 2^{n+1} – 1 \)

6. Chứng minh bất đẳng thức bằng quy nạp

Ứng dụng phương pháp quy nạp toán học cho bất đẳng thức:

6.1. Các dạng BĐT thường gặp

Dạng	Ví dụ
So sánh lũy thừa	2ⁿ > n, 2ⁿ > n²
BĐT giai thừa	n! > 2ⁿ (với n đủ lớn)
BĐT Bernoulli	(1+x)ⁿ ≥ 1 + nx
BĐT tổng	1 + 1/2 + … + 1/n < 2√n

6.2. Kỹ thuật chứng minh

Phương pháp: Từ P(k), biến đổi để dẫn đến P(k+1)

Mẹo: Thường cần ước lượng hoặc sử dụng BĐT phụ

6.3. Ví dụ: BĐT 2ⁿ > n

Đề bài: Chứng minh 2ⁿ > n với mọi n ≥ 1

Lời giải:

Bước 1 (Cơ sở): Với n = 1: 2¹ = 2 > 1 ✓

Bước 2 (Quy nạp): Giả sử 2ᵏ > k với k ≥ 1

Ta chứng minh 2ᵏ⁺¹ > k + 1:

\[ 2^{k+1} = 2 \cdot 2^k > 2k \quad \text{(theo giả thiết quy nạp)} \]

Ta cần: 2k ≥ k + 1 ⟺ k ≥ 1 (đúng với mọi k ≥ 1)

Vậy 2ᵏ⁺¹ > 2k ≥ k + 1, tức 2ᵏ⁺¹ > k + 1 ✓

Kết luận: 2ⁿ > n với mọi n ≥ 1. ∎

6.4. Ví dụ: BĐT Bernoulli

Đề bài: Chứng minh (1 + x)ⁿ ≥ 1 + nx với x > −1 và n ≥ 1

Lời giải:

Bước 1 (Cơ sở): Với n = 1: (1+x)¹ = 1 + x = 1 + 1·x ✓

Bước 2 (Quy nạp): Giả sử (1+x)ᵏ ≥ 1 + kx với k ≥ 1

Ta chứng minh (1+x)ᵏ⁺¹ ≥ 1 + (k+1)x:

\[ (1+x)^{k+1} = (1+x)^k \cdot (1+x) \geq (1+kx)(1+x) \]

\[ = 1 + x + kx + kx^2 = 1 + (k+1)x + kx^2 \]

Vì kx² ≥ 0 nên:

\[ (1+x)^{k+1} \geq 1 + (k+1)x \] ✓

Kết luận: BĐT Bernoulli đúng với mọi n ≥ 1. ∎

6.5. Ví dụ: BĐT 2ⁿ > n²

Đề bài: Chứng minh 2ⁿ > n² với mọi n ≥ 5

Lời giải:

Bước 1 (Cơ sở): Với n = 5: 2⁵ = 32 > 25 = 5² ✓

Bước 2 (Quy nạp): Giả sử 2ᵏ > k² với k ≥ 5

Ta chứng minh 2ᵏ⁺¹ > (k+1)²:

\[ 2^{k+1} = 2 \cdot 2^k > 2k^2 \quad \text{(theo giả thiết)} \]

Cần chứng minh: 2k² ≥ (k+1)² = k² + 2k + 1

⟺ k² ≥ 2k + 1 ⟺ k² − 2k − 1 ≥ 0

⟺ (k−1)² ≥ 2 (đúng với k ≥ 5)

Vậy 2ᵏ⁺¹ > 2k² ≥ (k+1)² ✓

Kết luận: 2ⁿ > n² với mọi n ≥ 5. ∎

7. Chứng minh tính chia hết bằng quy nạp

Ứng dụng phương pháp quy nạp toán học cho tính chia hết:

7.1. Các dạng thường gặp

Dạng	Ví dụ
Đa thức của n	n³ − n ⋮ 6
Lũy thừa	4ⁿ − 1 ⋮ 3
Tổ hợp	aⁿ − bⁿ ⋮ (a − b)
Biểu thức phức tạp	11ⁿ⁺² + 12²ⁿ⁺¹ ⋮ 133

7.2. Kỹ thuật chứng minh

Phương pháp: Biểu diễn f(k+1) theo f(k) và một số chia hết cho m

\[ f(k+1) = A \cdot f(k) + B \cdot m \]

Nếu f(k) ⋮ m thì f(k+1) ⋮ m

7.3. Ví dụ: n³ − n chia hết cho 6

Đề bài: Chứng minh n³ − n ⋮ 6 với mọi n ≥ 1

Lời giải:

Bước 1 (Cơ sở): Với n = 1: 1³ − 1 = 0 ⋮ 6 ✓

Bước 2 (Quy nạp): Giả sử k³ − k ⋮ 6 với k ≥ 1

Ta chứng minh (k+1)³ − (k+1) ⋮ 6:

\[ (k+1)^3 – (k+1) = k^3 + 3k^2 + 3k + 1 – k – 1 \]

\[ = (k^3 – k) + 3k^2 + 3k = (k^3 – k) + 3k(k+1) \]

Ta có:

• (k³ − k) ⋮ 6 (theo giả thiết quy nạp)
• k(k+1) là tích hai số liên tiếp nên ⋮ 2
• Do đó 3k(k+1) ⋮ 6

Vậy (k+1)³ − (k+1) ⋮ 6 ✓

Kết luận: n³ − n ⋮ 6 với mọi n ≥ 1. ∎

7.4. Ví dụ: 4ⁿ − 1 chia hết cho 3

Đề bài: Chứng minh 4ⁿ − 1 ⋮ 3 với mọi n ≥ 1

Lời giải:

Bước 1 (Cơ sở): Với n = 1: 4¹ − 1 = 3 ⋮ 3 ✓

Bước 2 (Quy nạp): Giả sử 4ᵏ − 1 ⋮ 3 với k ≥ 1

Ta chứng minh 4ᵏ⁺¹ − 1 ⋮ 3:

\[ 4^{k+1} – 1 = 4 \cdot 4^k – 1 = 4 \cdot 4^k – 4 + 3 = 4(4^k – 1) + 3 \]

Ta có:

• 4(4ᵏ − 1) ⋮ 3 (vì 4ᵏ − 1 ⋮ 3 theo giả thiết)
• 3 ⋮ 3

Vậy 4ᵏ⁺¹ − 1 ⋮ 3 ✓

Kết luận: 4ⁿ − 1 ⋮ 3 với mọi n ≥ 1. ∎

7.5. Ví dụ nâng cao: 11ⁿ⁺² + 12²ⁿ⁺¹ ⋮ 133

Đề bài: Chứng minh 11ⁿ⁺² + 12²ⁿ⁺¹ ⋮ 133 với mọi n ≥ 0

Lời giải:

Đặt f(n) = 11ⁿ⁺² + 12²ⁿ⁺¹. Lưu ý: 133 = 7 × 19

Bước 1 (Cơ sở): f(0) = 11² + 12¹ = 121 + 12 = 133 ⋮ 133 ✓

Bước 2 (Quy nạp): Giả sử f(k) = 11ᵏ⁺² + 12²ᵏ⁺¹ ⋮ 133

Ta chứng minh f(k+1) ⋮ 133:

\[ f(k+1) = 11^{k+3} + 12^{2k+3} = 11 \cdot 11^{k+2} + 144 \cdot 12^{2k+1} \]

\[ = 11 \cdot 11^{k+2} + 11 \cdot 12^{2k+1} + 133 \cdot 12^{2k+1} \]

\[ = 11(11^{k+2} + 12^{2k+1}) + 133 \cdot 12^{2k+1} \]

\[ = 11 \cdot f(k) + 133 \cdot 12^{2k+1} \]

Cả hai số hạng đều ⋮ 133, nên f(k+1) ⋮ 133 ✓

Kết luận: 11ⁿ⁺² + 12²ⁿ⁺¹ ⋮ 133 với mọi n ≥ 0. ∎

8. Chứng minh công thức tổng quát của dãy số

Ứng dụng phương pháp quy nạp toán học cho dãy số:

8.1. Dãy số cho bởi công thức truy hồi

Bài toán: Cho dãy (uₙ) xác định bởi công thức truy hồi. Chứng minh công thức tổng quát.

8.2. Ví dụ: Dãy cấp số cộng

Đề bài: Cho dãy (uₙ): u₁ = a, uₙ₊₁ = uₙ + d. CM: uₙ = a + (n−1)d

Lời giải:

Bước 1 (Cơ sở): u₁ = a + (1−1)d = a ✓

Bước 2 (Quy nạp): Giả sử uₖ = a + (k−1)d

\[ u_{k+1} = u_k + d = [a + (k-1)d] + d = a + kd = a + [(k+1)-1]d \] ✓

Kết luận: uₙ = a + (n−1)d với mọi n ≥ 1. ∎

8.3. Ví dụ: Dãy Fibonacci

Đề bài: Cho dãy Fibonacci: F₁ = F₂ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂ (n ≥ 3)

Chứng minh: F₁ + F₂ + … + Fₙ = Fₙ₊₂ − 1

Lời giải:

Bước 1 (Cơ sở): n = 1: F₁ = 1 và F₃ − 1 = 2 − 1 = 1 ✓

Bước 2 (Quy nạp): Giả sử F₁ + F₂ + … + Fₖ = Fₖ₊₂ − 1

Ta chứng minh: F₁ + F₂ + … + Fₖ + Fₖ₊₁ = Fₖ₊₃ − 1

\[ F_1 + F_2 + … + F_k + F_{k+1} = (F_{k+2} – 1) + F_{k+1} \]

\[ = F_{k+1} + F_{k+2} – 1 = F_{k+3} – 1 \] ✓

Kết luận: F₁ + F₂ + … + Fₙ = Fₙ₊₂ − 1. ∎

8.4. Ví dụ: Công thức Binet

Đề bài: Chứng minh công thức Binet cho dãy Fibonacci:

\[ F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n – \left(\frac{1-\sqrt{5}}{2}\right)^n\right] \]

Lời giải: (Dùng quy nạp mạnh)

Đặt \( \phi = \frac{1+\sqrt{5}}{2} \), \( \psi = \frac{1-\sqrt{5}}{2} \)

Tính chất quan trọng: φ + ψ = 1, φψ = −1, φ² = φ + 1, ψ² = ψ + 1

Bước 1 (Cơ sở):

• n = 1: (φ − ψ)/√5 = √5/√5 = 1 = F₁ ✓
• n = 2: (φ² − ψ²)/√5 = (φ − ψ)(φ + ψ)/√5 = √5·1/√5 = 1 = F₂ ✓

Bước 2 (Quy nạp): Giả sử công thức đúng với n = k và n = k−1

\[ F_{k+1} = F_k + F_{k-1} = \frac{\phi^k – \psi^k}{\sqrt{5}} + \frac{\phi^{k-1} – \psi^{k-1}}{\sqrt{5}} \]

\[ = \frac{\phi^{k-1}(\phi + 1) – \psi^{k-1}(\psi + 1)}{\sqrt{5}} = \frac{\phi^{k-1} \cdot \phi^2 – \psi^{k-1} \cdot \psi^2}{\sqrt{5}} \]

\[ = \frac{\phi^{k+1} – \psi^{k+1}}{\sqrt{5}} \] ✓

Kết luận: Công thức Binet đúng với mọi n ≥ 1. ∎

9. Các sai lầm thường gặp khi dùng quy nạp

Những lỗi cần tránh khi sử dụng phương pháp quy nạp toán học:

9.1. Quên kiểm tra bước cơ sở

Ví dụ sai: “CM: n = n + 1 với mọi n”

Giả sử k = k + 1, thì k + 1 = (k + 1) + 1 = k + 2… (Sai!)

Lỗi: Không có n nào thỏa mãn n = n + 1, nên bước cơ sở sai.

9.2. Không sử dụng giả thiết quy nạp

Ví dụ sai: Trong bước quy nạp, chứng minh P(k+1) mà không dùng P(k).

Lỗi: Không có “cầu nối” giữa các mệnh đề.

9.3. Kiểm tra sai cơ sở

Ví dụ: CM 2ⁿ > n² với n ≥ 1

Bước cơ sở: 2¹ = 2 > 1 = 1² ✓

Nhưng 2² = 4 = 2², 2³ = 8 < 9 = 3², 2⁴ = 16 = 4²

Lỗi: Mệnh đề chỉ đúng với n ≥ 5, không phải n ≥ 1.

9.4. Sai trong bước quy nạp

Ví dụ sai: “CM: Mọi số tự nhiên đều bằng nhau”

P(n): “Trong tập n số tự nhiên bất kỳ, các số đều bằng nhau”

Bước cơ sở: P(1) đúng (tập 1 phần tử)

Quy nạp: Từ P(k), lấy tập k+1 số, bỏ số đầu được k số bằng nhau, bỏ số cuối được k số bằng nhau, nên k+1 số bằng nhau.

Lỗi: Khi k = 1, hai tập “bỏ số đầu” và “bỏ số cuối” không giao nhau, không thể kết luận.

9.5. Bảng sai lầm và cách tránh

Sai lầm	Cách tránh
Quên bước cơ sở	Luôn kiểm tra P(n₀) đầu tiên
Không dùng giả thiết	Chỉ rõ “theo giả thiết quy nạp”
Sai cơ sở	Kiểm tra thêm vài giá trị đầu
Sai logic quy nạp	Viết rõ ràng từng bước biến đổi
Chọn sai n₀	Xác định rõ miền áp dụng

10. Ví dụ và bài tập minh họa có lời giải chi tiết

Để nắm vững phương pháp quy nạp toán học, hãy làm các bài tập sau:

Bài tập 1: Chứng minh đẳng thức tổng lập phương

Đề bài: Chứng minh \( 1^3 + 2^3 + … + n^3 = \frac{n^2(n+1)^2}{4} \) với mọi n ≥ 1

Lời giải:

Bước 1 (Cơ sở): Với n = 1:

• VT = 1³ = 1
• VP = 1²·2²/4 = 1

VT = VP ✓

Bước 2 (Quy nạp): Giả sử đẳng thức đúng với n = k:

\[ 1^3 + 2^3 + … + k^3 = \frac{k^2(k+1)^2}{4} \]

Chứng minh đúng với n = k + 1:

\[ 1^3 + … + k^3 + (k+1)^3 = \frac{k^2(k+1)^2}{4} + (k+1)^3 \]

\[ = \frac{k^2(k+1)^2 + 4(k+1)^3}{4} = \frac{(k+1)^2[k^2 + 4(k+1)]}{4} \]

\[ = \frac{(k+1)^2(k^2 + 4k + 4)}{4} = \frac{(k+1)^2(k+2)^2}{4} \] ✓

Kết luận: Đẳng thức đúng với mọi n ≥ 1. ∎

Bài tập 2: Chứng minh đẳng thức tổng phân số

Đề bài: Chứng minh \( \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + … + \frac{1}{n(n+1)} = \frac{n}{n+1} \)

Lời giải:

Bước 1 (Cơ sở): Với n = 1:

• VT = 1/(1·2) = 1/2
• VP = 1/2

VT = VP ✓

Bước 2 (Quy nạp): Giả sử đẳng thức đúng với n = k:

\[ \frac{1}{1 \cdot 2} + … + \frac{1}{k(k+1)} = \frac{k}{k+1} \]

Chứng minh với n = k + 1:

\[ \frac{1}{1 \cdot 2} + … + \frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)} = \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} \]

\[ = \frac{k(k+2) + 1}{(k+1)(k+2)} = \frac{k^2 + 2k + 1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2} \] ✓

Kết luận: Đẳng thức đúng với mọi n ≥ 1. ∎

Bài tập 3: Chứng minh BĐT n! > 2ⁿ

Đề bài: Chứng minh n! > 2ⁿ với mọi n ≥ 4

Lời giải:

Bước 1 (Cơ sở): Với n = 4: 4! = 24 > 16 = 2⁴ ✓

Bước 2 (Quy nạp): Giả sử k! > 2ᵏ với k ≥ 4

Ta chứng minh (k+1)! > 2ᵏ⁺¹:

\[ (k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k \]

Vì k ≥ 4 nên k + 1 ≥ 5 > 2

Do đó: (k+1)·2ᵏ > 2·2ᵏ = 2ᵏ⁺¹

Vậy (k+1)! > 2ᵏ⁺¹ ✓

Kết luận: n! > 2ⁿ với mọi n ≥ 4. ∎

Bài tập 4: Chứng minh chia hết 7ⁿ − 1 ⋮ 6

Đề bài: Chứng minh 7ⁿ − 1 chia hết cho 6 với mọi n ≥ 1

Lời giải:

Bước 1 (Cơ sở): Với n = 1: 7¹ − 1 = 6 ⋮ 6 ✓

Bước 2 (Quy nạp): Giả sử 7ᵏ − 1 ⋮ 6

Ta chứng minh 7ᵏ⁺¹ − 1 ⋮ 6:

\[ 7^{k+1} – 1 = 7 \cdot 7^k – 1 = 7 \cdot 7^k – 7 + 6 = 7(7^k – 1) + 6 \]

Vì 7ᵏ − 1 ⋮ 6 và 6 ⋮ 6, nên 7ᵏ⁺¹ − 1 ⋮ 6 ✓

Kết luận: 7ⁿ − 1 ⋮ 6 với mọi n ≥ 1. ∎

Bài tập 5: Chứng minh n² + n ⋮ 2

Đề bài: Chứng minh n² + n chia hết cho 2 với mọi n ≥ 1

Lời giải:

Bước 1 (Cơ sở): Với n = 1: 1² + 1 = 2 ⋮ 2 ✓

Bước 2 (Quy nạp): Giả sử k² + k ⋮ 2

Ta chứng minh (k+1)² + (k+1) ⋮ 2:

\[ (k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = (k^2 + k) + 2(k+1) \]

Cả hai số hạng đều ⋮ 2, nên tổng ⋮ 2 ✓

Kết luận: n² + n ⋮ 2 với mọi n ≥ 1. ∎

Bài tập 6: Tổng cấp số nhân

Đề bài: Chứng minh \( 1 + q + q^2 + … + q^n = \frac{q^{n+1} – 1}{q – 1} \) với q ≠ 1

Lời giải:

Bước 1 (Cơ sở): Với n = 0:

• VT = 1
• VP = (q − 1)/(q − 1) = 1

VT = VP ✓

Bước 2 (Quy nạp): Giả sử đẳng thức đúng với n = k:

\[ 1 + q + … + q^k = \frac{q^{k+1} – 1}{q – 1} \]

Chứng minh với n = k + 1:

\[ 1 + q + … + q^k + q^{k+1} = \frac{q^{k+1} – 1}{q – 1} + q^{k+1} \]

\[ = \frac{q^{k+1} – 1 + q^{k+1}(q-1)}{q – 1} = \frac{q^{k+1} – 1 + q^{k+2} – q^{k+1}}{q – 1} \]

\[ = \frac{q^{k+2} – 1}{q – 1} \] ✓

Kết luận: Công thức đúng với mọi n ≥ 0. ∎

Bài tập 7: Số đường chéo đa giác

Đề bài: Chứng minh đa giác lồi n cạnh (n ≥ 3) có \( \frac{n(n-3)}{2} \) đường chéo

Lời giải:

Bước 1 (Cơ sở): Với n = 3 (tam giác): 3(3−3)/2 = 0 đường chéo ✓

Bước 2 (Quy nạp): Giả sử đa giác k cạnh có k(k−3)/2 đường chéo

Xét đa giác (k+1) cạnh. Chọn 1 đỉnh A, kẻ đường chéo đến k−2 đỉnh không kề.

Một đường chéo chia đa giác thành tam giác và đa giác k cạnh.

Số đường chéo = số đường chéo đa giác k cạnh + (k−2) đường chéo mới + 1 đường chéo vừa kẻ

\[ = \frac{k(k-3)}{2} + (k-2) = \frac{k(k-3) + 2(k-2)}{2} = \frac{k^2 – k – 4}{2} \]

Hmm, cần kiểm tra lại…

Cách khác: Đa giác (k+1) cạnh có thêm 1 đỉnh mới so với đa giác k cạnh.

Đỉnh mới nối với k−2 đỉnh không kề (tạo k−2 đường chéo mới).

1 cạnh cũ trở thành đường chéo.

\[ \frac{k(k-3)}{2} + (k-2) + 1 = \frac{k^2 – 3k + 2k – 4 + 2}{2} = \frac{k^2 – k – 2}{2} = \frac{(k+1)(k-2)}{2} = \frac{(k+1)[(k+1)-3]}{2} \] ✓

Kết luận: Công thức đúng với mọi n ≥ 3. ∎

Bài tập 8: BĐT AM-GM cho 2ⁿ số

Đề bài: CM \( \frac{a_1 + a_2 + … + a_{2^n}}{2^n} \geq \sqrt[2^n]{a_1 a_2 … a_{2^n}} \) với aᵢ > 0

Lời giải: (Quy nạp theo n)

Bước 1 (Cơ sở): Với n = 1 (2 số):

\[ \frac{a_1 + a_2}{2} \geq \sqrt{a_1 a_2} \]

⟺ (a₁ + a₂)² ≥ 4a₁a₂ ⟺ (a₁ − a₂)² ≥ 0 ✓

Bước 2 (Quy nạp): Giả sử BĐT đúng với 2ᵏ số.

Với 2ᵏ⁺¹ số, chia thành 2 nhóm, mỗi nhóm 2ᵏ số:

Đặt \( A = \frac{a_1 + … + a_{2^k}}{2^k} \geq \sqrt[2^k]{a_1…a_{2^k}} \)

Đặt \( B = \frac{a_{2^k+1} + … + a_{2^{k+1}}}{2^k} \geq \sqrt[2^k]{a_{2^k+1}…a_{2^{k+1}}} \)

\[ \frac{a_1 + … + a_{2^{k+1}}}{2^{k+1}} = \frac{A + B}{2} \geq \sqrt{AB} \]

\[ \geq \sqrt{\sqrt[2^k]{a_1…a_{2^k}} \cdot \sqrt[2^k]{a_{2^k+1}…a_{2^{k+1}}}} = \sqrt[2^{k+1}]{a_1…a_{2^{k+1}}} \] ✓

Kết luận: BĐT AM-GM đúng với 2ⁿ số. ∎

Bài tập 9: Công thức đạo hàm

Đề bài: Chứng minh (xⁿ)’ = nxⁿ⁻¹ với mọi n ≥ 1

Lời giải:

Bước 1 (Cơ sở): Với n = 1: (x)’ = 1 = 1·x⁰ ✓

Bước 2 (Quy nạp): Giả sử (xᵏ)’ = kxᵏ⁻¹

Ta chứng minh (xᵏ⁺¹)’ = (k+1)xᵏ:

\[ (x^{k+1})’ = (x \cdot x^k)’ = x’ \cdot x^k + x \cdot (x^k)’ \]

\[ = 1 \cdot x^k + x \cdot kx^{k-1} = x^k + kx^k = (k+1)x^k \] ✓

Kết luận: (xⁿ)’ = nxⁿ⁻¹ với mọi n ≥ 1. ∎

Bài tập 10: Công thức nhị thức Newton

Đề bài: CM \( (a+b)^n = \sum_{k=0}^{n} C_n^k a^{n-k} b^k \)

Lời giải:

Bước 1 (Cơ sở): Với n = 0: (a+b)⁰ = 1 = C₀⁰a⁰b⁰ ✓

Bước 2 (Quy nạp): Giả sử công thức đúng với n:

\[ (a+b)^n = \sum_{k=0}^{n} C_n^k a^{n-k} b^k \]

Ta có:

\[ (a+b)^{n+1} = (a+b)(a+b)^n = (a+b)\sum_{k=0}^{n} C_n^k a^{n-k} b^k \]

\[ = a\sum_{k=0}^{n} C_n^k a^{n-k} b^k + b\sum_{k=0}^{n} C_n^k a^{n-k} b^k \]

\[ = \sum_{k=0}^{n} C_n^k a^{n+1-k} b^k + \sum_{k=0}^{n} C_n^k a^{n-k} b^{k+1} \]

Đổi chỉ số ở tổng thứ hai (j = k+1):

\[ = \sum_{k=0}^{n} C_n^k a^{n+1-k} b^k + \sum_{j=1}^{n+1} C_n^{j-1} a^{n+1-j} b^j \]

Tách và gộp các số hạng, sử dụng \( C_n^k + C_n^{k-1} = C_{n+1}^k \):

\[ = a^{n+1} + \sum_{k=1}^{n} (C_n^k + C_n^{k-1}) a^{n+1-k} b^k + b^{n+1} = \sum_{k=0}^{n+1} C_{n+1}^k a^{n+1-k} b^k \] ✓

Kết luận: Công thức nhị thức Newton đúng với mọi n ≥ 0. ∎

Bài tập 11: Bài toán đếm vùng

Đề bài: n đường thẳng trong mặt phẳng, không có 2 đường nào song song, không có 3 đường nào đồng quy, chia mặt phẳng thành \( \frac{n^2 + n + 2}{2} \) vùng.

Lời giải:

Bước 1 (Cơ sở): Với n = 1: 1 đường thẳng chia mp thành 2 vùng.

Công thức: (1 + 1 + 2)/2 = 2 ✓

Bước 2 (Quy nạp): Giả sử k đường thẳng chia mp thành (k² + k + 2)/2 vùng.

Thêm đường thẳng thứ (k+1): đường này cắt k đường cũ tại k điểm phân biệt, tạo thêm (k+1) vùng mới.

Số vùng mới:

\[ \frac{k^2 + k + 2}{2} + (k+1) = \frac{k^2 + k + 2 + 2k + 2}{2} = \frac{k^2 + 3k + 4}{2} \]

\[ = \frac{(k+1)^2 + (k+1) + 2}{2} \] ✓

Kết luận: Công thức đúng với mọi n ≥ 1. ∎

Bài tập 12: Chứng minh 5ⁿ − 4n − 1 ⋮ 16

Đề bài: Chứng minh 5ⁿ − 4n − 1 ⋮ 16 với mọi n ≥ 1

Lời giải:

Bước 1 (Cơ sở): Với n = 1: 5 − 4 − 1 = 0 ⋮ 16 ✓

Bước 2 (Quy nạp): Giả sử 5ᵏ − 4k − 1 ⋮ 16

Ta chứng minh 5ᵏ⁺¹ − 4(k+1) − 1 ⋮ 16:

\[ 5^{k+1} – 4(k+1) – 1 = 5 \cdot 5^k – 4k – 5 \]

\[ = 5(5^k – 4k – 1) + 5 \cdot 4k + 5 – 4k – 5 \]

\[ = 5(5^k – 4k – 1) + 20k – 4k = 5(5^k – 4k – 1) + 16k \]

Cả hai số hạng đều ⋮ 16, nên tổng ⋮ 16 ✓

Kết luận: 5ⁿ − 4n − 1 ⋮ 16 với mọi n ≥ 1. ∎

11. Kết luận

Qua bài viết trên, VJOL đã giúp bạn hiểu rõ về phương pháp quy nạp toán học cùng các ứng dụng quan trọng. Tóm tắt những điểm cần nhớ:

• Nguyên lý: Nếu P(n₀) đúng và P(k) ⟹ P(k+1) thì P(n) đúng ∀n ≥ n₀
• Bước 1 (Cơ sở): Kiểm tra P(n₀) đúng
• Bước 2 (Quy nạp): Giả sử P(k) đúng, chứng minh P(k+1) đúng
• Quy nạp mạnh: Giả sử P(n₀), …, P(k) đều đúng
• Chứng minh đẳng thức: Tách số hạng thứ (k+1) rồi áp dụng giả thiết
• Chứng minh BĐT: Biến đổi và ước lượng phù hợp
• Chứng minh chia hết: Biểu diễn f(k+1) = A·f(k) + B·m
• Lưu ý: Phải thực hiện cả hai bước, phải sử dụng giả thiết quy nạp
• Sai lầm thường gặp: Quên bước cơ sở, không dùng giả thiết, chọn sai n₀
• Ứng dụng: Đẳng thức, BĐT, chia hết, dãy số, tổ hợp, hình học

Hy vọng bài viết đã giúp bạn nắm vững phương pháp quy nạp toán học và có thể áp dụng vào giải toán hiệu quả!