Xem mẫu
- Quy nạp
Trần Vĩnh Đức
HUST
Ngày 24 tháng 7 năm 2018
CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 37
- Tài liệu tham khảo
▶ Eric Lehman, F Thomson Leighton & Albert R Meyer,
Mathematics for Computer Science, 2013 (Miễn phí)
▶ 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)
CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 37
- Nội dung
Nguyên lý quy nạp
Quy nạp mạnh
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Nguyên lý quy nạp
880
81
777879
82
3 84
73747576
88
87 8685
72
71
70
69
68
67
666564
63661
260
59
58
5354 557
556
505152
49
48
47
46
45
4443 2
4 4140
9 3 3387
35
34 36
Xét vị từ P(n) trên N. Nếu 2 3 33133
0 2
2 28 9
2256 7
▶ P(0) đúng, và 24
23
22
22109
▶ với mọi n ∈ N, (P(n) ⇒ P(n + 1)) 1 8
1 1716
cũng đúng, 151143
2
110
11
thì P(n) đúng với mọi n ∈ N.
789
56
4
3
2
1
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 37
- Ví dụ
Chứng minh rằng
1 1 1 1
+ + + ··· + n < 1
2 4 8 2
với mọi n ≥ 1.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 / 37
- Ví dụ
Định lý
Với mọi n ∈ N, ta có n3 − n chia hết cho 3.
Đặt P(n) là mệnh đề
”n3 − n chia hết cho 3.”
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.”
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 37
- Bài tập
1. Chứng minh rằng
∑
n
n(n + 1)(2n + 1)
i2 =
6
i=1
2. Chứng minh rằng 2n > n2 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 12 / 37
- a proof technique in the preceding examples. But induction
rwise, there are four central squares.) A complica
Vígeneral
more dụ lát gạch tool.
reasoning
ntional architect,
d a new computer Frank
science building. As Gehry, insisted
the project went further that only spec
here were some radical fundraising ideas. One plan was to
dimensions 2n ⇥ 2n : A courtyard meeting these constraints exsists, at least for n = 2:
B
2n
2n
Hình:toLát
For larger values of n, is there a way tile agạch
2n ⇥và2n đặt
courtyard with L-s
Hình: Let’s
Hình: Sânstatue in the center? Gạchtry to prove
tượngthat
Billthis is so.
would be occupied by a statue of a wealthy potential donor.
g these constraints exsists, at least for n = 2:
e special case n = 0, the whole15.
Theorem courtyard
For all n consists
0 thereof a single
exists a tiling of a 2n ⇥ 2n courtyard wi
there are four central square.
squares.) A complication was that the
architect, Frank Gehry, insisted that only special L-shaped tiles
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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).
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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: !
CuuDuongThanCong.com https://fb.com/tailieudientucntt 15 / 37
- Proof. (successful attempt) The proof is by induction. Let P (n) be the propo
every location of Bill in a 2n ⇥ 2n courtyard, there exists a tiling of the rema
Chứng minh. Base case: P (0) is true because Bill fills the whole courtyard.
Inductive step: Asume that P (n) is true for some n 0; that is, for every loc
Xét P(n) là mệnh đềa 2n ⇥ 2n courtyard, there exists a tiling of the remainder. Divide the 2n+1 ⇥ 2
into four quadrants, each 2n ⇥ 2n . One quadrant contains Bill (B in the dia
”Với mỗi vị Place
trí đặt tượng Bill
a temporary Bill(Xtrong sân 2nin×each
in the diagram) 2n of
, ta
theđều
three central squares
this quadrant:
có cách lát gạch kín sân.”
B
▶ Bước cơ sở: P(0) đúng vì chỉ có 2n
một ô dành cho Bill. X
X X
▶ Bước quy nạp: Giả sử P(n) đúng,
2n
ta chứng minh P(n + 1) đúng.
2n 2n
Theo quy nạp ta có P(n) đúng với mọi số n ∈ N.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 16 / 37
- “mcs-ftl”
“mcs-ftl” —
— 2010/9/8
2010/9/8 —
— 0:40
0:40 —
— page
page 59
59 —
— #65
#65
15-Puzzle
3.3.
3.3.Invariants
Invariants 59
59
22 33 44 55 2 3 4 55
66 77 88 99 6 7 8 99
⇒
:: 21
21 22
22 23
23 : 21 22
24
24 26
26 25
25 24
24 26
26 25
25 23
23
(a)
(a) (b)
(b)
Figure3.5
Chuyển
Figure 3.5 The
hợp The15-puzzle
lệ: di15-puzzle
chuyển in its
in its starting
một starting configuration
số sang (a)cạnh
ô trống(a)
configuration and
and after
nó.the
after the 12-block
12-block
isismoved
movedinto
intothe
thehole
holebelow
below(b).
(b).
22 33 44 55
CuuDuongThanCong.com 6 7 8
https://fb.com/tailieudientucntt
6 7 8 99 17 / 37
- 6 7 8 9 6 7 8 9
15-Puzzle
: 21 22 23 : 21 22
24 — 26
“mcs-ftl” — 2010/9/8 — 0:40 25 — #65
page 59 24 26 25 23
(a) (b)
Có thể chuyển từ
3.3. Invariants Figure 3.5 The 15-puzzle in its starting configuration
59 (a) and after the 12-block
is moved into the hole below (b).
2 3 4 5 2 23 34 45 5
6 7 8 9 6 67 78 89 9
sang
: 21 22 23 : 21
: 22
21 22 23
24 26 25 24 26
24 25
25 23
26
(a) (b)
Figure 3.6 The desired final configuration for the 15-puzzle. Can it be achieved
không? Figure 3.5 The 15-puzzle in its starting configuration (a) and after the 12-block
by only moving one block at a time into an adjacent hole?
is moved into the hole below (b).
get all 15 blocks into their natural order. A picture of the 15-puzzle is shown in
Figure 2 3.5 along
3 4 the5 configuration after the 12-block is moved into the hole
with
below. The desired final configuration is shown in Figure 3.6.
The6 15-puzzle
7 became
8 9 very popular in North America and Europe and is still
sold in game and puzzle shops today. Prizes were offered for its solution, but
it is doubtful
: 21 that22they were
23 ever awarded, since it is impossible to get from the
CuuDuongThanCong.com
configuration in Figure 3.5(a) to the configuration in Figure 3.6 by only moving
https://fb.com/tailieudientucntt 18 / 37
one block at a time into an adjacent hole. The proof of this fact is a little tricky so
- 8-Puzzle
“mcs-ftl” — 2010/9/8 — 0:40 — page 60 — #66
Chapter 3 Induction
A B C A B C A B C
D E F D E F D F
H G H G H E G
(a) (b) (c)
Figure 3.7 The 8-Puzzle in its initial configuration (a) and after one (b) and
two (c) possible moves.
3.3.4 The 8-Puzzle
In the 8-Puzzle, there are 8 lettered tiles (A–H) and a blank square arranged in a
3 ⇥ 3 grid. Any lettered tile
CuuDuongThanCong.com
adjacent to the blank square can be slid into the blank.
https://fb.com/tailieudientucntt 19 / 37
- 8-Puzzle
“mcs-ftl” — 2010/9/8 — 0:40 — page 60 — #66
“mcs-ftl” — 2010/9/8 — 0:40 — page 61 — #67
Bài tập
60 Chapter 3 Induction
Liệu có thể tìm 3.3.
được một dãy chuyển hợp lệ để chuyển từ
Invariants
A B C A B A C B CA B C
D E F sang
D E D F E FD F
H G H G G H H E G
(a) (b) (c)
Figure 3.8 The desired final configuration of the 8-puzzle.
Figure 3.7 The 8-Puzzle in its initial configuration (a) and after one (b) and
two (c) possible moves.
2 3 4
3.3.4 The 8-Puzzle
5 6 7
CuuDuongThanCong.com In the 8-Puzzle, there are 8 lettered tiles (A–H) and a blank square arranged in20a/ 37
https://fb.com/tailieudientucntt
nguon tai.lieu . vn