Strong Induction

Download as PDF

Ever feel like you need more than just the last step to solve a puzzle? Strong induction is a powerful proof technique that lets you use the truth of *all* previous steps, not just one, to build your argument. It's like having a whole team of dominoes to help knock over the next one!

What Is Strong Mathematical Induction?

Strong mathematical induction is a method of mathematical proof used to establish that a given statement is true for all natural numbers (or all integers from a certain starting point). It is a variation of standard mathematical induction where the assumption made—the inductive hypothesis—is more powerful. Instead of just assuming the statement is true for the previous case, we assume it is true for all previous cases.

Imagine you have a line of dominoes. In standard induction, to prove domino `k+1` will fall, you only assume that domino `k` (the one right before it) will fall. In strong induction, you get to assume that all the dominoes from the first one up to domino `k` have fallen. This stronger assumption can make certain proofs much easier to construct.

Why Is It Called 'Strong' Induction?

The name "strong induction" comes directly from the nature of its core assumption, the inductive hypothesis. It's considered "stronger" because you are assuming more than you do in standard (or "weak") induction.

Weak Induction Hypothesis: Assume the statement P(n) is true for a single case, $n = k$ .
Strong Induction Hypothesis: Assume the statement P(n) is true for all cases from the start up to $n = k$ .

Think of it like climbing. Weak induction is like climbing a ladder. To get to rung $k + 1$ , you really only need to be standing on rung $k$ . Strong induction is more like rock climbing. To get to the next handhold at position $k + 1$ , you can use any of the handholds you've already passed, from the very first one up to $k$ . Having more options and a stronger foundation can make the next move possible, even when the immediately preceding handhold isn't helpful.

Paradoxically, making a "stronger" assumption often makes the proof itself easier to write, because you have more information to work with in your inductive step.

How Do You Write a Strong Induction Proof?

A proof by strong induction follows a structure similar to standard induction but with key differences in the hypothesis and often the base case. Here are the essential steps to prove a statement $P (n)$ is true for all integers $n \geq n_{0}$ .

The Base Case(s): First, prove that the statement is true for the starting value, $n_{0}$ . For strong induction, you sometimes need to prove the statement for several initial values (e.g., $P (n_{0}), P (n_{0} + 1), \dots$ ). This is necessary if your inductive step needs to "reach back" more than one step. You must establish a firm foundation of cases to ensure the logic never tries to reference a case that hasn't been proven.
The Inductive Hypothesis: This is the crucial difference. You assume that the statement $P (j)$ is true for all integers $j$ in the range from your starting point $n_{0}$ up to some arbitrary integer $k$ . We assume $P (n_{0}), P (n_{0} + 1), \dots, P (k)$ are all true.
Assume $P (j)$ is true for all integers $j$ such that $n_{0} \leq j \leq k$ .
The Inductive Step: In this final step, your goal is to prove that the statement must also be true for the next integer, $k + 1$ . You must show that the truth of the previous cases (your inductive hypothesis) logically guarantees the truth of $P (k + 1)$ . Because you assumed $P (j)$ is true for all values up to $k$ , you can use any of them (e.g., $P (k)$ , $P (k - 1)$ , or even $P (k / 2)$ ) to help you prove $P (k + 1)$ .

Worked Example: The Postage Stamp Problem

Example 1

Prove that any amount of postage of 12 cents or more can be formed using only 4-cent and 5-cent stamps.

Statement: For any integer $n \geq 12$ , $P (n)$ is the statement " $n$ cents of postage can be formed using 4-cent and 5-cent stamps."

1. Base Cases:

Our inductive step will involve reaching back 4 cents. To show we can make $k + 1$ cents, we will assume we can make $(k + 1) - 4 = k - 3$ cents and just add a 4-cent stamp. For this logic to be sound, we need to ensure that $k - 3$ is always an amount we've already proven. If we want to prove this for $k + 1 = 16$ , we need to know the case for $13$ . If we want to prove for $15$ , we need to know $12$ . So, we need to establish the first four consecutive cases starting from 12.

$P (12)$ : $12 = 3 \times 4$ . True.
$P (13)$ : $13 = 2 \times 4 + 1 \times 5$ . True.
$P (14)$ : $14 = 1 \times 4 + 2 \times 5$ . True.
$P (15)$ : $15 = 3 \times 5$ . True.

2. Inductive Hypothesis:

Assume that for some integer $k \geq 15$ , the statement $P (j)$ is true for all integers $j$ where $12 \leq j \leq k$ . This means we assume we can make any postage amount from 12 cents up to $k$ cents.

3. Inductive Step:

We want to prove that $P (k + 1)$ is true. That is, we want to show we can form $k + 1$ cents of postage. Our goal is to form $k + 1$ cents by adding either a 4-cent or 5-cent stamp to a smaller amount we already know how to make.

Consider the amount $(k + 1) - 4$ , which simplifies to $k - 3$ . Since we assumed $k \geq 15$ , we know that $k - 3 \geq 12$ . Therefore, the amount $k - 3$ is within the range of our inductive hypothesis (from 12 to $k$ ).

By our strong hypothesis, $P (k - 3)$ is true. This means we know how to make $k - 3$ cents using 4-cent and 5-cent stamps. To get $k + 1$ cents, we can simply take the combination for $k - 3$ cents and add one more 4-cent stamp.

$(combination for k - 3 cents) + 4 cents = (k - 3) + 4 = k + 1 cents$

Thus, we have successfully formed $k + 1$ cents. Since we have established our base cases and proven that if the statement holds for all values up to $k$ , it must also hold for $k + 1$ , we conclude by strong induction that the statement is true for all integers $n \geq 12$ .

Worked Example: The Fundamental Theorem of Arithmetic

Example 2

Prove that every integer $n > 1$ is either a prime number or a product of prime numbers.

Statement: For any integer $n > 1$ , $P (n)$ is the statement " $n$ is a prime number or a product of prime numbers."

1. Base Case:

The smallest integer greater than 1 is 2. So, our base case is $n = 2$ . The number 2 is a prime number, so the statement $P (2)$ is true.

2. Inductive Hypothesis:

Assume that for some integer $k \geq 2$ , the statement $P (j)$ is true for all integers $j$ where $2 \leq j \leq k$ . This means we assume every integer from 2 up to $k$ is either prime or a product of primes.

3. Inductive Step:

We want to prove that $P (k + 1)$ is true. We must show that the integer $k + 1$ is either prime or a product of primes. There are two possibilities for any integer greater than 1:

Case 1: $k + 1$ is a prime number.
If $k + 1$ is prime, then the statement $P (k + 1)$ is true by definition. We are done for this case.
Case 2: $k + 1$ is a composite number.
If $k + 1$ is composite, then it can be factored into two smaller integers, $a$ and $b$ , such that $k + 1 = a \times b$ . By the definition of a composite number, we know that $1 < a < k + 1$ and $1 < b < k + 1$ . This means that $2 \leq a \leq k$ and $2 \leq b \leq k$ .

Both integers $a$ and $b$ fall within the range of our strong inductive hypothesis! Therefore, we know that $P (a)$ is true and $P (b)$ is true. This means that $a$ is either prime or a product of primes, and $b$ is also either prime or a product of primes.

Since $k + 1$ is the product of $a$ and $b$ , $k + 1$ must be a product of primes. For example, if $a$ is a product of primes and $b$ is prime, their product $a \times b$ is also a product of primes. Thus, $P (k + 1)$ is true in this case as well.

Because $P (k + 1)$ holds in both possible cases, we conclude by strong induction that every integer $n > 1$ is either prime or a product of primes.

Worked Example: Solving a Recurrence Relation

Example 3

A sequence is defined by $a_{0} = 1$ , $a_{1} = 8$ , and for $n \geq 2$ , $a_{n} = a_{n - 1} + 2 a_{n - 2}$ . Prove that the closed-form formula for this sequence is $a_{n} = 3 \cdot 2^{n} - 2 (- 1)^{n}$ .

Statement: For any integer $n \geq 0$ , $P (n)$ is the statement $a_{n} = 3 \cdot 2^{n} - 2 (- 1)^{n}$ .

1. Base Cases:

The recurrence relation for $a_{n}$ depends on two previous terms ( $a_{n - 1}$ and $a_{n - 2}$ ). This tells us we will need at least two base cases to ensure our inductive step is always valid.

$P (0)$ : The definition gives $a_{0} = 1$ . The formula gives $3 \cdot 2^{0} - 2 (- 1)^{0} = 3 \cdot 1 - 2 \cdot 1 = 1$ . True.
$P (1)$ : The definition gives $a_{1} = 8$ . The formula gives $3 \cdot 2^{1} - 2 (- 1)^{1} = 3 \cdot 2 - 2 (- 1) = 6 + 2 = 8$ . True.

2. Inductive Hypothesis:

Assume that for some integer $k \geq 1$ , the statement $P (j)$ is true for all integers $j$ where $0 \leq j \leq k$ . This means we assume $a_{j} = 3 \cdot 2^{j} - 2 (- 1)^{j}$ for all $j$ from 0 to $k$ .

3. Inductive Step:

We want to prove that $P (k + 1)$ is true, meaning $a_{k + 1} = 3 \cdot 2^{k + 1} - 2 (- 1)^{k + 1}$ . We start with the definition of $a_{k + 1}$ for $k + 1 \geq 2$ (our assumption $k \geq 1$ ensures this).

a_{k + 1} = a_{k} + 2 a_{k - 1}

Since both $k$ and $k - 1$ are in the range $0 \leq j \leq k$ , we can use our strong inductive hypothesis to substitute the formula for both $a_{k}$ and $a_{k - 1}$ :

a_{k + 1} = (3 \cdot 2^{k} - 2 (- 1)^{k}) + 2 (3 \cdot 2^{k - 1} - 2 (- 1)^{k - 1})

Now, we simplify the expression and rearrange the terms to group powers of 2 and powers of -1.

a_{k + 1} = 3 \cdot 2^{k} - 2 (- 1)^{k} + 6 \cdot 2^{k - 1} - 4 (- 1)^{k - 1}

a_{k + 1} = (3 \cdot 2^{k} + 3 \cdot 2 \cdot 2^{k - 1}) - (2 (- 1)^{k} + 4 (- 1)^{k - 1})

a_{k + 1} = (3 \cdot 2^{k} + 3 \cdot 2^{k}) - (2 (- 1)^{k} + 4 (- 1)^{k - 1})

Let's simplify each part. The first part is:

3 \cdot 2^{k} + 3 \cdot 2^{k} = 2 \cdot (3 \cdot 2^{k}) = 3 \cdot 2^{k + 1}

The second part is a bit trickier. Let's factor out $- 2$ :

- (2 (- 1)^{k} + 4 (- 1)^{k - 1}) = - 2 [(- 1)^{k} + 2 (- 1)^{k - 1}]

Now, let's rewrite $(- 1)^{k}$ as $(- 1) (- 1)^{k - 1}$ :

- 2 [(- 1) (- 1)^{k - 1} + 2 (- 1)^{k - 1}] = - 2 [(- 1 + 2) (- 1)^{k - 1}] = - 2 [1 \cdot (- 1)^{k - 1}] = - 2 (- 1)^{k - 1}

This is where it gets subtle. We want the final term to be $- 2 (- 1)^{k + 1}$ . Is $- 2 (- 1)^{k - 1}$ the same? Yes! Since the exponents $k - 1$ and $k + 1$ differ by an even number (2), the sign of $(- 1)$ raised to these powers is identical. So, $(- 1)^{k - 1} = (- 1)^{k + 1}$ .

Putting it all together:

a_{k + 1} = 3 \cdot 2^{k + 1} - 2 (- 1)^{k + 1}

This is exactly the formula for $P (k + 1)$ . We have shown that if the formula works for all cases up to $k$ , it must work for $k + 1$ . Thus, the formula is correct for all $n \geq 0$ .

Strong vs. Weak Induction: Which One Should You Use?

Deciding between strong and weak induction depends entirely on what you need to prove the inductive step. The key question to ask is: "To prove the statement for $k + 1$ , do I only need to know it's true for $k$ , or do I need to know about other, earlier cases?"

Here is a table summarizing the differences:

Feature	Weak (Standard) Induction	Strong Induction
Base Case	Prove $P (n_{0})$ is true.	Prove $P (n_{0})$ is true (and possibly $P (n_{0} + 1), \dots$ if needed).
Inductive Hypothesis	Assume $P (k)$ is true for one specific $k$ .	Assume $P (j)$ is true for all $j$ from $n_{0}$ to $k$ .
When to Use	When $P (k + 1)$ follows directly from $P (k)$ .	When proving $P (k + 1)$ requires knowing the truth of cases earlier than $k$ .
Typical Problems	Summation formulas (e.g., $\sum_{i = 1}^{n} i$ ), simple divisibility rules.	Recurrence relations (like Example 3), prime factorization (Example 2), postage/coin problems (Example 1), game theory.

It's important to know that strong induction is, in a formal sense, no more powerful than weak induction. Any proof written with strong induction can be converted into a weak induction proof. However, for many problems, using strong induction is far more direct, natural, and intuitive.

What Are the Common Mistakes in Strong Induction Proofs?

Strong induction is a powerful tool, but it's easy to make small mistakes that can invalidate a proof. Here are some common pitfalls to watch out for:

Insufficient Base Cases. This is the most frequent error. If your inductive step for $P (k + 1)$ relies on, for instance, $P (k - 4)$ , you must manually prove enough base cases to ensure that $k - 4$ is always in a range you've proven. In the postage stamp example, we needed four base cases (12, 13, 14, 15) so that when we proved $P (16)$ , our argument could rely on $P (12)$ , which we had already shown was true.
Incorrect Inductive Hypothesis. A common mistake is to state the weak hypothesis (assuming only $P (k)$ ) but then use the strong hypothesis in the proof (by referencing, say, $P (k - 1)$ ). Always be precise: state that you are assuming the property holds for all integers from the base case up to $k$ .
A Gap in Logic. Ensure your inductive step covers all possibilities. In the prime factorization proof, we had to consider two separate cases: $k + 1$ being prime and $k + 1$ being composite. If we had only handled the composite case, the proof would be incomplete.
Circular Reasoning. Be careful not to assume $P (k + 1)$ in your attempt to prove $P (k + 1)$ . The goal is to use the truth of $P (j)$ for $j \leq k$ to derive the truth of $P (k + 1)$ from scratch.

Strong Induction: A Quick Reference

Here is a quick summary of the process for proving a statement $P (n)$ for all $n \geq n_{0}$ using strong induction.

1. Identify the Statement $P (n)$ . Clearly define what you are trying to prove for a given $n$ .
2. Prove the Base Case(s). Show $P (n_{0})$ is true. Check if your inductive logic will require more than one base case, and prove them if necessary.
3. State the Strong Inductive Hypothesis. Write down your assumption clearly: "Assume $P (j)$ is true for all integers $j$ such that $n_{0} \leq j \leq k$ for some arbitrary integer $k \geq n_{0}$ ."
4. Prove the Inductive Step. Your goal is to prove $P (k + 1)$ . Start with one side of the statement for $k + 1$ and use the inductive hypothesis to manipulate it until you arrive at the other side. You are allowed to use the fact that $P (j)$ is true for any value of $j$ between $n_{0}$ and $k$ .
5. Conclude. Finish your proof with a concluding sentence, such as, "By the principle of strong induction, the statement is true for all $n \geq n_{0}$ ."

Frequently Asked Questions

What's the main difference between strong and regular induction?

The main difference is the assumption you make. In regular (weak) induction, you only assume the statement is true for the single previous case, $k$ . In strong induction, you assume the statement is true for all cases from the beginning up to $k$ .

Do I always need more than one base case for strong induction?

Not always, but it's common. You need enough base cases to ensure your inductive step is always valid. If your proof for $P (k + 1)$ relies on $P (k - 3)$ , you need to establish enough initial cases so that $k - 3$ is always in the range you've proven or assumed.

Is strong induction actually more powerful than weak induction?

Logically, they are equivalent; any proof done with one can be technically rewritten for the other. However, in practice, strong induction is a much more natural and easier tool for problems where the next step depends on more than just the immediately preceding one.

Can I use strong induction on a problem I can solve with weak induction?

Yes, absolutely! Using a strong induction hypothesis where a weak one would suffice is perfectly valid. It just means you made a stronger assumption than you actually needed to use in your proof.

Why is the base case so important?

The base case is the anchor for your entire proof. It's the first domino that you knock over by hand. Without a true base case, the inductive step has nothing to build upon, and the entire chain of logic fails.

Where is strong induction used outside of math class?

It's a fundamental concept in computer science, especially for proving that algorithms are correct (e.g., recursive algorithms). It's also used in game theory to analyze strategies and in proving properties of complex systems.

What does 'inductive hypothesis' mean?

The inductive hypothesis is the key assumption you make in the proof. It's the 'let's pretend this is true for previous cases' step. You assume the statement holds for cases up to $k$ in order to show that it must then hold for the next case, $k + 1$ .