Induction
The principle of mathematical induction (often referred to as induction, sometimes referred to as PMI in books) is a fundamental proof technique. It is especially useful when proving that a statement is true for all positive integers
Induction is often compared to toppling over a row of dominoes. If you can show that the dominoes are placed in such a way that tipping one of them over ensures that the next one will fall and then you tip the first one over, you can assure that all the dominoes will eventually fall.
Contents
Statement
Let's say you have a statement that depends on a positive integer and you have to prove that this statement holds for all positive integers . How would you do that?
Step 1:
At first you prove that is true where is the starting value of your statement for example, if your statement is for all integers greater than 98, you must prove 99 is a valid solution. In other words, you must prove the starting value of your statement is valid.Step 2:
Then you show that if the statement is true for any arbitrary positive integer , then it is true for .
If you can do both of these things, you've proved that the statement is true for all positive integers . Congratulations!
Take some time to think about why this argument works. Remember that you proved that is true, where is your starting value. You also proved that is also true if is equal to which is a valid assumption Therefore, or would also be true. By the same reasoning, is also true and so on. Therefore, proving the two steps mentioned above is enough to prove that the statement holds for all positive integers above your starting value .
For further details, see Proof of Mathematical Induction.
Formulation
Main article: Writing a Proof by Induction
Now that we've gotten a little bit familiar with the idea of proof by induction, let's rewrite everything we learned a little more formally.
Proof by Induction
Step 1: Prove the base case
This is the part where you prove that is true if is the starting value of your statement. The base case is usually showing that our statement is true when .Step 2: The inductive step
This is where you assume that is true for some positive integer . This assumption is called the inductive hypothesis. Then you show that if were true, so is . This is the inductive step.In short, the inductive step usually means showing that .
Notice the word "usually," which means that this is not always the case. You'll learn that there are many variations of induction where the inductive step is different from this, for example, the strong induction
That's basically all there's to it. At the start, it is best to follow a standardized format so that you know exactly what to write. Once you get comfortable with it, you can simplify the proof further.
Sometimes, flawed induction proofs happen.
As always, the best way to learn is through examples. So let's begin!
Examples - Summation
Summations are often the first example used for induction. It is often easy to trace what the additional term is, and how adding it to the final sum would affect the value.
Prove that for all positive integers .
We want to prove something for "all positive integers " and induction seems like a good way to start.
First, we verify the base case. Although it seems obvious here (the base case is 1 because it is the first positive integer), this is a crucial step. Sometimes not verifying the base case can lead to fallacious proofs.
Our statement is true for (our base case) because with the left-hand side is and the right-hand side is which is also .
Now let us assume that the statement is true for some positive integer . This is our induction hypothesis. If we can show that the statement is true for , our proof is done.
By our induction hypothesis, we have
Now if we add to both sides, we get
which means that if our statement is true for , it is true for as well. This proves the statement true for all positive integers . We're done!
Prove that for all positive integers.
Since , the statement holds when .
Now let's assume that for some positive integer . Then add to both sides of the equation, which gives
Thus if the statement holds when , it also holds for . Therefore the statement is true for all positive integers .
Prove that for all positive integers.
Since , the statement holds when .
Now let's assume that for some positive integer . Then add to both sides of the equation, which gives
Thus if the statement holds when , it also holds for . Therefore the statement is true for all positive integers .
Examples - Inequalities
Induction can also be used for proving inequalities. Just apply the same method we have been using. Once again, it is easy to trace what the additional term is, and how it affects the final sum.
Prove that for all positive integers
Since , the statement holds when .
Now let's assume that for some positive integer which is larger than . Then multiply both sides of the equation by , which gives
Since we assumed that , is always true. Hence we have
Thus if the given statement holds when , it also holds for . Therefore the statement is true for all positive integers .
Prove that when , the inequality holds for all positive integers .
Since , the statement holds when .
Now let's assume that for some positive integer that is larger than . Then multiply both sides of the equation by , which gives
Thus if the statement holds when , it also holds for . Therefore the statement is true for all positive integers .
Prove, by mathematical induction, for
We attempt to verify that this statement holds true for the base case, that is, , which is true by nature. Now, we suppose that for some arbitrary integer, the statement will hold true: If this is true (by assumption), then if the next value of which is holds true, then by the principles of mathematical induction the whole statement is true within the domain of
which implies
Thus, if the statement holds when , it also holds for . Therefore, the statement holds true within the condition .
Sometimes the application of induction to inequalities cannot happen directly. This happens when the side that is supposed to be smaller is increased to a larger extent. For more details, see "Stronger" Induction.
Examples - Divisibility
For proving divisibility, induction gives us a way to slowly build up what we know. This allows us to show that certain terms are divisible, even without knowing number theory or modular arithmetic.
Prove that is always divisible by if is a positive integer.
Again we have to prove something about "all positive integers "
For our statement is true since is equal to and thus divisible by .
Now we have to show that if the statement is true for some positive integer , it is true for . If the statement is true for , we can set for some positive integer . Note that
Since , this can be rewritten as which is obviously divisible by .
We've been able to show the inductive step and that completes our proof.
Show that, for all positive integers ,
Let be the proposition for all positive integers .
First, consider the base case where . Observe that
and that divides since Then is true.
Now, assume is true for some then . This gives
\[ \begin{array} { l l } 64~|~ 3^{2k+3}+40k\times 9 - 67\times 9\\ 64~|~ 3^{2k+3}+40k + 40 + (40 \times 8k - 40) -67 + (-67\times 8)\\ 64~|~ 3^{2k+3}+40(k+1) -67 + (320k -576)\\
64~|~ 3^{2(k+1)+1}+40(k+1) -67. \end{array} \]Hence true true.
By mathematical induction, since the base case where is true and is true, true. Therefore, is true for all positive integers .
In the above question, it was difficult to utilize the induction hypothesis. Most people found it difficult to deal with the term, and the solution follows by understanding that .
We can actually show the base case for , which is a simpler calculation to do. While it is not immediately obvious why we would want to do this, imagine if the question asked to show this for positive integers . Would you want to evaluate Not likely.
Examples - Recurrence Relations
When you are given the closed form solution of a recurrence relation, it can be easy to use induction as a way of verifying that the formula is true.
Consider the sequence of numbers given by for all positive integers . Show that .
Base case:
Let's check .
LHS: RHS: .
Hence, the base case is true.Induction step:
Assume that for some .
Then we have
Hence, the inductive step is true, and the result follows.
Consider the Fibonacci sequence where for all positive integers . Prove that
for all
Base case:
Let . The LHS is and the RHS is .Induction step:
Assume that the statement is true for i.e. Then which is the statement for . This completes the induction.
Consider the sequence of numbers given by and for all positive integers . Show that .
Base case:
Let's check .
LHS: . RHS: .
LHS: . RHS: .
Hence the base case is true.Induction step:
Assume that and .
Then we have
\[\begin{array} {l l } b_{n+2} & = b_{n+1} + 2 \times b_n \\ & = \left(2^{n+2} + (-1)^{n+1} \right) + 2 \times \left(2 ^{n+1} + (-1)^n\right) \\ &= \left(2^{n+2} + 2^{n+2}\right) + \left( (-1)^{n+1} - 2 \times (-1)^{n+1} \right) \\ &= 2 \times 2 ^ {n+2} + (-1) \times (-1) ^ { n + 1 } \\
&= 2^{n+3} + (-1)^{n+2} \\ \end{array} \] Hence the inductive step is true and the result follows.Note: Why did we do 2 bases cases? This is because in the inductive step we have to use 2 equations.
As you can see, induction is a powerful tool for us to verify an identity. However, if we were not given the closed form, it could be harder to prove the statement by induction. Instead, we will need to study linear recurrence relations in order to understand how to solve them.
Examples - Functional Equations
The following theorem is an extremely important fact in functional equations.
is a real-valued function defined on the rationals such that for all rational values and . Then for all rational values .
We provide a sketch of the proof. Details are left to the reader.
We first show by induction that for all positive integers .
We then show that , so the statement holds for all integers.
By substituting and we get that for all integers.
We substitute and to get that
for all integers and .
Examples - Differentiation
Examples - Integration
Examples - Combinatorics Applications
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.
The statement is obviously true for or . So we're clear in the "base-case department."
But how do we show the inductive step, that is, if we know that there is a route for a country with cities, how do we show that a route exists for a country with cities?
Let's write down what we already know. Let's say the cities are and there is a route
that passes through all of them. This is our induction hypothesis. Now we have to show the inductive step. In other words, if we have another city , we have to show that it is possible to insert it somewhere in the route above.
We know that every two cities are connected by a one-way road. That means there is a road between and . Can we add to the end of the route like that?
No, because the roads are one-way and thus it is very much possible that the road between and may go the wrong way. We can't simply say that our route is
and that we are done with it. It's a bit more complicated than that.
However, all hope is not gone. Remember that any two cities are connected by a road. There is a possibility that . If that is the case, we're done because we have the route
If that is not the case, there exists an , with such that .
Take the largest such . By definition, we have . Now we can insert in between these two cities and we have the route
which completes our proof.
Note: There's a possibility that . That just means that you have to take to the end of the route.
For some positive integers , there exists a polynomial in variables whose image is exactly the set of the real positive numbers (note that 0 is not included in this set). The values of verifying that property are called Bremen numbers.
Find the sum of all the Bremen numbers smaller than or equal to 30.
Submit 0 as your answer if you believe that there does not exist any Bremen number smaller than or equal to 30.
Problem Solving
Here are some tips:
- Know when induction is a good approach. Problems containing the phrase "prove for all positive integers " are good candidates for induction.
- Never miss the base case. Although most of the times the base case is obvious, the proof isn't complete unless you show it. Not justifying the base case leads to a lot of fallacious proofs.
- If you want to use induction in a problem, make sure you have at least some sort of idea about how you're going to link to
- Sometimes proving something harder is easier! See "Stronger" Induction.
- Sometimes starting with a smaller base case makes calculation easier. Sometimes starting with a larger base case makes the induction step easier. Induction can also be used on finite discrete sets.
- You do not always induct on the variable
- If the hypothesis is given, questions usually test your mathematical ability to manipulate values.
If the proposition is not given, it tests your ability to make sense of a series and spot any underlying pattern crucial to the solution. - Though induction can establish the truthfulness of a statement, it rarely provides the motivation/reasoning behind the problem. However, it might provide a simpler solution.
Consider an 8 by 8 square grid with 1 random tile removed. Show that the remaining area can be completely tiled with 21 L-shaped triminos.
This might seem like a strange problem for induction because there is no variable to induct on. The trick to this problem is to instead show that
Give it a try!
Proof of Mathematical Induction
Let be a set of positive integers with the following properties:
(1) The integer 1 belongs to the set.
(2) Whenever integer is in , the next integer must also be in .Then is the set of all positive integers.
This statement seems almost immediately obvious. A proof is provided for completeness but is not essential in understanding induction.
We will prove this theorem by contradiction.
Let be the set of all positive integers not in . By assumption, is non-empty. Hence, according to the well-ordering principle, it must contain the 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.