Transcript PPT

Intro to Induction
Supplementary Notes
Prepared by Raymond Wong
Presented by Raymond Wong
1
e.g.1 (Page 4)

Illustration of “Proof by Contradiction”
We are going to prove that a claim C is correct
Proof by Contradiction:
Suppose “NOT C”
….
Derive some results, which may contradict to
1. “NOT C”, OR
e.g., we derived that C is true finally
2. some facts
e.g., we derived that “1 = 4”
2
Suppose that I want to prove that the above claim
is correct by “Proof by Contradiction”.
e.g.1

Illustration of “Proof by smallest counter
example”
We are going to prove the following claim C:
statement P(m) is true for each non-negative integer m, namely 0, 1, 2, …
P(0)
true
P(1)
true
P(2)
true
P(3)
true
P(4)
true
…
true
If we can prove that statement P(m) is
true for each non-negative integer
separately, then we can prove the above
claim C is correct.
3
Suppose that I want to prove that the above claim
is correct by “Proof by Contradiction”.
e.g.1

Illustration of “Proof by smallest counter
example”
We are going to prove the following claim C:
statement P(m) is true for each non-negative integer m, namely 0, 1, 2, …
P(0)
true
P(1)
true
P(2)
true
false
P(3)
true
P(4)
true
false
…
true
Suppose “NOT C”.
We can assume that there exists a nonnegative integer k’ such that
P(k’) is false
There may exist another non-negative integer
k such that
P(k) is false
4
Suppose that I want to prove that the above claim
is correct by “Proof by Contradiction”.
e.g.1

Illustration of “Proof by smallest counter
example”
We are going to prove the following claim C:
statement P(m) is true for each non-negative integer m, namely 0, 1, 2, …
P(0)
true
P(1)
true
P(2)
true
false
P(3)
true
P(4)
true
false
…
true
Suppose “NOT C”.
We can assume that there exists a smallest
non-negative integer k such that
P(k) is false
Why?
This is called by “Proof by smallest counter example”.
5
e.g.2 (Page 5)
e.g., P(n) is
n(n+1)
“0+1+2+…+n =
”
2
Steps for “Proof by smallest counter example”
We are going to prove the following claim C:
statement P(n) is true for each non-negative integer n, namely 0, 1, 2, …
Step 1: Suppose that claim C is not true.
P(0)
true
P(1)
true
P(2)
true
false
P(3)
true
P(4)
true
false
…
true
Suppose “NOT C”.
Step 2: there exists a smallest non-negative integer m such that
P(m) is false.
Step 3: We want to show that this value m must be greater
than the smallest value (i.e., 0)
Step 4: We derive that P(i) is true for 0  i < m
Step 5: We consider a special case that P(m-1) is true.
Step 6: Consider the LHS (or some components) of P(m)
Prove that P(m) is true (by using P(m-1))
Step 7: We have a contradiction that P(m) is false
Step 8: Thus, by the principle of proof by contradiction,
claim C is correct.
6
e.g.3 (Page 14)

Illustration of “Proof by mathematical
induction”
We are going to prove the following claim C:
statement P(n) is true for each non-negative integer n, namely 0, 1, 2, …
P(0)
true
P(1)
true
P(2)
true
P(3)
true
P(4)
true
…
true
If we can prove that statement P(n) is
true for each non-negative integer
separately, then we can prove the above
claim C is correct.
7
e.g.3

Illustration of “Proof by mathematical
induction”
We are going to prove the following claim C:
statement P(n) is true for each non-negative integer n, namely 0, 1, 2, …
P(0)
P(1)
true
Step 1: Prove that P(0) (i.e., the base case) is true.
Verify that P(0) is true
P(2)
P(3)
P(4)
…
8
e.g.3

Illustration of “Proof by mathematical
induction”
We are going to prove the following claim C:
statement P(n) is true for each non-negative integer n, namely 0, 1, 2, …
P(0)
true
P(1)
true
P(2)
true
P(3)
true
P(4)
true
…
true
Step 1: Prove that P(0) (i.e., the base case) is true.
Verify that P(0) is true
Step 2: Prove that “P(n-1) P(n)” is true for all n > 0.
Step 2(a): Assume that P(n-1) is true for n > 0.
Inductive Hypothesis
Step 2(b): According to P(n-1),
we deduce that P(n) is true.
Inductive Step
9
e.g.4 (Page 15)
Prove that n  0, 2n+1  n2+2
Let P(n) be “2n+1  n2+2“
We want to show that 20+1  02+2
Step 1: Prove that P(0) (i.e., the base case) is true.
Consider 20+1 = 2
= 0+2
 02+2
Thus, P(0) is true.
10
e.g.4
Prove that n  0, 2n+1  n2+2
Let P(n) be “2n+1  n2+2“
11
Prove that n  0, 2n+1  n2+2
Let P(n) be “2n+1  n2+2“
e.g.4
Step 2: Prove that “P(n-1) P(n)” is true for all n > 0.
Step 2(a): Assume that P(n-1) is true for n > 0.
That is, 2(n-1)+1  (n-1)2+2 for n > 0.
2n  (n-1)2+2 for n > 0.
Step 2(b): According to P(n-1),
we deduce that P(n) is true.
Consider 2n+1 = 2n . 2
 [(n-1)2+2] . 2
= 2(n-1)2+2. 2
= 2(n2-2n+1)+4
= 2n2-4n+2+4
We want to show that 2n+1  n2+2
= (n2+2) + (n – 2)2
 n2+2
(Since (n-2)2  0)
Thus, 2n+1  n2+2
That is, P(n) is true.
= 2n2-4n+6
What should I do next?
We prove that “P(n-1) P(n)” is true
= (n2+n2) – 4n + (2+4)
for all n > 0
= n2+2 + n2 – 4n + 4
= (n2+2) + (n2 – 4n + 4)
By Mathematical Induction,
n  0, 2n+1  n2+2
12
e.g.5 (Page 16)
Prove that n  2, 2n+1 > n2+3
Let P(n) be “2n+1 > n2+3“
We want to show that 22+1 > 22+3
Step 1: Prove that P(2) (i.e., the base case) is true.
Consider 22+1 = 23
=8
>7
= 22+3
Thus, P(2) is true.
13
e.g.5
Prove that n  2, 2n+1 > n2+3
Let P(n) be “2n+1 > n2+3“
14
Prove that n  2, 2n+1 > n2+3
Let P(n) be “2n+1 > n2+3“
e.g.5
Step 2: Prove that “P(n-1) P(n)” is true for all n > 2.
Step 2(a): Assume that P(n-1) is true for n > 2.
That is, 2(n-1)+1 > (n-1)2+3 for n > 2.
2n > (n-1)2+3 for n > 2.
Step 2(b): According to P(n-1),
we deduce that P(n) is true.
Consider 2n+1 = 2n . 2
We want to show that 2n+1 > n2+3
= (n2+3) + (n2 – 4n + 4 + 1)
>[(n-1)2+3] . 2
= (n2+3) + (n – 2)2 + 1
> n2+3
(Since (n-2)2 + 1 0)
= 2(n-1)2+3. 2
Thus, P(n) is true.
= 2(n2-2n+1)+6
We prove that “P(n-1) P(n)” is true
for all n > 2
=
2n2-4n+2+6
= 2n2-4n+8
What should I do next?
= (n2+n2) – 4n + (3+5)
= n2+3 + n2 – 4n + 5
By Mathematical Induction,
n  2, 2n+1 > n2+3
= (n2+3) + (n2 – 4n + 5)
15
e.g.6 (Page 18)
Prove that k  Z+, 1+3+5+…+(2k-1) = k2
Let P(k) be “1+3+5+…+(2k-1) = k2”
Step 1: Prove that P(1) (i.e., the base case) is true.
Consider 1 = 12
Thus, P(1) is true.
We want to show that
1 = 12
16
e.g.6
Prove that k  Z+, 1+3+5+…+(2k-1) = k2
Let P(k) be “1+3+5+…+(2k-1) = k2”
17
Prove that k  Z+, 1+3+5+…+(2k-1) = k2
Let P(k) be “1+3+5+…+(2k-1) = k2”
e.g.6
Step 2: Prove that “P(n-1) P(n)” is true for all n > 1.
Step 2(a): Assume that P(n-1) is true for n > 1.
That is, 1+3+5+…+(2(n-1)-1) = (n-1)2 for n > 1.
1+3+5+…+(2n-3) = (n-1)2 for n > 1.
Step 2(b): According to P(n-1),
we deduce that P(n) is true.
We want to show that
1+3+5+…+(2n-1) = n2
Consider 1+3+5+…+(2n-1)
= 1+3+5+…+(2n-3)+(2n-1)
= (n-1)2 + (2n-1)
= (n2 – 2n + 1) + (2n – 1)
= n2
Thus, P(n) is true.
We prove that “P(n-1) P(n)” is true
for all n > 1
By Mathematical Induction,
k  Z+, 1+3+5+…+(2k-1) = k2
18
P(1) is true.
P(2) is false.
e.g.7 (Page 19)
For what positive integer values of n is “2n > n2”?
Let P(n) be “2n > n2”
We don’t know the base case.
Thus, we need to test the “smallest” value of n for the
base case.
Step 1: Prove that P( ? ) (i.e., the base case) is true.
Consider P(1)
Consider 21 = 2
We want to see whether P(1) is true.
(i.e., whether “21 > 12” is true.)
> 12
Thus, P(1) is true.
Consider P(2)
Consider 22 = 4
We want to see whether P(2) is true.
(i.e., whether “22 > 22” is true.)
> 22
Thus, P(2) is false.
19
P(1) is true.
P(2) is false.
P(3) is false.
e.g.7
P(4) is false.
For what positive integer values of n is “2n > n2”?
Let P(n) be “2n > n2”
We don’t know the base case.
Thus, we need to test the “smallest” value of n for the
base case.
Step 1: Prove that P( ? ) (i.e., the base case) is true.
Consider P(3)
Consider 23 = 8
We want to see whether P(3) is true.
(i.e., whether “23 > 32” is true.)
> 32
Thus, P(3) is false.
Consider P(4)
Consider 24 = 16
We want to see whether P(4) is true.
(i.e., whether “24 > 42” is true.)
> 42
Thus, P(4) is false.
20
P(1) is true.
P(5) is true.
P(2) is false.
P(6) is true.
P(3) is false.
e.g.7
P(4) is false.
For what positive integer values of n is “2n > n2”?
Let P(n) be “2n > n2”
We don’t know the base case.
Thus, we need to test the “smallest” value of n for the
base case.
Step 1: Prove that P(
? ) (i.e., the base case) is true.
P(5)
Consider P(5)
Consider 25 = 32
We want to see whether P(5) is true.
(i.e., whether “25 > 52” is true.)
> 52
Thus, P(5) is true.
Consider P(6)
Consider 26 = 64
> 62
Thus, P(6) is true.
We want to see whether P(6) is true.
(i.e., whether “26 > 62” is true.)
Thus, we guess that P(7), P(8), …are also true.
Thus, we think that the base case is P(5).
21
e.g.7
For what positive integer values of n is “2n > n2”?
Let P(n) be “2n > n2”
Prove that n  5, 2n > n2
Step 1: Prove that P(
? ) (i.e., the base case) is true.
P(5)
Thus, we think that the base case is P(5).
22
e.g.7
Prove that n  5, 2n > n2
Let P(n) be “2n > n2”
Step 1: Prove that P(
? ) (i.e., the base case) is true.
P(5)
23
e.g.7
Prove that n  5, 2n > n2
Let P(n) be “2n > n2”
Step 1: Prove that P(
? ) (i.e., the base case) is true.
P(5)
Consider 25 = 32
> 52
We want to show that
“25 > 52”
Thus, P(5) is true.
24
e.g.7
Prove that n  5, 2n > n2
Let P(n) be “2n > n2”
25
Prove that n  5, 2n > n2
Let P(n) be “2n > n2”
e.g.7
Step 2: Prove that “P(n-1) P(n)” is true for all n > 5.
Step 2(a): Assume that P(n-1) is true for n > 5.
That is, 2n-1 > (n-1)2 for n > 5.
Step 2(b): According to P(n-1),
we deduce that P(n) is true.
We want to show that
2n > n 2
Thus, 2n > n2
Consider 2n
= 2n-1 . 2
Thus, P(n) is true.
> (n-1)2 . 2
= (n2 – 2n + 1) . 2
= 2n2 – 4n + 2
What should I do next?
= n2 + n2 – 4n + 2
> n2 + n2 – 4n
> n2 + n2 – 5.n
> n2 + n2 – n.n
= n2
(Since n > 5)
We prove that “P(n-1) P(n)” is true
for all n > 5
By Mathematical Induction,
n  5, 2n > n2
26
Prove that n  5, 2n > n2
Let P(n) be
“2n
>
Alternative Derivation
n2 ”
e.g.7
Step 2: Prove that “P(n-1) P(n)” is true for all n > 5.
Step 2(a): Assume that P(n-1) is true for n > 5.
That is, 2n-1 > (n-1)2 for n > 5.
We want to show that
2n > n 2
Step 2(b): According to P(n-1),
we deduce that P(n) is true.
= n2 + 7
> n2
Consider 2n
= 2n-1 . 2
> (n-1)2 . 2
= (n2 – 2n + 1) . 2
= 2n2 – 4n + 2
= n2 + n2 – 4n + 2
= n2 + n2 – 4n + 4 – 4 +2
=
n2
+
(n2
– 4n + 4) – 2
= n2 + (n – 2)2 – 2
> n2 + 9 – 2
Thus, 2n > n2
Thus, P(n) is true.
We prove that “P(n-1) P(n)” is true
for all n > 5
By Mathematical Induction,
n  5, 2n > n2
Since (n-2)2 is increasing when n> 5,
we have (n-2)2 > (5-2)2
= 32
=9
27
e.g.8 (Page 21)

Illustration of “Proof by mathematical
induction” (Weak Induction)
We are going to prove the following claim C:
statement P(n) is true for each non-negative integer n, namely 0, 1, 2, …
P(0)
P(1)
true
Step 1: Prove that P(0) (i.e., the base case) is true.
Verify that P(0) is true
P(2)
P(3)
P(4)
…
28
e.g.8

Illustration of “Proof by mathematical
induction” (Weak Induction)
We are going to prove the following claim C:
statement P(n) is true for each non-negative integer n, namely 0, 1, 2, …
P(0)
true
P(1)
true
P(2)
true
P(3)
true
P(4)
true
…
true
Step 1: Prove that P(0) (i.e., the base case) is true.
Verify that P(0) is true
Step 2: Prove that “P(n-1) P(n)” is true for all n > 0.
Step 2(a): Assume that P(n-1) is true for n > 0.
Inductive Hypothesis
Step 2(b): According to P(n-1),
we deduce that P(n) is true.
Inductive Step
29
e.g.8

Illustration of “Proof by mathematical
induction” (Strong Induction)
We are going to prove the following claim C:
statement P(n) is true for each non-negative integer n, namely 0, 1, 2, …
Step 1: Prove that P(0) (i.e., the base case) is true.
P(0) true
P(1)
Verify that P(0) is true
P(2)
P(3)
P(4)
…
30
e.g.8

Illustration of “Proof by mathematical
induction” (Strong Induction)
We are going to prove the following claim C:
statement P(n) is true for each non-negative integer n, namely 0, 1, 2, …
Step 1: Prove that P(0) (i.e., the base case) is true.
P(0) true
P(1)
true
Verify that P(0) is true
P(2)
Step 2: Prove that “P(0)P(1)…P(n-1) P(n)” is true
for all n > 0.
P(3)
Step 2(a): Assume that P(0)P(1)…P(n-1) is true for n > 0.
P(4)
…
Inductive Hypothesis
Step 2(b): According to P(0)P(1)…P(n-1),
we deduce that P(n) is true.
Inductive Step
31
e.g.8

Illustration of “Proof by mathematical
induction” (Strong Induction)
We are going to prove the following claim C:
statement P(n) is true for each non-negative integer n, namely 0, 1, 2, …
Step 1: Prove that P(0) (i.e., the base case) is true.
P(0) true
P(1)
P(2)
P(3)
P(4)
…
true
true
Verify that P(0) is true
Step 2: Prove that “P(0)P(1)…P(n-1) P(n)” is true
for all n > 0.
Step 2(a): Assume that P(0)P(1)…P(n-1) is true for n > 0.
Inductive Hypothesis
Step 2(b): According to P(0)P(1)…P(n-1),
we deduce that P(n) is true.
Inductive Step
32
e.g.8

Illustration of “Proof by mathematical
induction” (Strong Induction)
We are going to prove the following claim C:
statement P(n) is true for each non-negative integer n, namely 0, 1, 2, …
Step 1: Prove that P(0) (i.e., the base case) is true.
P(0) true
P(1)
true
P(2)
true
P(3)
true
P(4)
…
Verify that P(0) is true
Step 2: Prove that “P(0)P(1)…P(n-1) P(n)” is true
for all n > 0.
Step 2(a): Assume that P(0)P(1)…P(n-1) is true for n > 0.
Inductive Hypothesis
Step 2(b): According to P(0)P(1)…P(n-1),
we deduce that P(n) is true.
Inductive Step
33
e.g.8

Illustration of “Proof by mathematical
induction” (Strong Induction)
We are going to prove the following claim C:
statement P(n) is true for each non-negative integer n, namely 0, 1, 2, …
Step 1: Prove that P(0) (i.e., the base case) is true.
P(0) true
P(1)
true
P(2)
true
P(3)
true
P(4) true
…
Verify that P(0) is true
Step 2: Prove that “P(0)P(1)…P(n-1) P(n)” is true
for all n > 0.
Step 2(a): Assume that P(0)P(1)…P(n-1) is true for n > 0.
Inductive Hypothesis
Step 2(b): According to P(0)P(1)…P(n-1),
we deduce that P(n) is true.
Inductive Step
34
e.g.9 (Page 26)
e.g., 4 = 22
12 = 22 . 3
Prove that every positive integer n is
a power of a prime number OR a product of powers of prime numbers
Let P(n) be “n is a power of a prime number OR a product of powers of prime numbers.”
We want to show that 1 is a power of a prime number OR a product of powers of
prime numbers
Step 1: Prove that P(1) (i.e., the base case) is true.
Consider 1 = 20
which is a power of a prime number (i.e., 2).
Thus, P(1) is true.
35
e.g.9
Prove that every positive integer n is
a power of a prime number OR a product of powers of prime numbers
Let P(n) be “n is a power of a prime number OR a product of powers of prime numbers.”
36
Prove that every positive integer n is
a power of a prime number OR a product of powers of prime numbers
Let P(n) be “n is a power of a prime number OR a product of powers of prime numbers.”
e.g.9
Step 2: Prove that “P(1)P(2)…P(n-1) P(n)” is true
for all n > 1.
Step 2(a): Assume that P(1)P(2)…P(n-1) is true for n > 1.
That is, 1 is a power of a prime number OR a product of powers of prime numbers.
2 is a power of a prime number OR a product of powers of prime numbers.
…
n-1 is a power of a prime number OR a product of powers of prime numbers.
Step 2(b): According to P(0)P(1)…P(n-1),
we deduce that P(n) is true.
We want to show that
n is a power of a prime number OR a product of powers of prime numbers.
Consider two cases.
n is a power of a prime number
Case 1: n is a prime number.
n is a product of two smaller numbers,
namely a and b (where a < n and b < n)
Case 2: n is not a prime number.
Thus, n = a . b
Note that a is a power of a prime number or a product of powers of prime numbers.
Note that b is a power of a prime number or a product of powers of prime numbers
Thus, n is a power of a prime number or a product of powers of prime numbers
37
Prove that every positive integer n is
a power of a prime number OR a product of powers of prime numbers
Let P(n) be “n is a power of a prime number OR a product of powers of prime numbers.”
e.g.9
Step 2: Prove that “P(1)P(2)…P(n-1) P(n)” is true
for all n > 1.
Step 2(a): Assume that P(1)P(2)…P(n-1) is true for n > 1.
That is, 1 is a power of a prime number OR a product of powers of prime numbers.
2 is a power of a prime number OR a product of powers of prime numbers.
…
n-1 is a power of a prime number OR a product of powers of prime numbers.
Step 2(b): According to P(0)P(1)…P(n-1),
we deduce that P(n) is true.
Thus, P(n) is true.
We prove that “P(1)P(2)…P(n-1) P(n)” is true
for all n > 1
By Strong Mathematical Induction,
every positive integer n is
a power of a prime number OR a product of powers of prime numbers
38