Section 4.3 More Mathematical Induction
In the last section we introduced mathematical induction by looking at proofs involving summation formulas. In this section we look at some more examples, including divisibility proofs and inequality proofs.
As in the previous section, we will assume We continue to use the Structure of a Mathematical Induction Proof from the previous section.
Example 4.3.1. Proof by Induction: Divisibility.
Prove for
Proof.
Base Step: Let Then We know
Thus, for
Induction Step:
Assume for some
Show
Scratchwork: before proving the induction step, we might need to do some scratchwork. This is NOT part of the proof, but will help us structure a clear proof. We can do some algebra on the expression we are trying to prove:
But by our assumption, and since the remaining terms are multiples of 3,
Now we are ready to use our scratch work to write the proof of the induction step.
Proof of induction step:
Which is what we wanted to show.
Hence, by induction for
Some comments about divisibility proofs:
- You will likely need to do scratchwork. Do not include the scratchwork in your actual proof.
- The point of the proof is that the reader can follow all of the steps. You do not need to explain where your choices came from. For example, in the proof in Example 4.3.1, it might not be obvious why you should add
but the reader just needs to know that 3 divides the expression, which is clear. - Divisibility proofs in this form can be challenging to do at first, but with practice, they often end up being some of the easier induction proofs to do, as they all follow a similar format.
Let’s try another example.
Example 4.3.2. Proof by Induction: Divisibility, Again.
Prove for
Proof.
Base Step: Let Then We know
Thus, for
Induction Step:
Assume for some
Show
Scratchwork:
But by our assumption, and since the remaining term is a multiple of 3,
Now we are ready to use our scratchwork to write the proof of the induction step.
Proof of induction step:
Which is what we wanted to show.
Hence, by induction for
Activity 4.3.2. A Divisibility Proof.
Our next example applies induction to a statement involving inequalities. Inequality induction proofs will be more challenging as they often take a bit more trial and error in the scratchwork. When dealing with equalities, you know for example, that you have to add the same thing to both sides. However, with inequalities you can change one side as long as you maintain the inequality. For example, if you know then you also know The fact that we can change one side of the expression makes it less intuitive to see what steps to take.
Example 4.3.3. Proof by Induction: Inequality.
Prove for
Proof.
Base Step: Let Then and We know
Thus, for
Induction Step:
Assume for some
Show
Scratchwork:
Now we want to make a useful observation: in the LHS expression we are addding. In the RHS expression we are multiplying. We need a way to go between them. One way is to notice that Then
We know and so we can put all this together into the proof.
Proof of induction step:
Thus, which is what we wanted to show.
Hence, by induction for
Exercises Exercises
1.
2.
3.
4.
Use mathematical induction to prove the following statements.
- For all non-negative integers
- For all non-negative integers
- For all non-negative integers
- For all non-negative integers
- For all non-negative integers
5.
Find a generalization for Exercise 4.3.4. State your generalization and prove it with induction.
6.
7.
Hint.
You can only do induction on integers, and only one integer at a time. So in this problem you want to do induction on not Let just be a variable. This problem does require so make sure you indicate in your proof where you needed to use that condition.