Giáo trình Toán rời rạc - Bài 3: Quy nạp - Trần Vĩnh Đức
Quy nạp
Trần Vĩnh Đức
HUST
Ngày 24 tháng 7 năm 2018
1 / 37
Tài liệu tham khảo
▶
▶
Eric Lehman, F Thomson Leighton & Albert R Meyer,
Kenneth H. Rosen, Toán học rời rạc ứng dụng trong tin học
(Bản dịch Tiếng Việt)
2 / 37
Nội dung
Nguyên lý quy nạp
Quy nạp mạnh
Nguyên lý quy nạp
7 888321
80
79
78
77
76
75
74
73
72
71
70
6
68
67
66
6
64
63
62
6
6
5
8
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
3
3
3
35
34
33
32
31
30
Xét vị từ P(n) trên N. Nếu
29
28
27
26
25
24
23
22
21
20
1
18
1
16
1
1
1
12
11
10
▶
▶
P(0) đúng, và
với mọi n ∈ N, (P(n) ⇒ P(n + 1))
cũng đúng,
thì P(n) đúng với mọi n ∈ N.
9
8
7
6
5
4
3
2
1
4 / 37
Ví dụ
Định lý
Với mọi n ∈ N,
n(n + 1)
1 + 2 + · · · + n =
2
Đặt P(n) là mệnh đề
n
∑
n(n + 1)
i =
2
i=1
5 / 37
Chứng minh.
▶
▶
Bước cơ sở: P(0) đúng.
Bước quy nạp: Ta sẽ chứng minh: với mọi n ≥ 0, mệnh đề
P(n) ⇒ P(n + 1)
đúng.
Thật vậy, giả sử P(n) đúng, với n là một số nguyên bất kỳ. Vì
1 + 2 + · · · + n + (n + 1) = (1 + 2 + · · · + n) + (n + 1)
n(n + 1)
=
+ (n + 1)
2
(n + 1)(n + 2)
=
2
nên P(n + 1) đúng.
Theo quy nạp ta có P(n) đúng với mọi số n ∈ N.
6 / 37
Ví dụ
Chứng minh rằng
1
2
1
4
1
8
1
2n
+
+
+ · · · +
< 1
với mọi n ≥ 1.
7 / 37
Ví dụ
Định lý
3
Với mọi n ∈ N, ta có n − n chia hết cho 3.
Đặt P(n) là mệnh đề
3
”n − n chia hết cho 3.”
8 / 37
Chứng minh.
Bước cơ sở: P(0) đúng vì 03 − 0 = 0 chia hết cho 3.
▶
▶
Bước quy nạp: Ta sẽ chứng minh rằng, với mọi n ∈ N, mệnh
đề
P(n) ⇒ P(n + 1)
đúng.
Thật vậy, giả sử P(n) đúng, với n là một số nguyên bất kỳ. Vì
(n + 1)3 − (n + 1) = n3 + 3n2 + 3n + 1 − n − 1
= n3 + 3n2 + 2n
= n3 − n + 3n2 + 3n
= (n3 − n) + 3(n2 + n)
chia hết cho 3 nên P(n + 1) đúng.
Theo quy nạp ta có P(n) đúng với mọi số n ∈ N.
9 / 37
Ví dụ chứng minh sai
Định lý (Sai)
Mọi con ngựa đều cùng màu.
Đặt P(n) là mệnh đề
”Trong mọi tập gồm n con ngựa, các con ngựa đều
cùng màu.”
10 / 37
Đặt P(n) là mệnh đề
”Trong mọi tập gồm n con ngựa, các con ngựa đều
cùng màu.”
Chứng minh Sai.
▶
▶
Bước cơ sở: P(1) đúng vì chỉ có một con ngựa.
Bước quy nạp: Giả sử P(n) đúng để chứng minh P(n + 1)
đúng.
Xét tập gồm n + 1 con ngựa {h1, h2, · · · , hn+1
}
▶
▶
Các con h1, h2, . . . , hn có cùng màu (giả thiết quy nạp).
Các con h2, h3, . . . , hn+1 có cùng màu (giả thiết quy nạp).
Vậy
màu(h1) = màu(h2, . . . , hn) = màu(hn+1).
Vậy các con ngựa {h1, h2, · · · , hn+1} đều cùng màu. Có nghĩa
rằng P(n + 1) đúng.
Theo quy nạp ta có P(n) đúng với mọi số n ∈ N.
11 / 37
Bài tập
1. Chứng minh rằng
n
∑
n(n + 1)(2n + 1)
i2 =
6
i=1
2
2. Chứng minh rằng 2n > n với n ≥ 5.
3. Chứng minh rằng với mọi n ≥ 1,
F(n − 1)F(n + 1) − F(n2) = (−1)n
với F(i) là số Fibonacci thứ i.
12 / 37
Ví dụ lát gạch
B
2n
2n
Hình: Lát gạch và đặt
tượng Bill
Hình: Gạch
Hình: Sân
13 / 37
Định lý
Với mọi n, luôn có cách lát gạch một sân 2n × 2n chỉ để lại một ô
trống ở giữa (để đặt tượng Bill).
14 / 37
Chứng minh thử.
Xét P(n) là mệnh đề
”Có cách lát gạch sân 2n × 2n để lại một ô ở giữa.”
▶
▶
Bước cơ sở: P(0) đúng vì chỉ có một ô dành cho Bill.
Bước quy nạp: !
15 / 37
Chứng minh.
Xét P(n) là mệnh đề
”Với mỗi vị trí đặt tượng Bill trong sân 2n ×2n, ta đều
có cách lát gạch kín sân.”
B
▶
▶
2n
Bước cơ sở: P(0) đúng vì chỉ có
một ô dành cho Bill.
X
X
X
Bước quy nạp: Giả sử P(n) đúng,
ta chứng minh P(n + 1) đúng.
2n
2n
2n
Theo quy nạp ta có P(n) đúng với mọi số n ∈ N.
16 / 37
15-Puzzle
2
6
43
87
5
9
5
9
2
6
43
87
⇒
:
21
26
22
25
23
:
21
26
22
25
24
24
23
Chuyển hợp lệ: di chuyển một số sang ô trống cạnh nó.
17 / 37
15-Puzzle
Có thể chuyển từ
2
6
43
87
5
9
2
6
43
87
5
9
sang
:
21
26
22
25
23
:
21
25
22
26
23
24
24
không?
18 / 37
8-Puzzle
A
D
CB
FE
A
D
H
CB
FE
A
D
H
CB
F
G
E
GH
G
(a)
(b)
(c)
19 / 37
8-Puzzle
Bài tập
Liệu có thể tìm được một dãy chuyển hợp lệ để chuyển từ
A
D
CB
FE
A
D
CB
FE
sang
HG
GH
20 / 37
Tải về để xem bản đầy đủ
37 trang
14740
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 3: Quy nạp - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_toan_roi_rac_bai_4_quy_nap_tran_vinh_duc.pdf
