Having seen how standard mathematical induction works, we now explore a variant known as Strong Induction.
Second Principle of Finite Induction
Let \(S\) be a set of positive integers with the following properties:
The integer 1 belongs to the set.
Whenever the integers \( 1, 2, \ldots k \) are in \(S\), then the next integer \(k+1\) must also be in \(S\).
Then \(S\) is the set of all positive integers.
Similar to the first principle of finite induction, this statement seems obvious. The corresponding analogy is that if the weight of all of the initial dominos is strong enough to push down the next domino, then all dominos in this sequence must eventually fall. Of course, standard Mathematical Induction can be considered a special case of Strong Induction.
Let's work through several examples, to see why we sometimes need all of the initial dominos, instead of just one preceding domino.
1. [Fundamental Theorem of Arithmetic] Every integer \(n\geq 2\) can be written as the product of prime numbers.
Proof: Base case: This is clearly true for \(n=2 \).
Induction step: Suppose the statement is true for \(n = 2, 3, \ldots k \).
If \(k+1\) is prime, then we are done.
Otherwise, \(k+1\) has a smallest prime factor, which we denote by \(p\). Let \(k+1= p \times N\). By Strong induction, \(N\) can be written as the product of prime numbers. Hence, so can \(k+1=p \times N\).
Note: This expression is unique up to the ordering of the primes. Since Induction is generally an 'existence' proof, it often is unable to show uniqueness. Instead, an alternative approach is required.
2. Throughout the world (with slight exceptions), McDonalds sells Chicken McNuggets in 4, 6, 9 and 20 piece boxes. Show that for any integer \(N \geq 24\), we can always obtain exactly \(N\) McNuggets by buying several boxes.
Proof: Base Case: This is clearly true for \( N = 24 = 4 \times 6 \), \(N = 25 = 4\times 4 + 9 \times 1\), \( N = 26 = 4 \times 2 + 9 \times 2 \) and \(N = 27 = 9 \times 3 \).
Induction step: Suppose the statement is true for \( n = k, k-1, k-2, k-3 \).
Then it is true for \( k-3 + 4 \), since we can buy \(k-3\) McNuggets, together with another box of 4 McNuggets.
Note: This approach of inducting on several base cases is also known as the Third Principle of Mathematical Induction.