CMPS 2120 Lecture Notes - Mathematical Induction
resources:
Towers of Hanoi video
Mathematical induction is a method of direct proof over well-ordered sets.
A well-ordered set is countable and ordered. The two sets generally
used in inductive proofs are N = {0,1,2,3,....} and Z+ = {1,2,3,4,...}.
(Any well-ordered set is acceptable)
Mathematical induction is not the same as inductive reasoning.
Mathematical induction is deductive reasoning.
The structure of a
standard inductive proof is essentially a direct proof.
Example of the structure:
Let P be a proposition over the well-ordered set N = {0,1,2,3...}; i.e.,
P(0), P(1), P(2), P(3), ...
The goal is to show P(n) is true for all n in N.
Step 1. BASIS STEP: P(0) is true. Show an example.
Step 2. INDUCTIVE STEP: P(k) -> P(k+1)
Inductive Hypothesis (IH) Assume P(k) is true.
Step 3. Assuming P(k), show true for P(k+1).
This is your Inductive Step.
If P(0) is true and P(k) -> P(k+1) then P(n) is true for all n in N.
Why does this work?
What you are trying to show is: "If P is true for some k out of N then
P remains true for k+1".
The antecedent (Inductive Hypothesis)
is "P is true for some k out of N; i.e. assume P(k)". The consequence is
"P remains true for k+1; i.e, P(k+1).". Follow steps for
a direct proof: Assume P(k) and show P(k+1).
You complete your proof with a concrete starting
case for which P is true (called the Basis).
With the basis you can now say true for
all n with the reasoning: true for P(0) thus true for P(1). True for
P(1) thus true for P(2). True for P(2) thus true for P(3). So on and so forth.
Since N is a well-ordered set, true for all n in N.
There are some subtleties to a proof by induction. In particular, you
are not claiming that the hypothesis *is* true for P(k). This would
be a fallacy of begging the question. You are *assuming* P(k) is true,
and, if so, showing P(k+1).
Why is induction important? Prove this algorithm works for n=100000:
// returns factorial for integer n >= 0
int fac(int n)
if n = 0
return 1
else
return fac(n-1) * n.
Messy to do through brute force but easy to do with induction.
By definition 0!=1, 1! = 1, and n! = 1*2*3*...*(n-1)*n.
Assume fac(k) is true for some arbitrary integer k > 0. Call this assumption
the Inductive Hypothesis. Thus,
fac(k), which is defined as fac(k-1) * k, must be 1*2*3*...*(k-1)*k.
Now show fac(k-1) is true. Call this the Inductive Step.
By the inductive hypothesis, fac(k-1) = 1*2*3*...*(k-1).
Thus, fac(k-1) holds. Now we need a starting case, call this the Basis.
The Basis is fac(0) = 1 is true. Since fac(0) is true fac(1) must be true.
Since fac(1) is true fac(2) must be true. So on and so forth.
Thus, fac(n) is true for all n.
EXAMPLE 1.
n
P(n): [ i = n(n+1)/2.
i=1
Basis Step. P(1) = 1(2)/2 = 1 is true.
Inductive Hypothesis. Assume P(k) is true.
k
P(k): [ i = k(k+1)/2. // assume the closed form is true for the
i=1 // summation over k
Inductive Step. Given P(k), show true for P(k+1).
k+1
P(k+1): [ i = (k+1)(k+2)/2 // show that the closed form for the
i=1 // summation over k+1 is (k+1)(k+2)/2
Break up the summation so you can pull out P(k), the inductive hypothesis.
Why do this? Because since you are assuming P(k) you can use what you already
know to show true for P(k+1). Pull out the last term of the summation, which
is (k+1).
k
P(k+1) = [ i + (k+1)
i=1
The summation is P(k):
k
[ i // this is P(k)
i=1
Since we assume P(k) is true, replace the summation with the closed form and
we are left with:
P(k+1) = k(k+1)/2 + (k+1)
Simplify:
= (k^2 + k)/2 + 2(k+1)/2
= (k^2 + k + 2k + 2)/2
= (k^2 + 3k + 2)/2
= (k+1)(k+2)/2. qed.
EXAMPLE 2.
Use mathematical induction to prove the inequality
P(n): 2^n < n!, for n >= 4.
Basis Step. P(4), 2^4 < 4! is true. (16 < 24)
Inductive Hypothesis. Assume P(k) is true:
P(k): 2^k < k!
Inductive Step. Given P(k), show true for P(k+1).
P(k+1): 2^(k+1) < (k+1)! <== show this is true
Express P(k+1) in terms of the inductive hypothesis:
P(k+1): (2^k)(2) < (k!)(k+1)
By the inductive hypothesis we know 2^k < k!, so we can remove these terms
from the inequality:
2 < k+1
Since k >= 4, shown true.
EXAMPLE 3.
Find the sum of the first n odd numbers:
1 + 3 + 5 + ... + (2n-1)
Examine a few cases:
P(3) = 1 + 3 + 5 = 9
P(4) = 1 + 3 + 5 + 7 = 16
P(5) = 1 + 3 + 5 + 7 + 9 = 25
n
It looks like P(n): [ 2i-1 = n^2.
i=1
Use induction to prove P(n).
Basis Step. P(1) is 1 = 1.
Inductive Hypothesis. Assume P(k) is true:
k
P(k): [ 2i-1 = k^2
i=1
Inductive Step. Show P(k+1) is true.
k+1
P(k+1): [ 2i-1 = (k+1)^2
i=1
Express P(k+1) in terms of the inductive hypothesis:
k
[ 2i-1 + (2(k+1)-1)
i=1
= k^2 + (2k + 2 - 1)
= k^2 + 2k + 1
= (k+1)(k+1)
= (k+1)^2.
EXAMPLE 4.
P: n^2 > 2n + 1, for n >= 5.
Basis Step. P(5) = 25 > 11.
Inductive Hypothesis: Assume P(k) is true:
P(k): k^2 > 2k + 1
Inductive Step: Show true for P(k+1):
P(k+1): (k+1)^2 > 2(k+1) + 1
Express P(k+1) in terms of P(k):
k^2(k) > 2(k+1) + 1
= k^2(k) > 2k+2 + 1
= k^2(k) > 2k+3
= k^2(k) > (2k+1) + 2
By the inductive hypothesis we know k^2 > 2k + 1, thus remove:
k > 2
Since k must be >= 5, true.
EXAMPLE 5.
n-1
Prove P(n): [ 2^i = 2^n - 1, n > 0.
i=0
4
Test. P(5): [ 2^i = 1 + 2 + 4 + 8 + 16 = 31 = 2^5 - 1. Appears true.
i=0
Basis: P(1) = (2^0) = (2^1 - 1) = 1. true.
Inductive Hypothesis: Assume true for P(k).
P(k): 2^0 + 2^1 + 2^2 + ... + 2^(k-1) = 2^k - 1
Inductive Step: Show true for P(k+1):
P(k+1): 2^(k+1) - 1
Expressed as a summation, P(k+1) = 2^0 + 2^1 + ... + 2^(k-1) + 2^k
Replace with P(k) = 2^k - 1 + 2^k
= 2^(k+1) - 1. qed.
EXAMPLE 6.
The recursive definition below defines the number of comparisons made by
mergesort on a list of size n, for n=2^k and k >= 0. The total comparisons
is the number of comparisons made to sort the left half (size n/2) plus the
comparisions to sort the right half (size n/2) plus n/2, which is the number
of comparisons needed to merge the sorted two halves. A recursive definition
is thus:
C(n) = C(n/2) + C(n/2) + n/2, where C(1) = 0.
What is the closed form formula? Try a few lists until we see a pattern. Set
n to a power of 2 to make the math easier.
k n C(n) closed formula f(n)
0 1 0 (1/2)lg1 = 0.
1 2 0 + 0 + 1 = 1 (2/2)lg2 = 1*1 = 1
2 4 1 + 1 + 2 = 4 (4/2)lg4 = 2*2 = 4
3 8 4 + 4 + 4 = 12 (8/2)lg8 = 4*3 = 12
4 16 12 + 12 + 8 = 32 (16/2)lg16 = 8*4 = 32.
The closed form f(n) appears to be
f(n) = (n/2)lgn, n >= 1.
Since we are only using powers of 2 for n we are applying induction over k,
for k >= 0. The recursive definition in terms of k is:
C(2^k) = C((2^k)/2) + C((2^k)/2) + (2^k)/2.
= C((2^(k-1)) + C((2^(k-1)) + 2^(k-1).
= 2(C(2^(k-1)) + 2^(k-1), where C(2^0) = 0.
Replacing n with 2^k in our closed form formula we have:
f(2^k) = ((2^k)/2)lg(2^k)
= 2^(k-1)(lg 2^k)
= 2^(k-1)*k, k >= 0.
Let Proposition P(k) be C(2^k) = f(2^k). P(k) is thus:
2(C(2^(k-1)) + 2^(k-1) = 2^(k-1)*k, for k >= 0 and C(2^0) = 0.
PROOF.
Basis. P(k=0). By definition C(2^0) = 0. f(2^0) = 2^(-1)*0 = 0. check.
IH. Assume P(k) true for some arbitrary k > 0:
C(2^k) = 2^(k-1)*k.
IS. Show P(k+1): C(2^(k+1)) = (2^k)(k+1).
Express P(k+1) by its recursive definition:
C(2^(k+1)) = 2(C(2^k)) + 2^k
Replace C(2^k) with our assumption from the IH, which is C(2^k) = 2^(k-1)*k:
C(2^(k+1)) = 2(C(2^k)) + 2^k
= 2(2^(k-1)*k) + 2^k.
= (2^k)*k + 2^k.
= (2^k)(k+1). bingo.
Now we need to express C(2^k) in terms of n, where n=2^k. Note that if
n=2^k then k=lgn.
C(2^k) = 2^(k-1)*k.
= ((2^k)/2)*k.
= (n/2)lgn. QED.
=============================================================================
*Alternative Forms of Induction*
Standard induction is over the set of N where the basis is P(0):
P(0) ^ [(P(k) -> P(k+1)] -> P(n), for an arbitrary k in N and for all n in N.
An alternative form of standard induction is to use an integer other than
zero as a basis. For example over the set of Z+ the basis is P(1):
P(1) ^ [(P(k) -> P(k+1)] -> P(n), for an arbitrary k in N and for all n in N.
///// More Standard Induction Problems
1. Assume you have a list of size n = 2^k (a power of 2). For each recursive
call of binary search, the list is divided exactly in half and the key is
either found or not found when the list is reduced to size 1.
The number of comparisons required in a successful or unsuccessful search
key is the number of times it takes to reduce the list to 1 or 1 + the
number of comparisons required for a list of size n/2. Thus, a list of size
1 requires 1 comparison and a list size 16 requires 4, which is 1 + the
number of comparisons for a list of size 8.
n k n/2 comparisons pattern
16 4 8 4+1=5 lg(16)+1 = 5
8 3 4 3+1=4 lg(8)+1 = 4
4 2 2 2+1=3 lg(4)+1 = 3
2 1 1 1+1=2 lg(2)+1 = 2
1 0 stop 1 lg(1)+1 = 1
Based on the pattern, it appears that the comparison count for a list of
size n (where n is 2^k for some k) is lg(n)+1.
Use induction on k to show that the closed formula for the number
of comparisons (lg 2^k) + 1:
C(2^k): (lg 2^k) + 1, for k >= 0.
Basis: for k=0, n=1, thus 1 comparison; lg 1 + 1 = 0 + 1 =1; 1 = 1; true
IH: Assume true for j:
C(2^j): lg 2^j + 1, for j from 0 to j-1
IS: Show true for j + 1:
C(2^(j+1)): lg 2^(j+1) + 1
By the definition of the algorithm:
C(2^(j+1)) = 1 + C(2^(j+1)/2)
= 1 + C(2^j)
= 1 + lg 2^j + 1 // By IH, replace C(2^j)
= lg 2*2^j + 1 // Replace 1 + lg 2^j with lg 2*2^j
= lg 2^(j+1) + 1.
2. The number of moves for n disks in the Towers of Hanoi problem can be
recursively explained as follows: Move n-1 disks from the starting tower
to the middle tower. Move the largest disk from the first tower to the final
tower. Move n-1 disks from the middle tower to the final tower. This
requires however many moves it took to move (n-1) disks doubled plus 1 move.
We can thus define a recursive function M(n) that returns the number of
moves for n disks as follows:
M(n) = 2M(n-1)+1. M(1) = 1.
This is a recursive definition. Use induction on the number of disks to
show that the closed form formula to generate M(n) = 2^n - 1. How did
we come up with this? Assuming we accept the recursive definition, we
trace the moves in the problem for small n until we see a pattern:
M(1) = 1.
M(2) = 1+1+1 = 3.
M(3) = 3+3+1 = 7.
M(4) = 7+7+1 = 15.
It *looks* like M(n) = 2^n - 1. We can *prove* it with induction.
The problem expressed mathematically is shown below:
Definition: M(1)=1. M(n) = 2M(n-1) + 1.
Show M(n) = 2^n - 1. // prove the closed form formula
Basis.
M(1) = 1. 2*0+1=1. 2^1 - 1 = 1. check.
IH. Assume M(k) is true.
M(k) = 2^(k-1) - 1.
IS. Show true for M(k+1).
M(k+1) = 2^(k+1) - 1. // show this is true
By definition M(k+1) = 2M(k) + 1.
By IH, M(k) takes 2^k - 1 moves. Plug this into the expression for M(k+1).
M(k+1) = 2M(k) + 1.
= (2^k - 1)(2^k - 1) + 1.
= 2(2^k - 1) + 1.
= (2^(k+1) - 2) + 1
= 2^(k+1) - 1. qed.