Phương pháp quy nạp
Một phương pháp rất mạnh trong toán học dùng nghiên cứu và chứng minh các giả thiết
là nguyên lý quy nạp toán học. Bài viết này giúp bạn đọc làm quen với phương pháp mới
này và có thể áp dụng nó vào bài toán.
I.Nguyên lý quy nạp:
Gọi P(x) là một mệnh đề theo x.
Định lý: Cho p là số nguyên dương và dãy các mẹnh đề P(1), P(2), , P(n), nếu
a) P(1),P(2), ,P(p) là những mệnh đề đúng
b) Với mỗi số tự nhiên k>=p các mệnh đề P(k-p+1), P(k-p+2), ,P(k) đúng suy ra
P(k+1) cũng đúng
Thì mệnh đề P(n) đúng với mọi số nguyên dương n.
việc chứng minh định lý có lẽ là không cần thiết ta sẽ tập trung vào các bài tập về nguyên
lý này, nhưng mọi việc tự bản thân nó đã rõ ràng với những bạn đọc yêu toán. Chúng tôi
cũng không đi sâu vào việc giới thiệu các bước quy nạp bởi vì qua các bài toán bạn đọc
sẽ nắm được chúng.
II.Các ví dụ:
Bài toán 1: Tính tổng S
n
= 1+3+5+ +(2n-1) theo n
Giải: Ta tính thử vài giá trị đầu của tổng này:
S
1
=1;
S
2
=4;
S
3
=9;
S
4

+ +n
2

Giải: Ta tính thử vài giá trị đầu của S
n
:
N 1 2 3 4 5 6
P
n
1 5 14

30 55 91
Nhìn vào bảng trên ta khó có thể dự đoán công thức của P
n
nhưng ta có thể liên hệ giữa
S
n
và P
n
dựa vào bảng sau:
N 1 2 3 4 5 6
P
n
1 5 14

30 55 91
S
n
1 3 6 10 15 91
n

+
=
. Từ đó ta có thể suy ra công thức
(
)
(
)
121
6
n
nnn
P
++
=

Ta chứng minh bằng quy nạp cho công thức trên
Cơ sở quy nạp:n=1 đúng
giả sử mệnh đề đúng với n=k tức là
(1)(21)
6
k
kkk
P
++
=
. Ta chứng minh mệnh đề đúng
với n=k+1. Thật vậy:
()
(
)

3
Bài toán 4: Tính tổng S
n
= 1
4
+2
4
+ +n
4

(bạn đọc tự giải hai bài toán trên)
Sau đây tôi xin giới thiệu với các bạn một phương pháp quy nạp lùi do nhà toán học
Cauchy đưa ra thông qua việc chứng minh BĐT Cauchy
Bài toán 5:Với n số không âm a
1,
a
2,
a
3,
, a
n
ta luôn luôn có
1212

n
nn
naaaaaa
≤+++

(xem phần cm trong mục b

Bài toán 6:CMR với số nguyên dương n thì A
n
= 7
n
+ 3n -1 chia hết cho 9
Giải: với n=1 đúng
Giả sử mệnh đề đúng với n=k tức là A
k
chia hết cho 9
Ta có : A
k+1
= 7
k+1
+ 3(k+1) -1 =7.7
k
+ 3k +2 = 7( 7
k
+ 3k -1) – 9(2k-1) = 7A
k
– 9(2k-1)
nên A
k+1
chia hết cho 9.
Vậy mệnh đề đúng với mọi n

Bài toán 7: Hãy tìm tất cả các đa thức P(x) thỏa mãn điều kiện P(x
2
-2) = (P(x))
2
– 2

thõa mãn đề bài. Từ đó ta có quan hệ giữa các đa thức trên:
P
3
(x)=xP
2
(x)-P
1
(x);
P
4
(x)=xP
3
(x)-P
2
(x);
P
5
(x)=xP
4
(x)-P
3
(x);
điều này gợi ý cho ta một giả thiết sau đây:
“mọi đa thức được xác định bằng công thức truy hồi P
n+2
(x)=xP
n+1
(x)-P
n
(x); P

2,
H
4

là G
3
, H
1,
H
3,
H
4
là G
2
, H
2,
H
3,
H
4
là G
1.
Gọi giao của 4 hình là H
+ Nếu G
4
nằm trong tam giác G
1
G
2
G

2
, ,H
n-2
,H
0
. Dựa vào giả thiết và trường hợp n=4 ta sẽ có mọi cặp ba hình
trong số n-1 hình này cắt nhau nên theo giả thiết quy nạp => đpcm

Bài toán 9: CM: với mọi n thì
1
13
n
n

+<



Giải: Vì vế phải của BĐT là một đại lượng biến thiên (bạn đọc có thể chứng minh nó
tăng) nhưng vế trái lại là một đại lượng không đổi nên ta không thể ch ứng minh bằng
quy nạp ngay được. Ta sẽ chứng minh :
()
2
2
1
11 1
k
nn
kn
nkk

chữ số 1 thì chia hết cho 3
n3)CMR: từ 2
n+1
-1 số nguyên bất kỳ có thể tìm được 2
n
số mà tổng của chúng chia hết cho
2
n

4)CMR: nếu
1
x
x
+
là số nguyên thì
1
n
n
x
x
+
cũng là số nguyên với mọi n

5)Gọi a,b là hai nghiệm của phương trình x
2
-14x+1=0. CMR: S
n

xy
xy
+

là số nguyên

7)CMR: với mọi n ta luôn có
(
)
23
n

+


là số lẻ

8)Cho hai số dương a,b sao cho a+b=3. CMR
3
2
2
n
nn
ab

+≥



9)CM bđt Becnuli:

*) Đây là một phương pháp rất hay và rất quan trọng trong toán học từ xưa đến nay.
*) Ý tưởng của phương pháp này là giả sử điều ngược lại của bài toán rồi từ điều giả sử
này ta tìm ra sự mâu thuẫn .Do đó bài toán được chứng minh đúng.
*) Ứng dụng của phương pháp này rộng trên mọi lĩnh vực của toán từ đại số, số học, hình
học cho đến các lĩnh vực cao hơn.
*) Chúng ta sẽ đi vào các ví dụ để hiểu rõ phương pháp này.
Ví dụ 1: Cho a,b
∈Ν
và(a,b)=1.CMR: (a+b,ab)=1.
Giải: Giả sử (a+b,ab)= d (d
≠
1).
Gọi p là ước nguyên tố lớn nhất của d
1
p
⇒≠
do d
1
≠
.

abp
abp
+

⇒






(
n
∈Ζ
)
Giả sử
2
35121
nn++

(1)
2
2
2
43.42011
(23)1111
(23)121
nn
n
n
⇒++
⇒++
⇒+




Thay vào (1) ta có 11

121 (vô lí)


⇒⇒+++<

<


<

(vô lí)
⇒
đpcm
Ví dụ 4:CMR không tồn tại số nguyên tố lớn nhất.
Giải: Giả sử tồn tại
n
p
là số nguyên tố lớn nhất.Gọi các số nguyên tố nhỏ hơn nó
là
121
, ,
nn
ppp
−−
(với
1
p
=2). Đặt A=
123

n
pppp

⇒
abcd chẵn (vô lí)
⇒
đpcm
Ví dụ 6:Cho bảng 6
×
6 được lấp đầy bằng quân đôminô 2
1
×
.CMR ta có thể cắt bảng này
ra thành 2 hình chữ nhật sao cho không làm hỏng quân đôminô.
Giải:
Gọi bảng (I) là bảng được tô đen, ô 1 là một quân đôminô
Giả sử 1:Các ô trong bảng bị lấp đầy và không thoả bài toán.
⇒
mỗi đường ketrong bảng(khác biên) đều chia đôi ít nhất 1
quân đôminô
Giả sử 2: Có 1 đuờng kẻ chia đôi 1 con đôminô.
⇒
Bảng (I) được lấp kín bằng quân
21
×
.
⇒
Số ô trong bảng (I) là chẵn (vô lí)
⇒
mỗi đường kẻ phải chia ít nhất 2 ô.
⇒
Bảng phải có ít nhất 5.2.2=20 ô
21

4)CMR nếu
0
0
0
abc
abbcca
abc
++>


++>


>

thì a,b,c>0.
5) Cho 2005 điểm trên mặt phẳng sao cho khoảng cách giữa 2 điểm trong 3 điểm bất kì
luôn nhỏ hơn 2,09 cm.CMR ta có thể vẽ 1 đường tròn đường kính 4,18 cm chứa 1003
điểm.

1

6) Chứng minh rằng không thể lấp đầy bảng 8x8 bị khoét một ô như hình vẽ bằng các
quân 3x1