展开查看详情
1 . Proof by the
Well ordering principle
09/28/18
2 .Well Ordering Principle
• Every nonempty set of
nonnegative integers has a
least element
09/28/18
3 .Well Ordering Principle
• Every nonempty set of
nonnegative integers has a
least element
09/28/18
4 .Well Ordering Principle
• Every nonempty set of
nonnegative integers has a
least element
09/28/18
5 .Well Ordering Principle
Every nonempty set of nonnegative
integers has a least element
We actually used this already when
arguing that a fraction can be
reduced to “lowest terms”
The set of factors of a positive
integer is nonempty
09/28/18
6 . To prove P(n) for every
nonnegative n:
• Let C = {n: P(n) is false} (the set of
“counterexamples”)
• Assume C is nonempty in order to
derive a contradiction
• Let m be the smallest element of C
• Derive a contradiction (perhaps by
finding a smaller member of C)
09/28/18
7 . A Proof Using WOP
• Given a stack of pancakes, make a
nice stack with the smallest on top,
then the next smallest, …, and the
biggest on the bottom
• By using only one operation: Grabbing
a wad off the top and flipping it!
• Theorem: n pancakes can be sorted
using 2n-3 flips (n≥2)
09/28/18
8 . One way to do it
• Grab under the
biggest pancake
and bring it to the
top
• Flip the entire
stack over
• Repeat, ignoring
the bottom
pancake
09/28/18
9 . Why does this take 2n-3
flips?
• For n≥2, let P(n) := “n pancakes can be
sorted using 2n-3 flips”
• Suppose this is false for some n
• Let C = {n: P(n) is false}
• C has a least element by WOP. Call it m.
• So m pancakes cannot be sorted using
2m-3 flips and m is the smallest
number for which that is the case
09/28/18
10 . Why does this take 2n-3
flips?
• m≠2 since one flip sorts 2 pancakes
• But if m>2 then it takes 2 flips to get
the biggest pancake on the bottom …
• and 2(m-1)-3 to sort the rest since
P(m-1) is true (since m-1 < m) …
• for a total of 2(m-1)-3+2 = 2m-3,
contradicting the assumption that
P(m) is false
09/28/18
12 . Summing powers of 2
• Thm: 1+2+22+23+…+2n =2n+1-1
• E.g. 1+2+22 = 1+2+4 = 7 = 23-1
09/28/18
13 . Summing powers of 2
• Thm: For every n≥0,
1+2+22+23+…+2n =2n+1-1
• E.g. 1+2+22 = 1+2+4 = 7 = 23-1
• Let P(n) be the statement
1+2+22+23+…+2n = 2n+1-1
09/28/18
14 . Summing powers of 2
• Let C = {n: P(n) is false}
= {n: 1+2+22+23+…+2n ≠2n+1-1}.
• Then C is nonempty by hypothesis.
• Then C has a minimal element m by
WOP.
• m cannot be 0 since P(0) is true:
1=20=20+1-1
• So m > 0
09/28/18
15 . Summing powers of 2
• But if
1+2+22+23+…+2m ≠2m+1-1
• then subtracting 2m from both sides:
1+2+22+23+…+2m-1 ≠2m+1-1-2m
= 2m-1
(since 2m+2m = 2m+1)
• But then P(m-1) is also false,
contradiction.
09/28/18
16 . Summing powers of 2
• Where did we use the fact that P(0) is
true, so m > 0?
09/28/18
17 . A Notational Note
• Learn to avoid ellipses …!
n
P(n) ≡∑ 2 =2i n+1
−1
i=0
Theorem: (∀n)P(n)
09/28/18
18 . A geometric “proof”
n
∑2 i
=2n+1
−1≡
i=0
n
2 n+1
=1+∑ 2 ≡ i 1
i=0 1 1/2 1/2
n
1
2= n +∑ 2i−n 1+½+¼+⅛+…
1+½+¼+⅛
1
1+½+¼
+½
2 i=0
09/28/18
热门城市
