# 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:

1. The integer 1 belongs to the set.

2. 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.

Note by Calvin Lin
7 years, 2 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 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"
MathAppears 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}$