P(n) is a propositional function over positive integers and we typically want to prove "n: n ³ 1 P(n)
To prove this using induction we must show:
P(1) is true P(k) ® P(k+1)
In other words [P(1) ^ ("k: P(k) ® P(k+1))] ® "n: P(n)
Need to show that P(k+1) cannot be false when P(k) is true
This is accomplished by:
- assuming P(k), induction hypothesis, to be true
- then use hypothesis to show that P(k+1) must also be true.
p q p ® q F F T F T T T F F T T T
Example
Claim that P(n) = 1 + 2 + 3 + ... + n = n(n+1)/2
P(1) = 1 = 1(1+1)/2 = 2/2 =1
P(2) = 1+2 = 2(2+1)/2 = 2(3)/2 = 6/2 = 3
P(3) = 1+2+3 = 3(3+1)/2 = 3(4)/2 = 12/2 = 6
:
P(n) = 1 + 2 + 3 + ... + n = n(n+1)/2
Proof - Use induction to prove that for every integer n³1:
P(n)
1 + 2 + 3 + ... + n = n(n+1)/2
Base Step: P(1)
n = 1 then:
1 = 1(1+1)/2 = 2/2 = 1
Inductive Step: P(k) ® P(k+1)
Inductive Hypothesis (IH): assume P(k) is true, then under this assumption show that P(k+1) must also be true
By P(k):
1 + 2 + 3 + ... + k = k(k+1)/2
Must show P(k+1):
1 + 2 + 3 + ... + k + (k+1) = (k+1)((k+1)+1) / 2
= (k+1)(k+2) / 2
Start with assumption P(k):
P(k) = k(k+1)/2 Start with P(k) P(k) + (k+1) = k(k+1)/2 + (k+1) Add k+1 to both sides
(for the k+1 result)= k(k+1)/2 + 2(k+1)/2 = [ k(k+1) + 2(k+1)] / 2 = [ (k2 + k)+ (2k+2)] / 2 = [ k2+3k+2] / 2 \ = (k+1)(k+2) / 2
Example - Use induction to prove that for every integer n³1:
P(n): 1 + 2 + 22 + ... + 2n = 20 + 21 + 22 + ... + 2n = 2n+1 - 1
Question What is P(4)?
Base Step: P(1)
n = 1 then:
20 + 21 = 21+1-1 = 22-1 = 3
3 = 3Question Why is P(1) the base? Why not P(0)?
Inductive Step: P(k) ® P(k+1)
Inductive Hypothesis (IH): assume P(k) is true, then under this assumption show that P(k+1) must also be true
By P(k):
20 + 21 + 22 + ... + 2k = 2k+1 - 1
Must show P(k+1):
20 + 21 + 22 + ... + 2k + 2k+1 = 2k+1+1 - 1 = 2k+2 - 1
Start with assumption P(k):
P(k) = 2k+1 - 1 Start with Inductive Hypothesis P(k) P(k) + 2k+1 = 2k+1 - 1 + 2k+1 Add 2k+1 to both sides
(for the k+1 result)= (2k+1 + 2k+1) - 1 = 2*2k+1 - 1 2*2k+1 = 2k+1 + 2k+1 \ = 2k+2 - 1 Multiply by 2
Example - Use induction to prove that the sum of the first n odd positive integers = n2
P(n): 1 + 3 + 5 + ... + 2n - 1 = n2
Note that:
P(1): 1=1 P(2): 1+3=4 P(3): 1+3+5=9 P(4): 1+3+5+7=16 P(5): 1+3+5+7+9=25 Question What is P(6)?
Base Step: P(1)
n = 1 then:
2(1) - 1 = 12 2(1)-1 Definition of odd number 1
2 - 1 = 1
1 = 1Inductive Step: P(k) ® P(k+1)
Inductive Hypothesis (IH): assume P(k) is true, then under this assumption show that P(k+1) must also be true
By P(k):
1 + 3 + 5 + ... + 2k - 1 = k2
Must show P(k+1):
(1 + 3 + ... + 2k - 1) + 2(k + 1) - 1 = (k+1)2
Start with assumption P(k):
P(k) = k2 P(k) Inductive Hypothesis P(k) + 2(k + 1) - 1 = k2 + 2(k + 1) - 1 Add 2(k+1)-1 to
both sides (for the k+1 result)= k2 + 2k + 1 Multiplication, Addition
and Associative properties= (k+1)(k+1) Factoring: k2 + 2k + 1 = (k+1)(k+1) \ = (k+1)2
Example - The Number of Subsets of a Finite Set
Use mathematical induction to show that if S is a finite set with n elements where n is a nonnegative integer, then S has 2n subsets.
P(n) = 2n
For n=0, there are 20 = 1 subsets.
S = Æ
Subsets are: Æ
For n=2, there are 22 subsets.
S = {b, c}
Subsets are: {b, c}, {b}, {c}, {b, c}, Æ
For n=3, there are 22+22 = 23 subsets.
S = {b, c} È {a}
Subsets are: {b}, {c}, {b, c}, Æ, {a, b, c}, {a}, {a, b}, {a, c}
Proof
P(n) proposition that a set with n elements has 2n subsets.
Base step
20 = 1 so P(0) is true for Æ
Inductive Step: P(k) ® P(k+1)
For k elements assume 2k subsets, P(k) is true.
Must show: P(k+1) is true, that a set of k+1 elements has 2k+1 subsets
P(k+1) = 2k+1
P(k) = 2k Inductive Hypothesis S has k elements and 2k subsets Inductive Hypothesis T = S È {a} T has k+1 elements including a S = T - {a} X Í S X is any subset of S X Í T ^ X È {a} Í T For each X Í S there are two subsets of T S has k elements and 2k subsets Inductive Hypothesis T has k+1 elements and 2k + 2k subsets P(k+1) = 2k + 2k = 2(2k) \ = 2k+1
Example
Recall the De Morgan law that:
______ __ __
A1 ^ A2 = A1 v A2Use induction to prove the following generalization for the De Morgan law of Boolean algebra.
______________ __ __ __
P(n): A1 ^ A2 ^ ... ^ An = A1 v A2 v ... v An for every integer n³2Base Step: P(2)
n = 2 then De Morgan's law holds:
______ __ __
P(2): A1 ^ A2 = A1 v A2Question Why is P(2) the base?
Inductive Step: P(k) ® P(k+1)
Inductive Hypothesis (IH): assume P(k) is true, then under this assumption show that P(k+1) must also be true
______________ __ __ __
P(k): A1 ^ A2 ^ ... ^ Ak = A1 v A2 v ... v AkNeed to show P(k+1):
_____________________ __ __ __ ____
P(k+1): A1 ^ A2 ^ ... ^ Ak ^ Ak+1 = A1 v A2 v ... v Ak v Ak+1Start with k+1 case where k³2 since already proven for P(2):
| _____________________ A1 ^ A2 ^ ... ^ Ak ^ Ak+1 |
_______________________ = (A1 ^ A2 ^ ... ^ Ak ) ^ Ak+1 |
Grouping (A1 ^ A2 ^ ... ^ Ak ) |
| _________________ ____ = (A1 ^ A2 ^ ... ^ Ak ) v Ak+1 |
De Morgan's law for P(2) | |
| \ | __ __
__ ____ = A1 v A2 v ... v Ak v Ak+1 |
______________
__ __
__ IH: P(k): A1 ^ A2 ^ ... ^ Ak = A1 v A2 v ... v Ak |
Note:
1! = 1
2! = 2 * 1!
3! = 3 * 2!
:
n! = n * (n-1)!(n+1)! = (n+1) * n!
Example - Use induction to prove that 2n < n! for every integer n³4
P(n): 2n < n! for every integer n³4
Base Step: P(4)
n = 4 then:
24 = 16 < 24 = 4!Question Why is P(4) the base?
n = 3 then:
23 = 9 > 6 = 3!
Inductive Step: P(k) ® P(k+1)
Inductive Hypothesis (IH): assume P(k) is true, then under this assumption show that P(k+1) must also be true
By P(k) for k³4:
2k < k!
Need to show P(k+1) for k³4:
2k+1 < (k+1)!
Start with P(k) assumption:
2k < k! IH: 2k < k! 2*2k < 2 * k! multiply both sides by 2 < (k+1) * k! k³4 so 2 < k+1 \ = (k+1)! definition of n!
Example - Prove by Induction that: 5 divides n5 - n
Base Step:
P(0): 5 divides 0.
5 divides 05 - 0 = 1 - 0 = 1
Question Why is P(0) base?
Inductive Step: P(k) ® P(k+1)
Assume P(k): 5 divides k5 - k
Must prove P(k+1): 5 divides (k + 1)5 - (k + 1)
P(k) 5 divides k5 - k Induction Hypothesis (k + 1)5 - (k + 1) = k5 + 5k4 + 10k3 +10k2 +5k + 1 - k - 1 Substitute k+1 for k and multiply = k5 + 5k4 + 10k3 +10k2 +4k Collect terms = (k5 - k) + (5k4 + 10k3 +10k2 + 5k) Factor = P(k) + (5k4 + 10k3 +10k2 + 5k) IH: P(k): 5 divides k5 - k \ = P(k) + 5(k4 + 2k3 +2k2 + k) 5 divides both terms of sum, 5 divides the sum
Question: Find a closed formula for a summation by examining small values of n for:
Summation:
1/2 + 1/4 + 1/8 +...+ 1/2n
Examine:
1/2 + 1/4 + 1/8 = 4/8 + 2/8 + 1/8 = 7/8
Closed formula:
1/2 + 1/4 + 1/8 +...+ 1/2n = 2n-1/2n
Question: Prove above formula using induction. Recall that 2*2n = 2n+1
Induction Hypothesis:
Base Step:
Inductive Step:
Prove:
Example
Definition: 1! = 1
n! = (n-1)! * n
{ Precondition: n ³ 1 } FACTORIAL(n)
if n = 1 then return 1
else return FACTORIAL(n-1) * n{ Postcondition: FACTORIAL(n) == n! }
Prove by induction that: FACTORIAL(n) = n!
Base Step:
P(1): If n=1 then return FACTORIAL(1) = 1!
Inductive Step: P(k) ® P(k+1)
Assume P(k): FACTORIAL(k) = k!
Must prove P(k+1):
FACTORIAL(k+1) = (k+1)!
FACTORIAL(k+1), k+1 > 1 so the algorithm else is executed.
Proof:
FACTORIAL((k+1)-1) * (k+1) k+1 = n in FACTORIAL(n-1) * n = FACTORIAL( k ) * (k+1) k = (k+1)-1 = k! * (k+1) FACTORIAL(k) = k! assumption = (k + 1)! From definition of n!