Module 10: Strong Induction Proofs

Strong Induction

Induction proofs are more powerful than they may first appear. In earlier examples, we often saw induction used to prove that if a statement is true for one value, say n-1, then it is true for the next, n. That is called weak induction. But this is just one way to apply induction; in fact, induction works for any smaller value, not just the one immediately before.

In strong induction, the inductive hypothesis assumes that the statement is true for all values less than n, and then uses that to prove it is also true for n. This means we're not limited to proving P(n-1) → P(n); we can prove P(k) → P(n) for any value of k that is strictly less than n.

We are also allowed to use more than one of those earlier values at the same time. If the inductive step requires using P(n - 1), P(n - 2), or even P(n/2), we're free to do so, as long as all of those values are strictly smaller than n and within the range of values we've already proved (either by base cases or by induction).

This flexibility is what makes strong induction so useful. It allows us to tackle problems where each new case depends on several earlier ones, not just the one immediately before it.

Proving ∀n ∈ ℤ+, P(n)
1. Prove P(1), P(2), ..., P(a) are true
2. Prove ∀n ∈ ℤ+, P(k) → P(n), where k < n:
    2a. Assume P(k) is true for any k < n
    2b. Prove P(n) is true

Any integer greater than 1 is divisible by a prime number.

Proof:

Base Case:
P(n=2) is true: 2 is divisible by 2, which is prime

Induction Hypothesis:
Assume any integer k < n is divisible by a prime number

Induction Step:
Consider an unspecified integer n > 1

Case 1: n is prime
Since n is prime and all numbers are divisible by themselves, n is divisible by a prime number.

Case 2: n is not prime
Since n is not prime, then there are two integers, a and b, such that n = a*b, such that 1 < a < n and 1 < b < n.
Since a < n, by IH a is divisible by a prime.
Since a is a factor of n, and a is divisible by a prime, then n is also divisible by a prime.

Therefore, by mathematical induction, any integer greater than 1 is divisible by a prime number.

◼

In this proof, we use two cases to simplify our reasoning. Case analysis is a flexible tool in mathematics; it can be used in any part of a proof, including within the inductive step. Here, we divide our proof into two cases: when n is prime and when n is not prime. We chose these cases because one is straightforward, and the other naturally leads us to apply a known definition.

When n is not prime (that is, composite), we can use the definition of a composite number. This definition tells us that n can be written as the product of two integers, a and b, both strictly less than n. This condition is key because it allows us to apply the inductive hypothesis (IH) to both a and b, since the IH applies to all integers smaller than n.

Even though in this particular proof we only need to use the IH once, it's perfectly valid to apply it multiple times if the situation requires it. The important point is that we don't need to know the exact values of a and b; it's enough to know that they are both smaller than n. That alone gives us permission to apply the IH and complete the reasoning.

This strategy of splitting the proof into cases and using the structure of known definitions helps us break the problem into manageable parts and apply inductive reasoning effectively.

In weak induction, the difference between the inductive hypothesis (IH) and the inductive step (IS) is always 1. For example, assuming the statement holds for n and proving it for n + 1, or assuming it holds for n − 1 and proving it for n.

In strong induction, however, the inductive hypothesis assumes the statement holds for all numbers smaller than n, and the inductive step proves it for n. Alternatively, you can assume it holds for all numbers less than or equal to n in the IH and then prove it for n + 1 in the IS.

Sequence of Implication

We can think of an induction proof as building a chain of logical implications. Suppose we want to prove that a certain statement P(n) is true for all positive integers n. In a standard induction proof, we prove two things: that P(1) is true, and that if P(n − 1) is true, then P(n) is also true.

What we are really doing is showing a chain like this:

P(1) → P(2) → P(3) → P(4) → P(5) → ...

If all the implications in this chain are true, and we know that the very first statement P(1) is true, then it follows that all statements after it must also be true. For example, since P(1) is true and P(1) → P(2) is true, then P(2) must be true. So, since P(2) is true and P(2) → P(3) is true, then P(3) is true, and so on. This is why the base case is so important, it's what starts the chain, since we can have the implications being true when both the hypothesis and the conclusion are false.

Now let's consider a strong induction proof, where instead of assuming just P(n-1), we assume that several previous values are true. For example, suppose we assume that P(n − 3) is true in order to prove P(n). This changes the implication structure dramatically.

Instead of one continuous chain, we now have several parallel chains, like this:

P(1) → P(4) → P(7) → P(10) → ...
P(2) → P(5) → P(8) → P(11) → ...
P(3) → P(6) → P(9) → P(12) → ...

Each of these chains progresses by adding 3 to the previous value. But here's the key point: if we only prove P(1) in the base case, we’re only activating the first chain. The other two chains (starting with P(2) and P(3)) are still inactive. And since the implication F → F is considered logically true, those chains don't help us unless we also know their first term is true.

So, to make sure all values of n are covered in our proof, we need to include more values in the base case. In this example, we must prove P(1), P(2), and P(3) in the base case. Once all three chains are started, the implication structure guarantees that every positive integer will eventually be proven.

This is why strong induction often requires more base cases than weak induction. It depends on how far back the inductive step looks. Without the right base cases, the logic might only apply to a subset of the integers, not all of them.

Recurrence Relations

A recurrence relation is a rule that defines each term of a sequence based on one or more previous terms. To fully determine a sequence from such a rule, we also need some initial values, also known as boundary conditions, just like how a recursive function and an induction proof needs a base case.

A well-known example is the Fibonacci sequence, where each term is the sum of the two terms before it. The recurrence relation is: an = an-1 + an-2. However, to start generating values from this rule, we need to define the first two terms. For instance, we might set: a0 = 1 and a1 = 1. Without these, the rule would reference terms like a₋₁, which aren't defined.

In recurrence relations, especially those involving division, we often use floor or ceiling functions to ensure that the index remains an integer. Since dividing two integers doesn't always result in an integer. Taking the floor or ceiling of the result helps us stay within valid index positions in the sequence. This is crucial, since sequence terms are only defined for integer positions.

Consider the relation:

a1 = 0
a2 = 2
a3 = 4
an = 3a⌊n/3⌋ + 2 for integer n > 3

For any positive integer n, an is even.

Proof:

Base Case:
P(n=1) is true: a1 = 0 and 0 is even
P(n=2) is true: a2 = 2 and 2 is even
P(n=3) is true: a3 = 4 and 4 is even

Induction Hypothesis:
Assume ak is even for any k < n.

Induction Step:
Consider an unspecified integer n > 3
an = 3a⌊n/3⌋ + 2
Since ⌊n/3⌋ < n, by IH a⌊n/3⌋ is even, so a⌊n/3⌋ =2c for some integer c
Therefore, an = 3(2c) + 2 = 6k + 2 = 2(3c+1)
Since the sum and the product of integers is an integer, then b = 3c+1 is an integer
Hence, an = 2b is even

Therefore, by mathematical induction, for any positive integer n, any term of this relation is even.

◼

This recurrence clearly calls for a strong induction proof. We can tell because each term an is defined in terms of a⌊n/3⌋, meaning that to prove a statement about aₙ, we need information about smaller values, not just an-1, but potentially any value less than n.

Let's begin by examining the inductive hypothesis (IH). We assume that the statement is true for all values smaller than n. Specifically, we assume that ak is even for every integer k < n. Then, in our inductive step (IS), we use this assumption to prove that an is also even.

To do this, we first use the recurrence definition. This is an important moment to be careful about what we assume and what we’re trying to prove. In this case, we want to prove that aₙ is even, and we’re allowed to use the recurrence: aₙ = 3a⌊n/3⌋ + 2. This recurrence shows that aₙ depends on a⌊n/3⌋. Since ⌊n/3⌋ < n, the value a⌊n/3⌋ is covered by our inductive hypothesis, which means it’s even. That allows us to write a⌊n/3⌋ = 2c for some integer c and conclude that aₙ is also even after some algebraic manipulations, completing the inductive step, but only for values of n where all parts of this argument are valid.

Now let's examine the base cases, which are essential for any induction proof. We always need to start from the smallest value of n allowed by the problem; in this case, n = 1. However, we can't stop there. We need to check whether our inductive step works for each value just above the base. If it fails for any of them, we need to add that value to the base case.

Start with n = 2. If we try to use the recurrence for n = 2, we get a2 = 3a⌊2/3⌋ + 2 = 3a₀ + 2, since ⌊2/3⌋ = 0. But a0 isn't defined; our proof starts at n = 1, so this value is invalid. That means n = 2 must be included in the base case, since the inductive step doesn't apply.

Now try n = 3. Here, ⌊n/3⌋ = ⌊3/3⌋ = 1, which is valid and part of our IH. But we must also check whether the recurrence aₙ = 3⌊n/3⌋ + 2 is defined for this value. Looking at the recurrence, it seems it only applies for n > 3, not for n = 3 itself. So we must also include n = 3 in the base case.

Now try n = 4. In this case, ⌊n/3⌋ = ⌊4/3⌋ = 1, which is valid. The recurrence is also defined for n = 4, since 4 > 3. So the inductive step works from this point onward.

Therefore, our final base case needs to include n = 1, n = 2, and n = 3. Only from n = 4 forward can the inductive step be applied safely.

Although base cases are typically written before the inductive step in a formal proof, we often don't know how many are needed until we analyze the behavior of the recurrence and determine where the inductive step first becomes valid.

 

Number of Base Cases

An induction proof always has at least one base case. The smallest valid value must appear as a base case, but additional values may also be required to ensure the proof is correct. To determine which values are needed, you must first complete the inductive step and then check whether all the values used in your inductive hypothesis are valid.

For example, suppose you are proving P(n) for all positive integers. The first base case will naturally be n=1. After finishing your inductive step, you must check the values for which you invoked the inductive hypothesis. If, for instance, your inductive step uses the hypothesis at n − 3, then the proof will not work for n=2, because 2 − 3 = − 1, which is not a valid positive integer. Therefore, n=2 must be added as a base case.

Next, you test n=3. Since 3 − 3=0, and 0 is also not a positive integer, the inductive step does not work for n=3, so n=3 must be added as well. Finally, testing n=4 gives 4 − 3=1, which is a valid positive integer. Thus, the inductive step works for n=4, and it does not need to be included as a base case.

Therefore, since the inductive hypothesis was used with k = n − 3, the proof requires n=1, n=2, and n=3 as base cases.

It is important to check each part of your inductive step to ensure it works for every number that is not included as a base case. If the step fails for some value, that value must be added as an additional base case.

Read More

Epp, Susanna. Discrete Mathematics with Applications.