Strong induction is a variant of induction, in which we assume that the statement holds for all values preceding . This provides us with more information to use when trying to prove the statement.
Now that we know how standard induction works, it's time to look at a variant of it, strong induction. In many ways, strong induction is similar to normal induction. There is, however, a difference in the inductive hypothesis. Normally, when using induction, we assume that is true to prove . In strong induction, we assume that all of are true to prove .
Why would we need to do that? Let's go back to our domino analogy. Say that you have infinitely many dominoes arranged in a line. But this time, the weight of the domino isn't enough to knock down the domino. Knocking down the domino requires the weight of all the dominoes before it. Even now, if you are able to knock down the first domino, you can prove that all the dominoes will eventually fall.
The reason why this is called "strong induction" is that we use more statements in the inductive hypothesis. Let's write what we've learned till now a bit more formally.
Proof by strong induction
Step 1. Demonstrate the base case:
This is where you verify that is true. In most cases,
Step 2. Prove the inductive step:
This is where you assume that all of , are true (our inductive hypothesis). Then you show that is true.
The proof of why this works is similar to that of standard induction.
[Fundamental Theorem of Arithmetic]
Every integer can be written uniquely as the product of prime numbers.
Base case: This is clearly true for .
Inductive step: Suppose the statement is true for
If is prime, then we are done. Otherwise, has a smallest prime factor, which we denote by Let Since , by our inductive hypothesis, can be written uniquely as the product of prime numbers. That means can also be written uniquely as a product of primes. We're done!
Notice how the assumption that is true wasn't enough to prove that is true. We actually needed another statement instead.
The Fibonacci sequence is defined by for integers , with starting values . Show that
For , we have and .
For , we have and .
Induction step: Suppose that the statement is true for and . Then, we have
Hence, the proposition is true.
Note that, in this case, we did not need to use all of prior statements, but just the previous 2.
A chocolate bar consists of unit squares arranged in an rectangular grid. You may split the bar into individual unit squares, by breaking along the lines. What is the number of breaks required?
We will show that the number of breaks needed is .
For a square, we are already done, so no steps are needed.
, so the base case is true.
Induction Step: Let denote the number of breaks needed to split up an square.
WLOG, we may assume that the first break is along a row, and we get an and an bar, where .
By the induction hypothesis, the number of further breaks that we need is and .
Hence, the total number of breaks that we need is
Note: This problem can also be approached using Invariance principle.
A country has cities. Any two cities are connected by a one-way road. Show that there is a route that passes through every city.
If you have already read the wiki on standard induction, this problem may seem familiar. Yes, we did prove this in that article (if you haven't read that wiki, now would be a good time to do that). We'll see how stronger induction produces a shorter and cleaner solution.
As we've already seen, our base case for this is true.
Now we make the "strong hypothesis." We assume that our statement is true for any set of or fewer cities.
Now, for a set of cities, take out the city and split the rest of them into two sets and . will contain all the cities that lead to and will contain all the cities leads to.
Since has or fewer cities in it, by the inductive hypothesis, there is a route that passes through every city in . The same argument holds for .
Now start with the route that passes through every city in . Then go to . You can do that because all the cities in lead to . After that, go to the route that passes through every city in . Again, you can do that because leads to every city in .
And just like that, our proof is complete!
This proof is almost identical to the proof of standard induction. Can you spot the differences?
Let be a set of positive integers with the following properties:
- The integer 1 belongs to the set.
- Whenever the integers are in , the next integer must also be in .
Then is the set of all positive integers.
We will prove this theorem by contradiction.
Let be the set of all positive integers not in . By assumption, is non-empty. Hence it must contain a smallest element, which we will denote by .
By (1), . Since is the smallest integer in , this implies that .
By (2), must also contain . This contradicts the assumption that .
Hence set is empty, and set contains all positive integers.
Show that every integer can be written in the form , where is a non-negative integer and is an odd integer.
[APMO '99] Let be a sequence of real numbers that satisfy . Prove that
Prove that every positive integer has a binary expression. Namely, that there exists integers such that
Consider the sequence defined as and for all positive integers .
Show that .