Mathematics Extension 1 - Mathematical Induction

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

$1+2+3+\ldots +n=\frac{1}{2}n(n+1)$

which may be proven true using Mathematical Induction. The process of Mathematical Induction simply involves assuming the formula true for some integer $n=k$ and then proving that if the formula is true for $n=k$ then the formula is true for $n=k+1$ . 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, $j$ say.STEP 2 (Assumption)

Assume that the statement/formula is true for some integral value, $n=k$ say.

STEP 3 (Inductive Step)

Show that if the assumption is true then the statement is true for $n=k+1$ .

STEP 4 (Conclusion)

End the proof by writing “Hence by Mathematical Induction the statement is true for $n\ge j$ where $n$ is an integer”, and $j$ 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

$\sum_{k=m}^{n}{f(k)}=f(m)+f(m+1)+f(m+2)+\ldots +f(n)$

and

$\prod_{k=m}^{n}{f(k)}=f(m)\times f(m+1)\times f(m+2)\times \ldots \times f(n)$

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 $n$ ,

$1+2+3+\ldots +n=\frac{1}{2}n(n+1)$

Solution 1

STEP 1:

We prove that the statement is true for $n=1$ . (Since we are required to prove the statement for all positive integers).

For $n=1$

LHS $=1$

RHS $=$ $\frac{1}{2}$ $(1)(1+1)=1=$ LHS

Hence as RHS $=$ LHS then the statement is true for $n=1$

STEP 2:

We assume that the statement is true for some positive integer $n=k$ . That is,

$1+2+3+\ldots +k=\frac{1}{2}k(k+1)$

STEP 3:

We now must prove that the statement is true for $n=k+1$ . That is, we must prove,

$1+2+3+\ldots +k+(k+1)=\frac{1}{2}(k+1)(k+2)$

LHS $=1+2+3+\ldots +k+(k+1)$

$=\frac{1}{2}k(k+1)+(k+1)$

$=(k+1)(\frac{1}{2}k+1)$

$=\frac{1}{2}(k+1)(k+2)$

$=$ RHS

Hence as the statement is true for $n=k$ , it follows that the statement is true for $n=k+1$ .

STEP 4:

Hence by Mathematical Induction the statement is true for $n\ge 1$ where $n$ 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 $n$ ,

$\sum_{r=1}^{n}{r^{2}}=\frac{1}{6}n(n+1)(2n+1)$

Solution 2

This is exactly the same as proving

$1^{2}+2^{2}+3^{2}+\ldots +n^{2}=\frac{1}{6}n(n+1)(2n+1)$

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

Firstly, for $n=1$

LHS $=1^{2}=1$

RHS $=$ $\frac{1}{6}$ $(1)(1+1)(2(1)+1)=1=$ LHS

Hence as RHS $=$ LHS, the statement is true for $n=1$ .

Assume the statement is true for $n=k$ , where $k$ is a positive integer. i.e.

$\sum_{r=1}^{k}{r^{2}}=\frac{1}{6}k(k+1)(2k+1)$

We are now, R.T.P. (required to prove) that the statement is true for $n=k+1$ . i.e.

$\sum_{r=1}^{k+1}{r^{2}}=\frac{1}{6}(k+1)(k+2)(2k+3)$

$LHS=\sum_{r=1}^{k+1}{r^{2}}$ $=(k+1)^{2}+\sum_{r=1}^{k}{r^{2}}$ $=(k+1)^{2}+\frac{1}{6}k(k+1)(2k+1) (Using)$ $=\frac{1}{6}(k+1)\lbrace 6(k+1)+k(2k+1)\rbrace$ $=\frac{1}{6}(k+1)\lbrace 2k^{2}+7k+6\rbrace$ $=\frac{1}{6}(k+1)(k+2)(2k+3)$ $=RHS$

Hence as the statement is true for $n=k$ , it follows that the statement is true for $n=k+1$ .

Hence by Mathematical Induction the statement is true for $n\ge 1$ where $n$ 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

$\frac{1}{2}(k+1)+k(k+1)$

Every student will remove a factor of $(k+1)$ . It is also a good idea to remove the $1/2$ out as a factor and this greatly simplifies ones working out. Be careful to account for the factor of $1/2$ though in every term. For e.g. we have that,

$\frac{1}{2}(k+1)+k(k+1)=\frac{1}{2}(k+1)\lbrace 1+2k\rbrace$

Many students however incorrectly factor out the $1/2$ and have the incorrect result,

$\frac{1}{2}(k+1)+k(k+1)=\frac{1}{2}(k+1)\lbrace 1+k\rbrace$

Example 3

Prove by mathematical induction that for all positive integers $n$ ,

$\sum_{k=1}^{n}{\frac{1}{(2k-1)(2k+1)}}=\frac{n}{2n+1}$

Solution 3

This is exactly the same as proving,

$\frac{1}{1.3}+\frac{1}{3.5}+\frac{1}{5.7}+\ldots +\frac{1}{(2n-1)(2n+1)}=\frac{n}{2n+1}$

So, for $n=1$ ,

$LHS=\frac{1}{1.3}=\frac{1}{3}$

$RHS=\frac{1}{2(1)+1}=\frac{1}{3}=LHS$

Hence as $LHS=RHS$ it thus follows that the statement is true for $n=1$ .

Assume that the statement is true for $n=r$ where $r$ is a positive integer. i.e.

$\sum_{k=1}^{r}{\frac{1}{(2k-1)(2k+1)}}=\frac{r}{2r+1}$

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

We are now R.T.P. that the statement is true for $n=r+1$ . That is,

$\sum_{k=1}^{r+1}{\frac{1}{(2k-1)(2k+1)}}=\frac{r+1}{2r+3}$

$LHS=\sum_{k=1}^{r+1}{\frac{1}{(2k-1)(2k+1)}}$

$=\frac{1}{(2r+1)(2r+3)}+\sum_{k=1}^{r}{\frac{1}{(2k-1)(2k+1)}}$

$=\frac{1}{(2r+1)(2r+3)}+\frac{r}{2r+1} (Using)$

$=\frac{1+r(2r+3)}{(2r+1)(2r+3)}$

$=\frac{2r^{2}+3r+1}{(2r+1)(2r+3)}$

$=\frac{(2r+1)(r+1)}{(2r+1)(2r+3)}$

$=\frac{r+1}{2r+3}$

$=RHS$

Hence as the statement is true for $n=r$ , it follows that the statement is true for $n=r+1$ .

Hence by Mathematical Induction the statement is true for $n\ge 1$ where $n$ 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 $5^{n}-1$ is divisible by 4 for all integers, $n\ge 1$ ”

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 $n$ , $5^{n}-1$ is divisible by $4$ .

Solution 4

We shall firstly consider the base case.For $n=1$ , $5^{n}-1=5^{1}-1=4$ , which is clearly divisible by $4$ . Hence the statement is true for $n=1$ .

We now assume that the statement is true for $n=k$ , where $k$ is a positive integer. i.e.

$\frac{5^{k}-1}{4}=M$

where $M$ is some integer.

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

$5^{k}-1=4M$

(Note this step!)

We now are R.T.P. that the statement is true for $n=k+1$ . That is, $5^{k+1}-1$ is divisible by $4$ .

We have that

$5^{k+1}-1=5.5^{k}-1$

$=5(5^{k}-1)+4$

$=5(4M)+4 (Using)$

$=4(5M+1)$

$=4N$

where $N$ is an integer. Since $4N$ is divisible by $4$ it thus follows that $5^{k+1}-1$ is divisible by 4.

Hence by Mathematical Induction the statement is true for $n\ge 1$ where $n$ is an integer.

Note: Notice that as in all induction proofs, we must use the assumed statement to prove the case for $k+1$ . 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 $n(n+1)$ is an even number for all positive integral $n$ .

Solution 5

An even number is any number that is divisible by $2$ . Hence in this question we are proving that the required expression is divisible by $2$ .So, for $n=1$ (the first positive integer),

$n(n+1)=1(1+1)=2$

Which is divisible by $2$ . Hence the statement is true for $n=1$ .

Assume that the statement is true for $n=k$ where $k$ is a positive integer. i.e.

$\frac{k(k+1)}{2}=M$

where $M$ is an integer. i.e.

$k(k+1)=2M$

We now are R.T.P. that the statement is true for $n=k+1$ . i.e. we are required to prove that $(k+1)(k+2)$ is divisible by $2$ .

$(k+1)(k+2)=k(k+1)+2(k+1)$

$=2M+2(k+1) (Using)$

$=2(M+k+1)$

$=2N$

Where $N$ is an integer. Hence as $2N$ is divisible by $2$ then it follows that $(k+1)(k+2)$ is divisible by $2$ .

Hence by Mathematical Induction the statement is true for $n\ge 1$ where $n$ 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 $n=1$ it thus follows that the statement is true for $n=1+1=2$ , and hence for $n=2+1=3$ and so on. Hence it follows that the statement is true for all integers $n\ge 1$ .” 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 $n\ge 1$ , 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 $2^{3n}-1$ is divisible by $7$ for all integers $n\ge 0$ .

Solution 6

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

$2^{3n}-1=2^{3(0)}-1=0$

which is clearly divisible by $7$ . Hence the statement is true for $n=0$ .

Assume that the statement is true for $n=k$ , where $k$ is an integer and $k\ge 0$ . i.e.

$\frac{2^{3k}-1}{7}=M$

where $M$ is an integer. i.e.

$2^{3k}-1=7M$

i.e.

$2^{3k}=1+7M$

(Note this technique!)

We are R.T.P. that the statement is true for $n=k+1$ . i.e. that $2^{3(k+1)}-1$ is divisible by $7$ .

$2^{3(k+1)}-1=2^{3k+3}-1$

$=2^{3}.2^{3k}-1$

$=8.2^{3k}-1$

$=8(1+7M)-1 (Using)$

$=7(8M+1)$

$=7N$

where $N$ is an integer. Since $7N$ is divisible by $7$ , it thus follows that $2^{3(k+1)}-1$ is divisible by $7$ .

Hence by Mathematical Induction the statement is true for $n\ge 0$ where $n$ 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 $x^{n}-1$ Is divisible by $x-1$ for all positive integral $n$ . (You may suppose that $x\ne 1$ )

Solution 7

For $n=1$ , we have that

$x^{n}-1=x-1$

which is clearly divisible by $x-1$ . Hence the statement is true for $n=1$ .

Assume that the statement holds for $n=k$ . That is,

$\frac{x^{k}-1}{x-1}=p(x)$

Where $p(x)$ is some polynomial in $x$ . (This is the definition of polynomial division)

That is,

$x^{k}=(x-1)p(x)+1$

We are now required to prove the statement true for $n=k+1$ . i.e. we are required to prove that $x^{k+1}-1$ is divisible by $x-1$ .

$x^{k+1}-1=x.x^{k}-1$

$=x\lbrace (x-1)p(x)+1\rbrace -1$

$=x(x-1)p(x)+(x-1)$

$=(x-1)(x.p(x)+1)$

$=(x-1)q(x)$

where [latext]p(x)[/latext] is some polynomial in $x$ . Hence as $(x-1)q(x)$ is clearly divisible by $(x-1)$ , it thus follows that $x^{k+1}-1$ is also divisible by $x-1$ .

Hence by Mathematical Induction the statement is true for $n\ge 0$ where $n$ 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 $2^{n}>n^{2}$ for all integral $n$ where $n\ge 5$ ”

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 $2^{n}\ge n+1$ for $n\ge 1$ where $n$ is an integer.

Solution 8

For $n=1$ ,LHS $=2^{1}=2$

RHS $=1+1=2$

Obviously we have that LHS $\ge$ RHS and thus the statement is true for $n=1$ .

Assume that the statement is true for $n=k$ , where $k$ is a positive integer. i.e.

$2^{k}\ge k+1$

R.T.P. true that the statement is true for $n=k+1$ . i.e.

$2^{k+1}\ge k+2$

LHS $=2^{k+1}$

$=2.2^{k}$

$\ge 2(k+1) (Using)$

$=2k+2$

$\ge k+2 (Since k is a positive integer)$

$=$ RHS

Hence we have that LHS $\ge$ RHS and that the statement is true for $n=k+1$ , if the statement is true for $n=k$ .

Hence by Mathematical Induction the statement is true for $n\ge 1$ where $n$ 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 $12^{n}>7^{n}+5^{n}$ for $n>1$ where $n$ is an integer.

Solution 9

For $n=2$ ,LHS $=12^{2}=144$

RHS $=7^{2}+5^{2}=49+25=74$

Obviously LHS $>$ RHS and thus we have that the statement is true for $n=2$ .

Assume that the statement is true for $n=k$ where $k$ is a positive integer. i.e.

$12^{k}>7^{k}+5^{k}$

R.T.P. that the statement is true for $n=k+1$ . i.e.

$12^{k+1}>7^{k+1}+5^{k+1}$

LHS $=12^{k+1}$

$=12.12^{k}$

$>12(7^{k}+5^{k}) (Using)$

$=12.7^{k}+12.5^{k}$

$>7.7^{k}+5.5^{k} (Since 12>7 and 12>5)$

$=7^{k+1}+5^{k+1}$

$=$ RHS

Hence as we have LHS $>$ RHS, then it follows that the statement is true for $n=k+1$ , if the statement is true for $n=k$ .

Hence by Mathematical Induction the statement is true for $n>1$ where $n$ 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

$\frac{d}{dx}(x^{n})=nx^{n-1}$

For all positive integers .

Solution 10

For $n=1$ ,

LHS $=\frac{d}{dx}$ $(x^{1})=1$ (Since it equals the gradient of $f(x)=x$ at the point $x$ which is $1$ )

RHS $=1.x^{1-1}=1=$ LHS

Hence the statement is true for $n=1$ .

Assume that the statement is true for $n=k$ where $k$ is a positive integer. i.e.

$\frac{d}{dx}(x^{k})=kx^{k-1}$

R.T.P. true that the statement is true for $n=k+1$ . i.e.

$\frac{d}{dx}(x^{k+1})=(k+1)x^{k}$

LHS $=$ $\frac{d}{dx}$ $(x^{k+1})$

$=\frac{d}{dx}(x.x^{k})$ $=x.\frac{d}{dx}(x^{k})+x^{k}.\frac{d}{dx}(x) (By the product rule)$ $=x.kx^{k-1}+x^{k}.1 (Using and\frac{d}{dx}(x)=1)$ $=kx^{k}+x^{k}$ $=(k+1)x^{k}$

$=$ RHS

Hence as the statement is true for $n=k$ it thus is true for $n=k+1$ .

Hence by Mathematical Induction the statement is true for $n\ge 1$ where $n$ 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 $x^{n}-y^{n}$ is divisible by $x-y$ for all $n\ge 1$ where $n$ is integral and $x\ne y$ .

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 $n=1$ and $n=2$ . (Since we assume the statement to be true for two values that are consecutive)For $n=1$ ;

$x^{n}-y^{n}=x-y$

which is clearly divisible by $x-y$ . Hence the statement is true for $n=1$ .

For $n=2$ ;

$x^{2}-y^{2}=(x-y)(x+y)$

Which is clearly divisible by $x-y$ . Hence the statement is true for $n=1$ and $n=2$ .

Assume the statement is true for $n=k$ and $n=k-1$ where $k$ is a positive integer greater than $1$ . That is,

$x^{k-1}-y^{k-1}=(x-y) p(x , y)$ (*)

$x^{k}-y^{k}=(x-y) q(x , y)$ (#)

Note here that $p(x , y)$ represents a polynomial in two variables $x$ and $y$ . An example of such a polynomial would be $x^{4}y^{5}+y^{6}$ .

R.T.P. that the statement is true for $n=k+1$ . i.e. that $x^{k+1}-y^{k+1}$ is divisible by $x-y$ .

$x^{k+1}-y^{k+1}=x.x^{k}-y.y^{k}$

$=(x.x^{k}-x.y^{k})+(y.x^{k}-y.y^{k})+\lbrace x.y^{k}-y.x^{k}\rbrace$

$=x(x^{k}-y^{k})+y(x^{k}-y^{k})-xy(x^{k-1}-y^{k-1})$

$=x(x-y) q(x , y)+y(x-y) q(x , y)-xy(x-y) p(x , y)$ (Using (*) and (#))

$=(x-y)\lbrace x.q(x , y)+y .q(x , y)-xy.p(x , y)\rbrace$

$=(x-y). r(x , y)$

where $r(x , y)$ is a polynomial in two variables $x$ and $y$ . Obviously, as $(x-y)r(x , y)$ is divisible by $x-y$ it thus follows that $x^{k+1}-y^{k+1}$ is divisible by $x-y$ .

Hence by Mathematical Induction the statement is true for $n\ge 1$ where $n$ is an integer.

Mathematics Extension 1 – Mathematical Induction

Introduction

Example 1

Solution 1

Proving Summation Statements using Mathematical Induction

Example 2

Solution 2

Example 3

Solution 3

Proving divisibility statements using mathematical induction

Example 4

Solution 4

Example 5

Solution 5

Example 6

Solution 6

Example 7

Solution 7

Proving Inequality Statements using Mathematical Induction

Example 8

Solution 8

Example 9

Solution 9

Proving miscellaneous problems using Mathematical Induction

Example 10

Solution 10

Example 11

Solution 11

Dux College Parramatta

Dux College Bondi Junction

Mathematics Extension 1 – Mathematical Induction

Introduction

Example 1

Solution 1

Proving Summation Statements using Mathematical Induction

Example 2

Solution 2

Example 3

Solution 3

Proving divisibility statements using mathematical induction

Example 4

Solution 4

Example 5

Solution 5

Example 6

Solution 6

Example 7

Solution 7

Proving Inequality Statements using Mathematical Induction

Example 8

Solution 8

Example 9

Solution 9

Proving miscellaneous problems using Mathematical Induction

Example 10

Solution 10

Example 11

Solution 11

search

search