Mathematical Induction
Introduction
Contents
Mathematical Induction is the process by which a certain formula or expression is proved to be true for an infinite set of integers. An example of such a formula would be
which may be proven true using Mathematical Induction. The process of Mathematical Induction simply involves assuming the formula true for some integer and then proving that if the formula is true for then the formula is true for . From this we may show that the formula is true, if and only if there is a base case. That is, if there exists some integer for which the formula is true. After this, the formula is true for all integers larger than that integral value, since if it is true for some integer, then it is true for the integer plus one and then that integer plus one and so on. The idea is set out below,
STEP 1 (Base Case)Show that the statement/formula is true for some integral value, say.STEP 2 (Assumption)
Assume that the statement/formula is true for some integral value, say. STEP 3 (Inductive Step) Show that if the assumption is true then the statement is true for . STEP 4 (Conclusion) End the proof by writing “Hence by Mathematical Induction the statement is true for where is an integer”, and was the integer the base case is true for. |
Before we move on, we shall review some basic notation and terminology which becomes useful in this topic.
- An integer is a whole number.
- A number greater than zero which is an integer is called a positive integer.
- A number greater than or equal to zero which is an integer is called a non-negative integer.
- Be familiar with the summation and product notation
and
We shall now illustrate the method of mathematical induction by proving the formula for the sum of the first positive integers.
Example 1Prove that for all positive integers , Solution 1STEP 1: We prove that the statement is true for . (Since we are required to prove the statement for all positive integers). For LHS RHS LHS Hence as RHS LHS then the statement is true for STEP 2: We assume that the statement is true for some positive integer . That is, STEP 3: We now must prove that the statement is true for . That is, we must prove, LHS RHS Hence as the statement is true for , it follows that the statement is true for . STEP 4: Hence by Mathematical Induction the statement is true for where is an integer. |
This illustrates the technique of mathematical induction. We shall now move on to an important category of questions requiring mathematical induction.
Proving Summation Statements using Mathematical Induction
We will study some further examples of summation problems in mathematical induction. In general, the three main types of mathematical induction problems are classified into summation, division or inequality problems. Some problems fall outside these categories, and we shall study them to encourage a more holistic view of Mathematical Induction.
Example 2Prove by mathematical induction that for all positive integral values of , Solution 2This is exactly the same as proving In this example we shall not write down the steps being taken as they should be obvious by the reasoning provided. Firstly, for LHS RHS LHS Hence as RHS LHS, the statement is true for . Assume the statement is true for , where is a positive integer. i.e. We are now, R.T.P. (required to prove) that the statement is true for . i.e. Hence as the statement is true for , it follows that the statement is true for . Hence by Mathematical Induction the statement is true for where is an integer. |
Note: A very good technique with these types of questions is to remove as a factor anything that occurs in the final statement. For e.g. in the simplification of
Every student will remove a factor of . It is also a good idea to remove the out as a factor and this greatly simplifies ones working out. Be careful to account for the factor of though in every term. For e.g. we have that,
Many students however incorrectly factor out the and have the incorrect result,
Example 3Prove by mathematical induction that for all positive integers , Solution 3This is exactly the same as proving, So, for , Hence as it thus follows that the statement is true for . Assume that the statement is true for where is a positive integer. i.e. (Note here that we have used instead of to avoid confusion, since the dummy variable within the summation is ) We are now R.T.P. that the statement is true for . That is, Hence as the statement is true for , it follows that the statement is true for . Hence by Mathematical Induction the statement is true for where is an integer. |
Proving divisibility statements using mathematical induction
Mathematical Induction is also very useful in proving that a certain expression is always divisible by another, given that the expressions have integers as there input. An example question would be,
“Prove that is divisible by 4 for all integers, ”
Such a question is proved using the exact same steps as those used previously, except that at the assumption step, we assume that the quotient is equal to some integer if numbers are being divided, or a polynomial if polynomials are being divided. This is due to divisibility being defined as thus. Also, at the inductive step, we must rearrange the expression so as to be able to substitute the assumed expression in. We shall now illustrate this by completing the above question as an example.
Example 4Prove by mathematical induction that for all positive integers , is divisible by . Solution 4We shall firstly consider the base case.For , , which is clearly divisible by . Hence the statement is true for . We now assume that the statement is true for , where is a positive integer. i.e. where is some integer. We may write this in a more useful form, namely that (Note this step!) We now are R.T.P. that the statement is true for . That is, is divisible by . We have that where is an integer. Since is divisible by it thus follows that is divisible by 4. Hence by Mathematical Induction the statement is true for where is an integer. |
Note: Notice that as in all induction proofs, we must use the assumed statement to prove the case for . Now, the step used, (that is the process of multiplying through by the divisor) is the key step which allows one to prove the result using induction. Consider another example to clarify the process.
Example 5Prove that is an even number for all positive integral . Solution 5An even number is any number that is divisible by . Hence in this question we are proving that the required expression is divisible by .So, for (the first positive integer), Which is divisible by . Hence the statement is true for . Assume that the statement is true for where is a positive integer. i.e. where is an integer. i.e. We now are R.T.P. that the statement is true for . i.e. we are required to prove that is divisible by . Where is an integer. Hence as is divisible by then it follows that is divisible by . Hence by Mathematical Induction the statement is true for where is an integer. |
Note: At this point it should be mentioned that some teachers insist that there students write out a conclusion to their mathematical induction proofs on the lines of “Since the statement is true for it thus follows that the statement is true for , and hence for and so on. Hence it follows that the statement is true for all integers .” Not only is this excessive and unnecessary, it also is incorrect because it has not mentioned once that the proof was by the method of mathematical induction. It is said in the Mathematics Extension 1 examiners comments that students should only write down a statement such as “Hence the statement is true for integers , by mathematical induction.” This is because Mathematical Induction is an axiom upon which Mathematics is built, not a theory that has a reasoning or proof behind it. Hence any type of explanation of Mathematical Induction from a heuristic approach is deemed to be incorrect, and students should keep to a simple conclusion as given in these notes. Students should note though that the values for which the statement is true is important and should be stated clearly in the conclusion.
We shall now consider another example;
Example 6Prove by mathematical induction that is divisible by for all integers . Solution 6We now prove the base case, where . (Note the difference in the values for which we are required to prove the statement is true).For , which is clearly divisible by . Hence the statement is true for . Assume that the statement is true for , where is an integer and . i.e. where is an integer. i.e. i.e. (Note this technique!) We are R.T.P. that the statement is true for . i.e. that is divisible by . where is an integer. Since is divisible by , it thus follows that is divisible by . Hence by Mathematical Induction the statement is true for where is an integer. |
Note:The technique used in the assumption in the above example is useful in simplifying ones working out.
We shall now consider an example of polynomial division.
Example 7Prove by mathematical induction that Is divisible by for all positive integral . (You may suppose that ) Solution 7For , we have that which is clearly divisible by . Hence the statement is true for . Assume that the statement holds for . That is, Where is some polynomial in . (This is the definition of polynomial division) That is, We are now required to prove the statement true for . i.e. we are required to prove that is divisible by . where [latext]p(x)[/latext] is some polynomial in . Hence as is clearly divisible by , it thus follows that is also divisible by . Hence by Mathematical Induction the statement is true for where is an integer. |
We shall now move on to induction problems involving inequality statements.
Proving Inequality Statements using Mathematical Induction
Inequality statements are not at all times straightforward to answer, and it is ones experience in answering such questions that proves to be the largest factor in solving these questions. Questions involving inequalities are typically questions such as,
“Prove that for all integral where ”
These types of questions are solved using the exact same technique as in the summation and divisibility questions. In these questions however, one proves the inductive step by showing that RHS and LHS satisfy the inequality required, after using the assumed statement. The below example will clarify this point.
Example 8Prove by mathematical induction that for where is an integer. Solution 8For ,LHS RHS Obviously we have that LHS RHS and thus the statement is true for . Assume that the statement is true for , where is a positive integer. i.e. R.T.P. true that the statement is true for . i.e. LHS RHS Hence we have that LHS RHS and that the statement is true for , if the statement is true for . Hence by Mathematical Induction the statement is true for where is an integer. |
We shall now investigate one more example to illustrate some of the techniques involved in solving these problems.
Example 9Prove that for where is an integer. Solution 9For ,LHS RHS Obviously LHS RHS and thus we have that the statement is true for . Assume that the statement is true for where is a positive integer. i.e. R.T.P. that the statement is true for . i.e. LHS RHS Hence as we have LHS RHS, then it follows that the statement is true for , if the statement is true for . Hence by Mathematical Induction the statement is true for where is an integer. |
Note: With inequality problems, a standard technique to use is to bring all terms onto one side to obtain a zero on another side. After this the problem boils down to proving that one side is always positive, negative or non-negative. Solving the problem using this method is rarely the best way to do so, but it is included so that the student may add this into his or her arsenal.
Proving miscellaneous problems using Mathematical Induction
We shall now investigate problems that can only come under the appropriately named category “miscellaneous”. These problems require deeper understanding and a more perseverance then most induction questions. We shall investigate some of these to show the method of solving these questions.
Example 10Assuming that the product rule for differentiation holds, show that For all positive integers . Solution 10For , LHS (Since it equals the gradient of at the point which is ) RHS LHS Hence the statement is true for . Assume that the statement is true for where is a positive integer. i.e. R.T.P. true that the statement is true for . i.e. LHS RHS Hence as the statement is true for it thus is true for . Hence by Mathematical Induction the statement is true for where is an integer. |
The above problem was in fact the induction question from the 2009 Mathematics Extension 1 HSC. The next example shows the method of “Strong Induction” where you assume the statement to be true for more than one value. This is not included in the Mathematics Extension 1 syllabus, but is the focus of Mathematics Extension 2 induction. Also, it is another example of polynomial division.
Example 11Prove by induction that is divisible by for all where is integral and . Solution 11Since we are using strong induction in this case, we then must prove that the statement is true for two base cases, namely and . (Since we assume the statement to be true for two values that are consecutive)For ; which is clearly divisible by . Hence the statement is true for . For ; Which is clearly divisible by . Hence the statement is true for and . Assume the statement is true for and where is a positive integer greater than . That is, (*) (#) Note here that represents a polynomial in two variables and . An example of such a polynomial would be . R.T.P. that the statement is true for . i.e. that is divisible by . (Using (*) and (#)) where is a polynomial in two variables and . Obviously, as is divisible by it thus follows that is divisible by . Hence by Mathematical Induction the statement is true for where is an integer. |