.: CHUYEÂN ÑEÀ OÂN THI MOÂN TOAÙN VAØO LÔÙP 10 THPT :.
Biên soạn: Trần Trung Chính 88
CHUÛ ÑEÀ 5
PHÖÔNG PHAÙP CHÖÙNG MINH "QUY NAÏP TOAÙN HOÏC"
1. Kiến thức cơ bản:
Quy nạp không hoàn toàn:
Là sự suy luận đi từ những sự kiện riêng lẻ đến một kết luận tổng quát. Phƣơng pháp này không
phải là phép chứng minh nhƣng là phƣơng pháp tìm tòi quan trọng, nó giúp ta dự đoán những giả
thiết có thể đúng hoặc sai.
Quy nạp hoàn toàn:
Là phép suy luận sau khi đã xem xét tất cả mọi trƣờng hợp có thể xảy ra mới rút ra kết luận tổng
quát.
Bài toán:
Chứng minh P(n) đúng với mọi n nguyên và n a, a nguyên.
Phương pháp 1:
Bƣớc 1: Thử với n = a
Thay n = a P(a) đúng.
Do đó P(n) đúng khi n = a.
Bƣớc 2: Lập giả thiết quy nạp.
Giả sử P(n) đúng với n = k, k Z và k a nghĩa là P(k) đúng.
Bƣớc 3: Chứng minh
Ta chứng minh rằng P(n) khi n = k + 1 nghĩa là ta chứng minh rằng:
P(k + 1) đúng.
Bƣớc 4: Kết luận.
Vậy P(n) đúng với mọi n N và n a, a Z.
Phương pháp 2:
Khi n = a P(a) đúng.
Khi n = a + 1 P(a + 1) đúng.
Giả sử P(k - 1) đúng và P(k) đúng, với k kZ và k a + 1
Chứng minh P(k + 1) đúng.
Vậy P(n) đúng với mọi n N và n a, a Z.
Phương pháp 3:
Khi n = a P(a) đúng.
Giả sử P(a), P(a + 1), P(a + 2), ..., P(k - 1), P(k) đúng.
Chứng minh P(k + 1) đúng.
Vậy P(n) đúng với mọi n N và n a, a Z.
Ví dụ 1: Sử dụng phƣơng pháp chứng minh quy nạp chứng minh rằng:
n(n 1)
1 2 3 ... n 2
Ví dụ 2: Tính tổng :
n
S =1+3+5+...+ (2n -1)
Các tổng cơ bản cần nhớ:
a)
n(n 1)
1 2 3 ... n 2
b.
2 2 2 2 n(n 1)(2n 1)
1 2 3 ... n 6

c.
3
3 3 3 n(n 1)
1 2 ... n 2



2. Bài tập áp dụng:
Bài tập 1: Tính tổng: Sn = 13 + 23 + 33 + ... + n3
Giải
.: CHUYEÂN ÑEÀ OÂN THI MOÂN TOAÙN VAØO LÔÙP 10 THPT :.
Biên soạn: Trần Trung Chính 89
Ta có:
S1 = 13 = 1 = 12
S2 = 13 + 23 = 9 = (1 + 2)2
S3 = 13 + 23 + 33 = (1 + 2 + 3)2
Giả sử:
Sk = 13 + 23 + 33 + ... + k3 = (1 + 2 + 3 + ... + k)2
Ta có:
1 + 2 + 3 + ... + k =
k k 1
2
2
k
k k 1
1S 2





(1')
Cộng (k + 1)3 vào hai vế của (1'), ta đƣợc:
2
33
k
k k 1
S k 1 k 1
2




2
22
k1
2
k1
k 1 k 2
k1
S k 4k 4
22
S 1 2 3 ... k 1




 
 


Vậy Sn = 13 + 23 + 33 + ... + n3 = (1 + 2 + 3 + ... + n)2
2
2
k k +1
=4
Bài tập 2: Cho
là một số nguyên. Chứng minh rằng số
2005
2005
1
b = x + x
là một số nguyên.
Giải
Ta chứng minh rằng nếu:
*
1
a x , x R
x
là một số nguyên thì
n
nn
1
Sxx

cũng là một số nguyên với mọi n Z.
Nhận xét: Nếu n nguyên âm, ta đặt:
n = -m, với m Z+
mm
n m n
mm
11
S x x S S
xx
Do đó ta chỉ cần chứng minh quy nạp.
Khi n = 0 thì S0 = 2 Z
Khi n = 1
Ta có:
11
S x Z
x
Giả sử Sn nguyên với n = k, k N và k 1.
S0, S1, S2, ..., Sk nguyên.
Ta chứng minh Sk+1 nguyên
Ta có:
www.VNMATH.com
.: CHUYEÂN ÑEÀ OÂN THI MOÂN TOAÙN VAØO LÔÙP 10 THPT :.
Biên soạn: Trần Trung Chính 90
k k 1 k 1
k k 1 k 1
k 1 k 1 k 1
k 1 k 1 k 1
1 1 1 1
x x x x
x
x x x
S .S S S
S S S S




Suy ra Sk+1 nguyên.
Sn nguyên với mọi n N
Do đó:
2005
2005 2005
1
Sxx

là một số nguyên.
Bài tập 3: Chứng minh rằng tồn tại vô hạn số tự nhiên n khác 0 sao cho:
2n - 1
n (*)
Tìm tất cả các số nguyên tố n thỏa mãn (*).
Giải
Ta chứng minh rằng với n = 3q, q N, thì n chia hết số 2n + 1
q
3q
2 1 3
(1)
Khi q = 0, ta có:
21 + 1
1, đúng
Giả sử (1) đúng với q = k, k N.
k
k
3k
3 k *
2 1 3
2 1 A.3 , A N 2
Ta chứng minh rằng (1) đúng với q = k + 1 tức là chứng minh
k1
3 k 1
2 1 3
(3)
Ta có:
k 1 k 33
3 3 3 k
3 3k 2 2k 3k
2 2k 1 k k 1
2 1 2 1 A .3 1
A .3 3A .3 3.A.3
A A .3 A.3 1 3



Do đó, ta có:
k1
3 k 1
2 1 3
(3) đã đƣợc chứng minh:
Vậy có vô số số tự nhiên n sao cho: 2n - 1
n (*)
Với n = 3q, q N, n nguyên tố khi q = 1 n = 3.
Bài tập 4: Cho x và y là các số thực khác 0 sao cho các số:
11
a = x + ; b = y +
yx
đều là số nguyên
a) Chứng minh rằng số
22
22
1
c = x y + xy
cũng là một số nguyên.
b) Tìm mọi n nguyên dƣơng sao cho số:
nn
nn
1
d = x y + xy
cũng là số nguyên.
Giải
a) Ta có:
11
a = x + ; b = y +
yx
, với x, y R*
.: CHUYEÂN ÑEÀ OÂN THI MOÂN TOAÙN VAØO LÔÙP 10 THPT :.
Biên soạn: Trần Trung Chính 91
1 1 1
a.b x y xy 2
y x xy
11
xy ab 2 xy Z
xy xy
Ta có:
2
22
22
11
c x y xy 2 c Z
xy
xy



Vậy nếu
11
a = x + ; b = y +
yx
nguyên thì các số
1
xy xy
và
22
22
1
xy xy
đều là số nguyên.
b) .Đặt:
nn
nn nn
1
t d t x y , n
xy
Z
Khi n = 1, n = 2 thì các số t1, t2 nguyên.
Giả sử tn nguyên cho đến khi n = k.
t1, t2, ..., tk-1, tk nguyên.
Ta chứng minh rằng:
k 1 k 1
k1 k 1 k 1
1
t x y , k Z
xy


cũng là số nguyên.
Ta có: tk+1 = tk.tk-1 tk+1 Z.
Vậy nếu
11
a = x + ; b = y +
yx
là các số nguyên thì số
nn
nn
1
d x y xy

nguyên, n Z.
Bài tập 5: Xem dãy số:
A1 = 1
A2 = 3 + 5
A3 = 7 + 9 + 11
A4 = 13 + 15 + 17 + 19
.....................................
Chứng minh rằng mỗi số hạng của dãy là lập phƣơng của một số tự nhiên.
Giải
Số hạng tổng quát của dãy số đã cho có dạng: An = ak+1 + ak+2 + ... + ak+n
Với am = 2m - 1 và k là số các số lẻ có trong các số hạng của dãy từ 1 đến n - 1.
Ta có: k = 1 + 2 + 3 + ... + (n - 1) =
n 1 n
2
An = (2k + 1) + (2k + 3) + ... + (2k + 2n - 1)
= (2k + n)n
= [(n - 1)n + n]n = n3
Do đó, ta có:
A1 = 1 = 13
A2 = 3 + 5 = 23
A3 = 7 + 9 + 11 = 33
A4 = 13 + 15 + 17 + 19 = 43
....................................
An = n3.
Bài tập 6: Chứng minh rằng số nguyên tố thứ n thì nhỏ hơn
n
2
2
.
Giải
Gọi Pn là số nguyên tố thứ n.
Ta chứng minh rằng:
www.VNMATH.com
.: CHUYEÂN ÑEÀ OÂN THI MOÂN TOAÙN VAØO LÔÙP 10 THPT :.
Biên soạn: Trần Trung Chính 92
Pn <
n
2
2
(1)
Khi n = 1, ta có:
P1 = 2 <
1
2
2
(1) đúng khi n = 1.
Giả sử (1) đúng khi n = 1, 2, 3, ..., k nghĩa là ta có:
P1 <
1
2
2
P2 <
2
2
2
P3 <
3
2
2
(2)
............
Pk <
k
2
2
Ta chứng minh rằng:
Pk+1 <
k1
2
2
(3)
Xem số:
A = P1P2 ... Pk + 1 A > Pk
Gọi d là một ƣớc số nguyên tố của A d A
Nếu d Pk thì d chia hết tích P1P2P3 ... Pk+1 và do đó d chia hết 1, vô lí
d > Pk d Pk+1
Ta có:
Pk+1 d A = P1P2P3... Pk + 1
Pk+1
1
2
2
.
2
2
2
.
3
2
2
...
k
2
2
+ 1
Pk+1
1 2 3 k
2 2 2 ... 2
2
Pk+1
k 1 k 1
22
2 2 2


(3) đã đƣợc chứng minh.
Vậy Pn <
n
2
2
.
Bài tập 7: Chứng minh rằng số đƣợc thành lập bởi 3n chữ số giống nhau thì chia hết cho 3n, trong đó
n là số tự nhiên.
Giải
Ta dùng phƣơng pháp quy nạp:
Khi n = 1. ta có số
1
aaa 3 3
Giả sử bài toán đúng khi n = k, k N và k 1.
k
k
A aaa...aaa 3
k
3 ch÷ sè a
Ta chứng minh rằng bài toán đúng khi n = k + 1 nghĩa là ta chứng minh:
k1
k1
A aaa...aaa 3
k+1
3 ch÷ sè a
Ta có thể viết:
kk
k1
1
A aaa...aaa aaa...aaa
aaa...aaaaaa...aaaaaa...aaa
aaa...aaa 100 ...000

kk
kkk
kk
3 .3 ch÷ sè a 3 +3 +3 ch÷ sè a
3 ch÷ sè a 3 ch÷ sè a 3 ch÷ sè a
3 ch÷ sè a 3 ch÷
1
k k 1
k
11
100 ...0001
=A .100 ...000 .100 ...000 3 .3 3

k
kk
sè 0 3 ch÷ sè 0
3 ch÷ sè 0 3 ch÷ sè 0