Mathematical Induction

Spread the love

Introduction

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

Latex formula

which may be proven true using Mathematical Induction. The process of Mathematical Induction simply involves assuming the formula true for some integer Latex formula and then proving that if the formula is true for Latex formula then the formula is true for Latex formula. 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, Latex formula say.STEP 2 (Assumption)Assume that the statement/formula is true for some integral value, Latex formula say.

STEP 3 (Inductive Step)

Show that if the assumption is true then the statement is true for Latex formula.

STEP 4 (Conclusion)

End the proof by writing “Hence by Mathematical Induction the statement is true for Latex formula where Latex formula is an integer”, and Latex formula 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

Latex formula

and

Latex formula

We shall now illustrate the method of mathematical induction by proving the formula for the sum of the first positive integers.

Example 1

Prove that for all positive integers Latex formula,

Latex formula

Solution 1

STEP 1:

We prove that the statement is true for Latex formula. (Since we are required to prove the statement for all positive integers).

For Latex formula

LHS Latex formula

RHS Latex formulaLatex formulaLatex formulaLHS

Hence as RHS Latex formula LHS then the statement is true for Latex formula

STEP 2:

We assume that the statement is true for some positive integer Latex formula. That is,

Latex formula

STEP 3:

We now must prove that the statement is true for Latex formula. That is, we must prove,

Latex formula

LHS Latex formula

Latex formula

Latex formula

Latex formula

Latex formula RHS

Hence as the statement is true for Latex formula, it follows that the statement is true for Latex formula.

STEP 4:

Hence by Mathematical Induction the statement is true for Latex formula where Latex formula 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 2

Prove by mathematical induction that for all positive integral values of Latex formula,

Latex formula

Solution 2

This is exactly the same as proving

Latex formula

In this example we shall not write down the steps being taken as they should be obvious by the reasoning provided.

Firstly, for Latex formula

LHS Latex formula

RHS Latex formulaLatex formulaLatex formula LHS

Hence as RHS Latex formula LHS, the statement is true for Latex formula.

Assume the statement is true for Latex formula, where Latex formula is a positive integer. i.e.

Latex formula

We are now, R.T.P. (required to prove) that the statement is true for Latex formula. i.e.

Latex formula

Latex formula Latex formula Latex formula Latex formula Latex formula Latex formula Latex formulaHence as the statement is true for Latex formula, it follows that the statement is true for Latex formula.

Hence by Mathematical Induction the statement is true for Latex formula where Latex formula 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

Latex formula

Every student will remove a factor of Latex formula. It is also a good idea to remove the Latex formula out as a factor and this greatly simplifies ones working out. Be careful to account for the factor of Latex formula though in every term. For e.g. we have that,

Latex formula

Many students however incorrectly factor out the Latex formula and have the incorrect result,

Latex formula

Example 3

Prove by mathematical induction that for all positive integers Latex formula,

Latex formula

Solution 3

This is exactly the same as proving,

Latex formula

So, for Latex formula,

Latex formula

Latex formula

Hence as Latex formula it thus follows that the statement is true for Latex formula.

Assume that the statement is true for Latex formula where Latex formula is a positive integer. i.e.

Latex formula

(Note here that we have used Latex formula instead of Latex formula to avoid confusion, since the dummy variable within the summation is Latex formula)

We are now R.T.P. that the statement is true for Latex formula. That is,

Latex formula

Latex formula

Latex formula

Latex formula

Latex formula

Latex formula

Latex formula

Latex formula

Latex formula

Hence as the statement is true for Latex formula, it follows that the statement is true for Latex formula.

Hence by Mathematical Induction the statement is true for Latex formula where Latex formula 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 Latex formula is divisible by 4 for all integers, Latex formula

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 4

Prove by mathematical induction that for all positive integers Latex formula, Latex formula is divisible by Latex formula.

Solution 4

We shall firstly consider the base case.For Latex formula, Latex formula, which is clearly divisible by Latex formula. Hence the statement is true for Latex formula.

We now assume that the statement is true for Latex formula, where Latex formula is a positive integer. i.e.

Latex formula

where Latex formula is some integer.

We may write this in a more useful form, namely that

Latex formula

(Note this step!)

We now are R.T.P. that the statement is true for Latex formula. That is, Latex formula is divisible by Latex formula.

We have that

Latex formula

Latex formula

Latex formula

Latex formula

Latex formula

where Latex formula is an integer. Since Latex formula is divisible by Latex formula it thus follows that Latex formula is divisible by 4.

Hence by Mathematical Induction the statement is true for Latex formula where Latex formula is an integer.

Note: Notice that as in all induction proofs, we must use the assumed statement to prove the case for Latex formula. 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 5

Prove that Latex formula is an even number for all positive integral Latex formula.

Solution 5

An even number is any number that is divisible by Latex formula. Hence in this question we are proving that the required expression is divisible by Latex formula.So, for Latex formula (the first positive integer),

Latex formula

Which is divisible by Latex formula. Hence the statement is true for Latex formula.

Assume that the statement is true for Latex formula where Latex formula is a positive integer. i.e.

Latex formula

where Latex formula is an integer. i.e.

Latex formula

We now are R.T.P. that the statement is true for Latex formula. i.e. we are required to prove that Latex formula is divisible by Latex formula.

Latex formula

Latex formula

Latex formula

Latex formula

Where Latex formula is an integer. Hence as Latex formula is divisible by Latex formula then it follows that Latex formula is divisible by Latex formula.

Hence by Mathematical Induction the statement is true for Latex formula where Latex formula 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 Latex formula it thus follows that the statement is true for Latex formula, and hence for Latex formula and so on. Hence it follows that the statement is true for all integers Latex formula.” 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 Latex formula, 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 6

Prove by mathematical induction that Latex formula is divisible by Latex formula for all integers Latex formula.

Solution 6

We now prove the base case, where Latex formula. (Note the difference in the values for which we are required to prove the statement is true).For Latex formula,

Latex formula

which is clearly divisible by Latex formula. Hence the statement is true for Latex formula.

Assume that the statement is true for Latex formula, where Latex formula is an integer and Latex formula. i.e.

Latex formula

where Latex formula is an integer. i.e.

Latex formula

i.e.

Latex formula

(Note this technique!)

We are R.T.P. that the statement is true for Latex formula. i.e. that Latex formula is divisible by Latex formula.

Latex formula

Latex formula

Latex formula

Latex formula

Latex formula

Latex formula

where Latex formula is an integer. Since Latex formula is divisible by Latex formula, it thus follows that Latex formula is divisible by Latex formula.

Hence by Mathematical Induction the statement is true for Latex formula where Latex formula 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 7 

Prove by mathematical induction that Latex formula Is divisible by Latex formula for all positive integral Latex formula. (You may suppose that Latex formula)

Solution 7

For Latex formula, we have that

Latex formula

which is clearly divisible by Latex formula. Hence the statement is true for Latex formula.

Assume that the statement holds for Latex formula. That is,

Latex formula

Where Latex formula is some polynomial in Latex formula. (This is the definition of polynomial division)

That is,

Latex formula

We are now required to prove the statement true for Latex formula. i.e. we are required to prove that Latex formula is divisible by Latex formula.

Latex formula

Latex formula

Latex formula

Latex formula

Latex formula

where [latext]p(x)[/latext] is some polynomial in Latex formula. Hence as Latex formula is clearly divisible by Latex formula, it thus follows that Latex formula is also divisible by Latex formula.

Hence by Mathematical Induction the statement is true for Latex formula where Latex formula 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 Latex formula for all integral Latex formula where Latex formula

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 8

Prove by mathematical induction that Latex formula for Latex formula where Latex formula is an integer.

Solution 8

For Latex formula,LHS Latex formula

RHS Latex formula

Obviously we have that LHS Latex formula RHS and thus the statement is true for Latex formula.

Assume that the statement is true for Latex formula, where Latex formula is a positive integer. i.e.

Latex formula

R.T.P. true that the statement is true for Latex formula. i.e.

Latex formula

LHS Latex formula

Latex formula

Latex formula

Latex formula

Latex formula

Latex formulaRHS

Hence we have that LHS Latex formula RHS and that the statement is true for Latex formula, if the statement is true for Latex formula.

Hence by Mathematical Induction the statement is true for Latex formula where Latex formula is an integer.

We shall now investigate one more example to illustrate some of the techniques involved in solving these problems.

Example 9

Prove that Latex formula for Latex formula where Latex formula is an integer.

Solution 9

For Latex formula,LHS Latex formula

RHS Latex formula

Obviously LHS Latex formula RHS and thus we have that the statement is true for Latex formula.

Assume that the statement is true for Latex formula where Latex formula is a positive integer. i.e.

Latex formula

R.T.P. that the statement is true for Latex formula. i.e.

Latex formula

LHS Latex formula

Latex formula

Latex formula

Latex formula

Latex formula

Latex formula

Latex formula RHS

Hence as we have LHS Latex formula RHS, then it follows that the statement is true for Latex formula, if the statement is true for Latex formula.

Hence by Mathematical Induction the statement is true for Latex formula where Latex formula 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 10

Assuming that the product rule for differentiation holds, show that

Latex formula

For all positive integers .

Solution 10

For Latex formula,

LHS Latex formula Latex formula(Since it equals the gradient of Latex formula at the point Latex formula which is Latex formula)

RHS Latex formula LHS

Hence the statement is true for Latex formula.

Assume that the statement is true for Latex formula where Latex formula is a positive integer. i.e.

Latex formula

R.T.P. true that the statement is true for Latex formula. i.e.

Latex formula

LHS Latex formula Latex formula Latex formula

Latex formula Latex formula Latex formula Latex formula Latex formulaLatex formula RHS

Hence as the statement is true for Latex formula it thus is true for Latex formula.

Hence by Mathematical Induction the statement is true for Latex formula where Latex formula 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 11

Prove by induction that Latex formula is divisible by Latex formula for all Latex formula where Latex formula is integral and Latex formula.

Solution 11

Since we are using strong induction in this case, we then must prove that the statement is true for two base cases, namely Latex formula and Latex formula. (Since we assume the statement to be true for two values that are consecutive)For Latex formula;

Latex formula

which is clearly divisible by Latex formula. Hence the statement is true for Latex formula.

For Latex formula;

Latex formula

Which is clearly divisible by Latex formula. Hence the statement is true for Latex formula and Latex formula.

Assume the statement is true for Latex formula and Latex formula where Latex formula is a positive integer greater than Latex formula. That is,

Latex formula (*)

Latex formula (#)

Note here that Latex formula represents a polynomial in two variables Latex formula and Latex formula. An example of such a polynomial would be Latex formula.

R.T.P. that the statement is true for Latex formula. i.e. that Latex formula is divisible by Latex formula.

Latex formula

Latex formula

Latex formula

Latex formula (Using (*) and (#))

Latex formula

Latex formula

where Latex formula is a polynomial in two variables Latex formula and Latex formula. Obviously, as Latex formula is divisible by Latex formula it thus follows that Latex formula is divisible by Latex formula.

Hence by Mathematical Induction the statement is true for Latex formula where Latex formula is an integer.