Strong Induction

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.

Worked Examples

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.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Strong Induction

Worked Examples

1. [Fundamental Theorem of Arithmetic] Every integer n≥2n\geq 2n≥2 can be written as the product of prime numbers.

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≥24N \geq 24N≥24, we can always obtain exactly NNN McNuggets by buying several boxes.

Comments

1. [Fundamental Theorem of Arithmetic] Every integer $n\geq 2$ can be written as the product of prime numbers.

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.