Bài 30. Phương pháp quy nạp toán học

Chương 2. Phương pháp quy nạp toán học. Nhị thức Newton

1. Phương pháp quy nạp toán học

Vì sao cần chứng minh Các đẳng thức

1 = 1^{2}; 1 + 3 = 2^{2}; 1 + 3 + 5 = 3^{2}; 1 + 3 + 5 + 7 = 4^{2}; \dots

gợi ý công thức

1 + 3 + 5 + \dots + (2 n - 1) = n^{2}

(HĐ1). Nhưng đa thức

p (n) = n^{2} - n + 41

cho số nguyên tố với

n = 1, 2, \dots, 40

mà sai khi

n = 41 (p (41) = 4 1^{2}

là hợp số). Vậy để khẳng định một mệnh đề toán học phụ thuộc số tự nhiên

n

là đúng, phải chứng minh dù đã kiểm nghiệm với bao nhiêu giá trị

n

đi nữa.

Phương pháp quy nạp toán học Để chứng minh một mệnh đề phụ thuộc

n \in N^{*}

đúng với mọi

n \in N^{*}

Bước 1. Kiểm tra mệnh đề đúng với $n = 1$ .
Bước 2. Giả thiết mệnh đề đúng với $n = k \geq 1$ (gọi là giả thiết quy nạp), chứng minh mệnh đề đúng với $n = k + 1$ . Kết luận.

Hình ảnh minh hoạ: hiệu ứng domino (quân đầu tiên đổ; mỗi quân đổ kéo theo quân kế tiếp đổ thì tất cả đều đổ).
Chú ý: nếu cần chứng minh đúng với mọi số tự nhiên

n \geq p

thì Bước 1 kiểm tra với

n = p

; Bước 2 giả thiết đúng với

n = k \geq p

rồi chứng minh với

n = k + 1

Ví dụ 1 Chứng minh

1 + 3 + 5 + \dots + (2 n - 1) = n^{2}

với

n \geq 1

. Bước

1 : n = 1

có

1 = 1^{2}

. Bước 2: giả sử

1 + 3 + \dots + (2 k - 1) = k^{2}

. Khi đó

1 + 3 + \dots + (2 k - 1) + [2 (k + 1) - 1] = k^{2} + (2 k + 1) = (k + 1)^{2}

. Vậy đúng với mọi

n \geq 1

.
Luyện tập 1:

1 + 2 + 3 + \dots + n = \frac{n ( n + 1 )}{2}

Ví dụ 2 Với

n \geq 2 : (1 - \frac{1}{2 ^{2}}) (1 - \frac{1}{3 ^{2}}) \dots (1 - \frac{1}{n ^{2}}) = \frac{n + 1}{2 n}

. Bước

1 : n = 2 : 1 - \frac{1}{4} = \frac{3}{4} = \frac{2 + 1}{2 \cdot 2}

. Bước 2: giả sử đúng với

n = k \geq 2

; nhân thêm

(1 - \frac{1}{( k + 1 ) ^{2}}) = \frac{( k + 1 ) ^{2} - 1}{( k + 1 ) ^{2}} = \frac{k ( k + 2 )}{( k + 1 ) ^{2}} : \frac{k + 1}{2 k} \cdot \frac{k ( k + 2 )}{( k + 1 ) ^{2}} = \frac{k + 2}{2 ( k + 1 )}

. Vậy đúng với mọi

n \geq 2

.
Luyện tập 2: với

n \geq 2, a^{n} - b^{n} = (a - b) (a^{n - 1} + a^{n - 2} b + \dots + a b^{n - 2} + b^{n - 1})

(gợi ý của sách:

a^{k + 1} - b^{k + 1} = a^{k} (a - b) + b (a^{k} - b^{k})

2. Một số ứng dụng khác của phương pháp quy nạp

Ví dụ 3 – chia hết Chứng minh

n (n + 1) (n + 2)

chia hết cho 3 với mọi số tự nhiên

n . n = 0 : 0

chia hết cho 3. Giả sử

k (k + 1) (k + 2) = 3 m

; khi đó

(k + 1) (k + 2) (k + 3) = k (k + 1) (k + 2) + 3 (k + 1) (k + 2) = 3 [m + (k + 1) (k + 2)]

, chia hết cho 3.
Nhận xét: trong hai số tự nhiên liên tiếp luôn có một số chẵn, nên tích của ba số tự nhiên liên tiếp luôn chia hết cho 6.

Ví dụ 4 – bất đẳng thức Chứng minh

2^{n} > 2 n + 1

với

n \geq 3. n = 3 : 2^{3} = 8 > 7

. Giả sử

2^{k} > 2 k + 1 (k \geq 3)

; khi đó

2^{k + 1} = 2 \cdot 2^{k} > 2 (2 k + 1) = 4 k + 2 = 2 k + 2 (k + 1) > 2 k + 3

k \geq 3

. Vậy bất đẳng thức đúng với mọi

n \geq 3

Ví dụ 5 – hình học Tổng các góc trong của đa giác

n

cạnh

(n \geq 3)

là

(n - 2) \cdot 180°. n = 3

: tam giác có tổng 180°. Giả sử đúng với

n = k

; với đa giác

k + 1

cạnh

A_{1} A_{2} \dots A_{k} A_{k + 1}

, nối

A_{1}

với

A_{k}

được đa giác

k

cạnh và tam giác

A_{k + 1} A_{k} A_{1}

, nên tổng góc là

(k - 2) \cdot 180° + 180° = [(k + 1) - 2] \cdot 180°

Vận dụng – công thức lãi kép; bài tập có “lập luận sai”

Lãi kép theo định kì: gửi số tiền $A$ với lãi suất $r$ mỗi kì, không rút lãi thì tiền lãi được tính vào vốn kì kế tiếp: $T_{1} = A (1 + r), T_{2} = A (1 + r)^{2}, T_{3} = A (1 + r)^{3}$ ; dự đoán $T_{n} = A (1 + r)^{n}$ rồi chứng minh bằng quy nạp. (Sách chỉ nêu đề; ở đây là kết quả do người biên soạn tính.)
Bài tập 2.8 của sách đưa ra một “chứng minh” bằng quy nạp rằng mọi con mèo đều cùng màu và hỏi lập luận sai ở chỗ nào — để cho thấy phải kiểm tra đủ cả hai bước.

Em có biết: các nhà toán học Hy Lạp đã biết tới nguyên lí quy nạp nhưng chưa rõ ràng; lập luận quy nạp xuất hiện tường minh lần đầu trong Arithmeticorum Libri Duo (1575) của Francesco Maurolico; John Wallis (1616–1703) được coi là người đầu tiên dùng thuật ngữ quy nạp.

Bài 30. Phương pháp quy nạp toán học

1. Phương pháp quy nạp toán học

2. Một số ứng dụng khác của phương pháp quy nạp

Sơ đồ tư duy