Phương pháp 9: PHƯƠNG PHÁP PHẢN CHỨNG

Phương pháp 9: PHƯƠNG PHÁP PHẢN CHỨNG

Để CM A(n)  p (hoặc A(n)  p )

+ Giả sử: A(n)  p (hoặc A(n)  p )

+ CM trên giả sử là sai

+ Kết luận: A(n)  p (hoặc A(n)  p )

Ví dụ 1: CMR n2 + 3n + 5  121 với  n  N

Giải: Giả sử tồn tại n  N sao cho n2 + 3n + 5  121

 4n2 + 12n + 20  121 (vì (n, 121) = 1)

 (2n + 3)2 + 11  121 (1)

 (2n + 3)2  11

Vì 11 là số nguyên tố  2n + 3  11

 (2n + 3)2  121 (2)

Từ (1) và (2)  11  121 vô lý

Vậy n2 + 3n + 5  121

Ví dụ 2: CMR n2 - 1  n với  n  N*

Giải: Xét tập hợp số tự nhiên N*

Giả sử  n  1, n  N* sao cho n2 - 1  n

Gọi d là ước số chung nhỏ nhất khác 1 của n  d  (p) theo định lý Format

ta có

2d-1  1 (mod d)  m < d

ta chứng minh m\n

Giả sử n = mq + r (0  r < m)

Theo giả sử n2 - 1  n  nmq+r - 1  n

 2r(nmq - 1) + (2r - 1)  n  2r - 1  d vì r < m mà m  N, m nhỏ nhất khác

1 có tính chất (1)

 r = 0  m\n mà m < d cũng có tính chất (1) nên điều giả sử là sai.

Vậy n2 - 1  n với  n  N*

BÀI TẬP TƯƠNG TỰ

Bài 1: Có tồn tại n  N sao cho n2 + n + 2  49 không?

Bài 2: CMR: n2 + n + 1  9 với  n  N*

Bài 3: CMR: 4n2 - 4n + 18  289 với  n  N

HƯỚNG DẪN - ĐÁP SỐ

Bài 1: Giả sử tồn tại n  N để n2 + n + 2  49

 4n2 + 4n + 8  49

 (2n + 1)2 + 7  49 (1)  (2n + 1)2  7

Vì 7 là số nguyên tố  2n + 1  7  (2n + 1)2  49 (2)

Từ (1); (2)  7  49 vô lý.

Bài 2: Giả sử tồn tại n2 + n + 1  9 với  n

 (n + 2)(n - 1) + 3  3 (1)

n



 (n + 2)(n - 1)  9 (2)

n



 32  31

 vì 3 là số nguyên tố   

Từ (1) và (2)  3  9 vô lý

Bài 3: Giả sử  n  N để 4n2 - 4n + 18  289

 (2n - 1)2 + 17  172

 (2n - 1)  17

17 là số nguyên tố  (2n - 1)  17  (2n - 1)2  289

 17  289 vô lý.

BÀI TẬP VÀ PHƯƠNG PHÁP

Cỏch 1: Để chứng minh A(n) chia hết cho k, có thể xét mọi trường hợp số

dư khi chia n cho k.

Vớ dụ: Chứng minh rằng:

a) Tớch của hai số nguyờn liờn tiếp chia hết cho 2.

b) Tớch của ba số nguyờn liờn tiếp chia hết cho 3.

Giải: a) Viết tớch của hai số nguyờn liờn tiếp dưới dạng A(n) = n(n + 1).

Có hai trường hợp xảy ra :

* n  2 => n(n + 1) 2

* n khụng chia hết cho 2 (n lẻ) => (n + 1)  2 => n(n +1)  2

b) Xét mọi trường hợp: n chia hết cho 3; n=3q+1; n = 3q+2

+ Nếu n chia hết cho 3, hiển nhiên A(n) chia hết cho 3

+ Nếu n = 3q+1 => n+2 = 3q+3 chia hết cho 3

+ Nếu n= 3q+2 => n+1 = 3q+2+1 = 3q+3 chia hết cho 3

Trong mọi trường hợp A(n) luôn chứa một thừa số chia hết cho 3.

Vậy A(n) chia hết cho 3 (đpcm)

Cỏch 2: Để chứng minh A(n) chia hết cho k, có thể phân tích k ra thừa

số: k = pq .

+ Nếu (p, q) = 1, ta chứng minh A(n)  p và A(n)  q.

+ Nếu (p, q)  1, ta phõn tớch A(n) = B(n) .C(n) rồi chứng

minh:B(n)  p và C(n)  q .

Vớ dụ 1: a) Chứng minh: A(n) = n(n +1)(n + 2) 6.

b) Chứng minh: tớch của hai số chẵn liờn tiếp chia hết cho 8.

Giải: a) Ta cú 6 = 2.3; (2,3) = 1 . Theo chứng minh trên đó cú A(n) chia

hết cho 2 và 3. Do đó A(n) chia hết cho 6.

b) Ta viết A(n) = 2n(2n + 2) = 2n. 2(n +1) = 4n(n + 1).

8 = 4 . 2.

Vỡ 4 4 và n(n +1) 2 nờn A(n)  8

Vớ dụ 2 : Chứng minh rằng n5 - n chia hết cho 10, với mọi số nguyên dương

n.

(Trích đề thi HSG lớp 9 cấp tỉnh năm học 2005 - 2006)

Giải: A(n) = n5 - n = n(n4 - 1) = n(n2 - 1)(n2 + 1) = n(n - 1)(n + 1)(n2 +1)  2

n = 5k + 1 => (n - 1)  5

n = 5k + 4 => (n + 1)  5.

n = 5k + 2 => n2 + 1 = (5k + 2)2 + 1 = (25k2 + 20k + 4 + 1) 5

n = 5k + 3 => n2 + 1 = (5k + 3)2 + 1 = (25k2 + 30k + 9 + 1) 5

Vậy : A(n) chia hết cho 2 và 5 nờn phải chia hết cho 10.

Cỏch 3: Để chứng minh A(n) chia hết cho k, có thể biến đổi A(n) thành

tổng (hiệu) của nhiều hạng tử, trong đó mỗi hạng tử đều chia hết cho k.

(Đó học trong tớnh chất chia hết của một tổng ở lớp 6)

(Liờn hệ: A(n) khụng chia hết cho k ...)

Vớ dụ 1: Chứng minh n3 - 13n (n > 1) chia hết cho 6. (Trích đề thi HSG cấp II toàn quốc năm 1970). Giải: n3 - 13n = n3 - n - 12n = n(n2 - 1) - 12n = (n - 1)n(n + 1) - 12n

(n - 1)n(n + 1) là tớch của 3 số tự nhiờn liờn tiếp nờn chia hết cho 6 ; 12n 6

. Do đó A(n)  6

Vớ dụ 2: Chứng minh n2 + 4n + 5 khụng chia hết cho 8 , với mọi số n lẻ.

Giải: Với n = 2k +1 ta cú:

A(n) = n2 + 4n + 5 = (2k + 1)2 + 4(2k + 1) + 5 = 4k2 + 4k + 1 + 8k + 4 + 5

= 4k(k + 1) + 8(k + 1) + 2.

A(n) bằng tổng của ba hạng tử, trong đó hai hạng tử đầu đều chia hết cho 8 ,

duy chỉ có hạng tử 2 không chia hết cho 8. Vậy A(n) không chia hết cho 8.

Cỏch 4: Phõn tớch A(n) thành nhõn tử. Nếu cú một nhõn tử chia hết cho

k thỡ A(n) chia hết cho k.

Hệ quả: Nếu A(n) = B(n).C(n) mà B(n)và C(n) đều không chia hết cho k

thỡ A(n) khụng chia hết cho k

A(n) = k . B(n).

Trường hợp này thường sử dụng các kết quả:

* (an - bn ) chia hết cho (a - b) với (a  b)

* (an - bn ) chia hết cho (a - b) với (a   b; n chẵn)

(an - bn ) chia hết cho (a - b) với (a  - b; n lẻ)

Vớ dụ 1: Chứng minh : 2 + 22 + 23 + ... + 260 chia hết cho 15.

Giải: Ta cú:

2 + 22 +23 + ... + 260 = (2 + 22 + ... + 24) + (25+ ... + 28) + ... + (257 +...+ 260)

= 2(1 + 2 + 4 + 8) + 25(1 + 2 + 4 + 8) + ... + 257(1 + 2 + 4 + 8)

= 15.(2 + 25 + ... + 257)  15.

Vớ dụ 2: Chứng minh rằng: 27 + 37 + 57 chia hết cho 5

Giải: Vì 7 là số lẻ nên (27 + 37) chia hết cho (2 + 3)

hay 27 + 37 chia hết cho 5 => 27 + 37 + 57 chia hết cho 5 (đpcm)

mà 57 chia hết cho 5

Cỏch 5: Dựng nguyờn tắc Dirichlet:

Nguyên tắc Dirichlet phát biểu dưới dạng hỡnh ảnh như sau:

Nếu nhốt k chỳ thỏ vào m chuồng mà k> m thỡ phải nhốt ớt nhất hai chỳ

thỏ vào chung một chuồng.

Vớ dụ: Chứng minh rằng trong m + 1 số nguyờn bất kỡ thế nào cũng cú hai

số cú hiệu chia hết cho m.

Giải: Chia một số nguyờn bất kỡ cho m ta được số dư là một trong m số 0; 1

; 2; 3; ...; m - 1. Theo nguyờn tắc Dirichlet, chia m + 1số cho m thỡ phải cú

ớt nhất hai số cú cựng số dư . Do đó hiệu của hai số này sẽ chia hết cho m.

Cỏch 6: Dùng phương pháp qui nạp toán học: Để chứng minh A(n)  k ta

làm theo trỡnh tự sau:

Thử với n = 1 hoặc 2(Tức số n nhỏ nhất chọn ra). Nếu sai => Dừng.Nếu

đúng A(1)k.Tiếp tục:

Giả sử A(k) k.

Chứng tỏ A(k + 1) k. Nếu đúng => Kết luận : A(n) k

Vớ dụ: Chứng minh : 16n - 15n - 1 chia hết cho 225.

Giải: Đặt A(n) = 16n - 15n -1 , ta cú : A(1) = 16 - 15 - 1 = 0 225 => A(1)

đúng.

Giả sử A(k) đúng : A(k) = 16k - 15k -1  225.

Ta chứng minh A(k + 1) đúng, tức là c/m: 16k + 1 - 15(k + 1) - 1225.

Thật vậy, 16k+1 - 15(k + 1) - 1 = 16. 16k - 15k - 15 - 1

= (15 + 1) 16k - 15k - 15 - 1

= 15.16k + 16k - 15k -15 - 1

= (16k - 15k - 1) + 15(16k - 1)

= (16k - 15k - 1) + 15(16 - 1) (16k-1 + ... +1)

= (16k - 15k - 1) + 225(16k-1+ ... + 1) 225

Khi gặp những bài toỏn chứng minh với là số tự nhiên, ta vẫn

thường dùng phương pháp quy nạp. Cụ thể lược đồ của cách giải này là:



 Giả sử

, ta chứng minh . Nhưng để ý rằng nếu thỡ

Vỡ vậy cú thể xem đây là một biến dạng của phương pháp quy nạp, để

chứng minh ta qua hai bước:





Áp dụng phương pháp này, ta có thể giải được một loạt cỏc bài toỏn chia

hết khỏ cồng kềnh.

Vớ dụ 1: Chứng minh cú chia hết cho

125.

Giải: Cú .

Xột nhưng

nờn (đpcm)

Vớ dụ 2: Chứng minh cú chia hết cho

64.

Giải: Cú

Xột

Lại áp dụng phương pháp trên với

Cỏch 7: Phương pháp phản chứng:

Để chứng minh A(n)  k ta chứng minh A(n) khụng chia hết cho k là sai.

A => B  B => A

Vớ dụ: Chứng minh nếu a2 + b2 3 thỡ a và b đều chia hết cho 3.

Giải: Giả sử a và b khụng chia hết cho 3 => a = 3k  1 ; b = 3h  1

a2 + b2 = (3k  1)2 + (3h  1)2 = 9k2  6k + 1 + 9h2  6h + 1

= 3(3k2 + 3h2  2k  2h) + 2 khụng chia hết cho

3 mõu thuẫn với GT

Tương tự cho trường hợp chỉ có một trong hai số chia hết cho 3.

Do đó a và b phải chia hết cho 3.