Mathematical Induction

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 formula$$Latex formula$$Latex formula$LHS

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 formula$$Latex formula$$Latex 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 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.

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 formula$RHS

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 formula$$Latex 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.