Strong Induction

What is Strong Induction?

In regular induction, to prove step 5, you can only use step 4.

In strong induction, to prove step 5, you can use all previous steps: 1, 2, 3, and 4.

When Do You Need It?

Use strong induction when proving something about $n$ requires information about values other than $n-1$.

Example 1: Breaking a Chocolate Bar

You have a chocolate bar made of $n$ squares.

You want to break it into individual squares.

Each break splits one piece into two pieces.

Claim: You need exactly $n - 1$ breaks to separate all $n$ squares.

Check by hand:

The Proof:

Base case ($n = 1$):

• One square — already separated
• Zero breaks needed
• Formula: $1 - 1 = 0$

First domino falls.

Inductive step:

Assume the formula works for all bars smaller than $n$.

Consider a bar of $n$ squares:

1. Make the first break
2. This gives two pieces — call their sizes $a$ and $b$
3. We know: $a + b = n$, and both $a$ and $b$ are smaller than $n$

By our assumption:

• The piece with $a$ squares needs $a - 1$ breaks
• The piece with $b$ squares needs $b - 1$ breaks

$1$ break to split the bar into two pieces.

$(a - 1)$ breaks for the left piece.

$(b - 1)$ breaks for the right piece.

Total breaks:

Exactly what the formula predicts.

If domino $k$ falls, domino $k+1$ falls.

Example 2: Prime Factorization

Every integer can be broken down into prime numbers.

Claim: Every integer $n \geq 2$ can be written as a product of primes.

The Proof:

Base case ($n = 2$):

• $2$ is prime
• A prime by itself counts as a “product of primes”

The claim holds for $n = 2$.

Inductive step:

Assume the claim is true for all integers from $2$ to $n-1$.

Now we prove it for $n$.

Case 1: $n$ is prime.

Then $n$ is already a product of primes (itself). Done.

Case 2: $n$ is not prime.

Then $n$ can be written as:

$n = a \times b$

where $2 \leq a < n$ and $2 \leq b < n$.

By our assumption:

$a = p_1 \times p_2 \times \ldots \times p_j \quad \text{(product of primes)}$

$b = q_1 \times q_2 \times \ldots \times q_k \quad \text{(product of primes)}$

Therefore:

$n = a \times b = p_1 \times p_2 \times \ldots \times p_j \times q_1 \times q_2 \times \ldots \times q_k$

This is a product of primes.

If it works for all smaller numbers, it works for $n$.

Example 3: Climbing Stairs

You want to climb a staircase with $n$ steps.

Each move, you can go up 1 step or 2 steps.

Question: How many different ways can you reach the top?

The formula:

$W_n = W_{n-1} + W_{n-2}$

Why Do These Need Strong Induction?

In all three examples, proving something about $n$ required more than just $n-1$.

Chocolate bar:

• Breaking a 5-square bar might give pieces of size $2$ and $3$
• We needed the formula for both $2$ and $3$ — not just $4$

Prime factorization:

• Factoring $12$ gives $3 \times 4$
• We needed the theorem for both $3$ and $4$ — not just $11$

Climbing stairs:

• Finding $W_5$ requires $W_4$ and $W_3$
• Regular induction only gives $W_4$ — we wouldn’t know $W_3$

The pattern:

When you need more than just the previous value, use strong induction.