As I promised in the Proof by induction post, I would follow up to elaborate on the proof by induction topic. Here is part of the follow up, known as the proof by strong induction. What I covered last time, is sometimes also known as weak induction.
In weak induction the induction step goes:
Induction step: If P(k) is true then P(k+1) is true as well.
Strong induction expands the concept to:
Induction step: If P(m), P(m+1), P(m+2)… P(k) is true then P(k+1) is true as well for some k > m.
The difference between the two methods is what assumptions we need to make in the induction step. To switch to the metaphor of dominoes again – in the weak induction we need to know that the previous domino is toppled, then the next one will topple as well. In strong induction we need to know that all the previous ones has toppled before we can ensure that the next one will fall as well.
Both methods have the same logical strength when we apply them, since in order to get to the k’th domino we need to topple 1,2,3,…k-1 anyway. However, sometimes strong induction makes the proof of the induction step easier.
Strong Induction Example 1
I have shamelessly stolen this example from Hammack since I think it brilliantly shows when strong induction is better to use. But lets first see what happens if we try to use weak induction on the following:
Proposition: if , then 12|(n4 – n2)
Weak induction
Base case: we need to prove that 12|(14 – 12) = 12|(1- 1) = 0, which is divisible by 12 by definition.
Induction step: We assume that the 12|(k4 – k2) is true such that (n4 – n2) = 12a for some . We then need to show that ((k+1)4 – (k+1)2) = 12b for some .
My approach would be to a direct proof such that
(k+1)4 – (k+1)2 = k4 + 4k3 + 6k2 + 4k + 1 – (k2 + 2k + 1) = (k4 – k2) + 4k3 + 6k2 + 2k = 12a + 4k3 + 6k2 + 2k
How do we proceed from there? I don’t have a clue. If you can show me how to continue of this road I would be glad to hear it.
Strong induction
The weak induction method failed. However, we can show that n = k-5 implies that the statement is true for k+1, so we need to expand the base case to include everything up to n = 6.
Base case:
n = 1: 12|(14 – 12) = 12|(1- 1) = 0 = 012
n = 2: 12|(24 – 22) = 12|16-12 = 12 = 112
n = 3: 12|(34 – 32) = 12|(81 – 9) = 72 = 612
n = 4: 12|(44 – 42) = 12|(256- 16) = 240 = 20 * 12
n = 5: 12|(54 – 52) = 12|(625- 25) = 600 = 5012
n = 6: 12|(64 – 62) = 12|(1296- 36) = 1260 = 105*12
So far it fits really well.
Induction step: let and assume that 12|(m4 – m2) for , now we need to prove that 12|((k+1)4 – (k+1)2) is true as well.
Let us define l = k-5 for which we assume the proposition to be true such that (l4 -l2) = 12a for some value of a. We need to show that 12|((l+6)4 – (l+6)2) is true. So let us try with a direct approach
(l+6)4 – (l+6)2= (l4 +24l3 + 180l2 + 864l + 1296) – (l2 + 12l + 36) = (l4 – l2) +24l3 + 180l2 + 852l + 1260 = 12a +12(2l3 + 15l2 + 71l + 105).
This statement is clearly divisible by 12, and thus proofs the proposition.
QED
So in order to prove it for n = k+1 = 7 we need n = k-5 = 1 to prove it, but that is handled in the base case, same goes for all the n = 8,9,10,11,12 and then we start to rely on the fact that we can prove n= 8 through the induction step.
Image Credits
The metaphor of dominoes also gave rise to the chosen post photo, which was kindly shared under the creative common license by Malkav. My crop of the photo is of course shared under the same conditions.