Skip to main content

Subsection 8.10.1 Strong Induction

So far, our inductive arguments have relied on our ability to prove:

If P holds for a single arbitrary value n, then it also holds for the next value, n+1.

Sometimes, however, we’ll need to use a stronger form of induction; we’ll argue:

If P holds for all values up to n, then it also holds for the next value, n+1.

We’ll call the inference rule that allows us to do that strong induction.

We can state the Principle of Strong Induction as follows:

If: P(b) is true for some integer base case b, and

For all integers n ≥ b:

(P(b) ∧ P(b+1) ∧ … ∧ P(n-1) ∧ P(n)) → P(n+1)

Then: For all integers n ≥ b, P(n)

Sometimes, to make clear which technique we’re using, we’ll call our old Principle of Mathematical Induction, weak induction.

While we are calling this new form of induction “strong” and we’re calling our old one “weak”, we should point out that, from a logical point of view, neither is stronger than the other. The soundness of one follows from the soundness of the other. Nevertheless, when we’re trying to do proofs, we may find strong induction a more potent tool.

Just like proofs that use weak induction, a proof using strong induction, of an assertion of the form ∀n (P(n)) about some set of natural numbers greater than or equal to some specific value b, has three parts. The first two are the same. The third one is different because it can use the fact that we assume P is true of all preceding values, not just the immediately preceding one.

The three proof steps are:

  1. A clear statement of the predicate P(n).

  2. A proof that that P holds for some base case b.

  3. A proof that:

(∀n ≥ b (P(b) ∧ P(b+1) ∧ … ∧ P(n-1) ∧ P(n))) → P(n+1)

As before, in step 3 we’ll exploit an inductive hypothesis, which, as in weak induction, is the antecedent of →. In other words, it’s:

n ≥ b (P(b) ∧ P(b+1) ∧ … ∧ P(n-1) ∧ P(n))

Consider the following claim:

Every positive integer can be written as the sum of distinct powers of 2.

We’ll prove it using strong induction. The idea is similar to the one we’ve used for all of our induction proofs. We want to prove something about n+1. We’ll figure out a way to describe it in terms of some smaller number. But that smaller number may not be n. It could be any smaller number. So it would be very awkward to use weak induction.

We proceed in the usual three steps.

First we define P(n)  (n can be written as the sum of distinct powers of 2)

Base case: P(1) is true because 1 = 20.

Induction step: We must prove:

Every positive integer less than or equal to n can be written as the sum of distinct powers of 2

\(\rightarrow\)

n + 1 can be written as the sum of distinct powers of 2.

The induction hypothesis is, of course, the claim to the left of . Now we must figure out how to use it to prove our claim about n+1. We must find something relevant about n+1 to start with.

Consider any n  1. There exists some integer k such that:

[1] 2k  n + 1 < 2k+1

To see why this must be so, consider the powers of 2 laid out on a number line:

1 2 4 8 16 and so forth.

Then any integer (including n + 1), is either equal to one of these (i.e., it’s 2k for some k), or it’s not, in which case it falls in some hole strictly between two numbers, 2k and 2k+1.

Suppose that n + 1 is equal to some 2k. Then, trivially, it can be written as the sum of distinct powers of 2. It’s just 2k.

Now suppose that it’s not equal to any 2k. Then it’s strictly in between two such values and we can rewrite [1] to say that:

[2] 2k < n + 1 < 2k+1 Just substituting < for 

[3] 0 < n + 1 - 2k < 2k+1 - 2k Subtracting 2k from all sides

[4] < n + 1 - 2k < 2k Since 2k+1 - 2k = 22k - 2k

But we also know that 2k  n. To see why this is so, recall [2]. We have that 2k is strictly less than n + 1. So it must be less than or equal to n. From [4] and the fact that 2k  n, we have:

[5] 0 < n + 1 - 2k < n

Since the value of n + 1 - 2k is positive, but less than n, the inductive hypothesis guarantees that it can be written as the sum of distinct powers of 2. Further, we know from [4] that n + 1 - 2k is less than 2k. So all of those powers are less than k. So we have:

[6] n + 1 - 2k = (some sum of distinct powers of 2, all less than k)

[7] n + 1 = 2k + (some sum of distinct powers of 2, all less than k)

We’ve added one new power of 2, but we know that it is distinct from all the others. Thus n + 1 can be written as the sum of distinct powers of 2.

By the Principle of Strong Induction then, we have that every positive integer can be written as the sum of distinct powers of 2.

If the claim that we just proved weren’t true, we wouldn’t be able to represent numbers in modern computers. Why not? Computer memory is a long string of bits, or binary digits. At the hardware level, each bit corresponds to an electronic component that has two states. Think of it as on/off, or positive/negative, or something else. The only thing that matters is that there are exactly two states. We’ll call them 0 and 1.

In the decimal number system that we use every day, a number is represented as the sum of powers of 10. So, for example, 5023 is 51000 + 0100 + 210 + 31. Note that each power of ten is multiplied by some factor between 0 and 9. If we needed to multiply by anything larger, we’d just use a higher power. So, for example, we don’t say that 5023 has 23 1’s. We give it 2 10’s and just use 1’s (3 of them) for the remainder. So we use digits from 0 up to 9 (which is 10–1). In the binary system that computers use, a number is represented similarly, except as the sum of powers of 2. So we only need two digits, 0 and 1 (which is 2-1). This is perfect if our hardware only has two states.

This means that we represent any natural number, in binary, as the sum of powers of 2. For example, 21 = 116 + 08 + 14 + 02 + 11. So we represent 21 in binary (and in our computers) as 10101.

Fortunately, we now know that it’s always possible to do this.

Exercises Exercises

1.

We’ve already seen that we can use weak induction to prove that there’s always a solution to our stamps problem: Suppose that the postage required to mail a letter is always at least 6¢. Prove that it is possible to apply any required postage to a letter given only 2¢ and 7¢ stamps. Recall that that solution required that we consider two cases when we did the inductive step. Using strong induction, we don’t have to do that. Write the proof.

Answer.
Click here for a hint. If clicked, should see: Strong induction lets us exploit the fact that P(n) is true of all values up to n. But often we don’t need to use all of them. Sometimes it’s sufficient just to go back one or maybe two values. So perhaps we want to use the fact that P(n-1) is true. Click here to see a complete proof. Base case: P(6) is true: We use three 2¢ stamps. P(7) is true: We use one 7¢ stamp. Induction hypothesis: possible to apply any amount up to n¢ Induction step: To apply (n+1)¢, add one 2¢ stamp to the postage required for (n-1)¢.