Up until this point we have been discussing ordinary mathematical induction and in this post I will explain what strong mathematical induction is and how it differs from ordinary induction. Before I talk about the differences lets talk about the similarities. Both types of induction involve a basis step and an inductive step to be proved, but strong induction can involve multiple basis steps and each of these must be proven before moving onto the inductive step.
The other main difference between strong and ordinary induction is that since we are possibly including multiple basis steps we must define some type of statement to represent the statement of interests validity over a range of values. All of this talking in the abstract is probably kind of confusing so we will go over an example.
Given the sequence:
= 0 = 4 = 6 – 5
Prove that all the terms of the previous recurrence sequence is satisfied by the following equation:
= – 1
The first step is to prove the basis step, but this time we must prove two basis steps for the two given base values.
= – 1 = 0 (true)
= – 1 = 4 (true)
Next is our inductive step, but here is where it gets a little bit different. Strong mathematical induction supposes the truth of our inductive hypothesis for all values beginning at our lowest base case through k. This is different from ordinary mathematical induction because in that type of induction they say nothing about all values, but only values within a range for which the relation is defined. Below I will show you the difference between how the inductive hypothesis looks in either case.
Inductive Hypothesis (Ordinary Mathematical Induction)
Suppose for some arbitrarily chosen but particular k 2 the following equation is true
= – 1
Inductive Hypothesis (Strong Mathematical Induction)
Let k be some arbitrarily chosen but particular value such that k 1 and the following equation is true
= – 1 for all integers i with 0 i k
As you can see, the only difference between the two is the range over which our inductive hypothesis is valid. The strong version includes all possible values in its inductive hypothesis. The rest of the proof flows the same ways as the other type of inductive proofs.
We must next show that:
= – 1
We can use the original recurrence relation to arrive at this conclusion through some basic algebra manipulations:
= 6 – 5
= 6( – 1) – 5( – 1)
= 6 – 6 – + 5
= (6 -1) – 1
= 5 – 1
= – 1
= 6 – 5 = – 1