# Part 9: Mathematical Induction | Beginner’s Guide to Year 12 Ext 1 Maths

Are you shaky with proofs? Well, let’s boost your Mathematical Induction marks! In this article, we will outline the steps for induction questions including series and divisibility, and provide you with concept check questions to test your knowledge and skills!

## Year 12 Mathematics Extension 1: Proof by Mathematical Induction

Proof by Mathematical Induction is a subtopic under the Proofs topic which requires students to prove propositions in problems involving series and divisibility. Mathematical Induction plays an integral part in Mathematics as it allows us to prove the validity of relationships and hence induce general conclusions from those observations.

Mathematical Induction can often be visualised through the domino effect. If the first domino falls, the next domino will also fall, along with its neighbouring domino and so on. This leads to a chain effect where we can thus conclude that all the dominoes will fall.

### NESA Syllabus Outcomes

Students should be proficient in the following outcomes after studies in this topic:

#### ME-P1 Proof by Mathematical Induction

• Applies techniques involving proof or calculus to model and solve problems
• Chooses and uses appropriate technology to solve problems in a range of contexts
• Evaluates and justifies conclusions, communicating a position clearly in appropriate mathematical forms

## Assumed Knowledge

Students should have a basic understanding of factorials and algebraic manipulations.

## General Steps to Induction Questions

In Proof by Mathematical Induction, there are several key steps that must be completed in order to format your proof correctly. These general steps are shown as follows:

 Steps Working out 1 Prove the statement is true for the base caseWe must verify that the statement is true for the base case (eg. $$n=1$$) by showing that LHS = RHS. 2 Assume the statement is true for $$n=k$$We assume that the statement is true for some positive integer $$n=k$$. 3 Prove the result is true for $$n=k+1$$We must prove, using the assumption made in step 2, that our result is true for $$n=k+1$$ (or the next value of $$n$$).Note: In some questions, the next case may not be $$n=k+1$$. For example, when inducting over odd integers, the next case would be $$n=k+2$$ since consecutive odd integers differ by 2. 4 ConclusionConclude the proof by stating something similar to: “The result is true for $$n=1$$. If the result is true for $$n=k$$, it is true for $$n=k+1$$. Therefore, by Mathematical Induction, it is true for all integers $$n≥1$$”

Note: Every school has their own approach to Proof by Mathematical Induction. Follow your own school’s format.

Continuing the domino analogy, Step 1 is proving that the first domino in a sequence will fall. Step 2 & 3 is equivalent to proving that if a domino falls, then the next one in sequence will fall. Step 4 concludes by saying that every domino in the sequence will fall.

## Induction involving Series

In this section, we will be proving results where one side is a sum of terms and the other side is an equivalent formula. The general strategy for induction involving series is to utilise the Step 2 assumption with the first terms in Step 3 to reduce the number of terms significantly.

### Example 1:

Prove by mathematical induction that $$1+2+3+…+n= \frac{n(n+1)}{2}$$ for all $$n≥1$$

### Solution:

 Steps Working out 1 Prove the result is true for $$n=1$$\begin{align*} LHS &= 1\\ RHS &= \frac{1(1+1)}{2}\\ &= 1\\ \end{align*}$$LHS = RHS$$ therefore true for $$n=1$$ 2 Assume the statement is true for $$n=k$$i.e. $$1+2+3+…+k= \frac{k(k+1)}{2}$$ 3 Use the assumption to prove it true for $$n=k+1$$i.e. $$1+2+3+…+k+(k+1) = \frac{(k+1)(k+2)}{2}$$\begin{align*} LHS &= 1 + 2 +3+…+k+(k+1)\\ &= \frac{k(k+1)}{2}+(k+1) \ \ \ \ \text{(using Step 2)}\\ &= \frac{(k+1)(k+2)}{2}\\ &= RHS\\ \end{align*} 4 The result is true for $$n=1$$. If the result is true for $$n=k$$, it is true for $$n=k+1$$. Therefore, by Mathematical Induction, it is true for all integers $$n≥1$$.

### Example 2:

Prove by mathematical induction that $$n!+(n-1)!+(n-2)!=n^2(n-2)!$$ for all $$n≥2$$

### Solution

 Steps Working out 1 Prove the result is true for $$n=2$$\begin{align*} LHS &= 2! + 1! + 0!\\ &= 2+1+1\\ &=4\\ RHS &= 2^2 \times 0!\\ &= 4\\ \end{align*}$$LHS=RHS$$ therefore true for $$n=2$$ 2 Assume the statement is true for $$n=k$$i.e. $$k!+(k-1)!+(k-2)!=k^2(k-2)!$$ 3 Use the assumption to prove it true for $$n=k+1$$i.e. $$(k+1)!+k!+(k-1)!=(k+1)^2(k-1)$$\begin{align*} LHS &= (k+1)! +k! +(k-1)!\\ &= (k+1)(k)(k-1)!+(k^2(k-2)!-(k-2)!) \ \ \text{(using Step 2)}\\ &= (k+1)(k)(k-1)!+(k-2)!(k^2-1)\\ &= (k+1)(k)(k-1)!+(k-2)!(k-1)(k+1)\\ &= (k+1)(k)(k-1)!+(k-1)!(k+1)\\ &= (k-1)![(k+1)(k)+(k+1)]\\ &= (k-1)!(k+1)(k+1)\\ &=(k-1)!(k+1)^2\\ &=RHS \end{align*} 4 The result is true for $$n=2$$. If the result is true for $$n=k$$, it is true for $$n=k+1$$. Therefore, by Mathematical Induction, it is true for all integers $$n≥2$$.

## Induction involving Divisibility

In this section, we will be proving results about the divisibility of an expression. A number is $$n$$ divisible by another number $$d$$, if $$n÷d$$ is a whole number.
For example, $$30$$ is divisible by $$5$$ because

$$30=6 \times 5$$

We will generalise this example with $$n$$ being divisible by $$d$$ as

$$n=d \times M$$

where $$M$$ is an integer.

### Example 1:

Prove by mathematical induction that $$5^n-1$$ is divisible by 4, for any $$n≥1$$

### Solution:

 Steps Working out 1 Prove the result is true for $$n=1$$\begin{align*} LHS &= 5^1-1\\ &= 4\\ \end{align*}Which is divisible by 4, therefore true for $$n=1$$ 2 Assume the statement is true for $$n=k$$i.e.\begin{align*} 5^k-1 &= 4M \ \ \ \text{(where M is an integer)} \\ 5^k &=4M+1\\ \end{align*} 3 Use the assumption to prove it true for $$n=k+1$$i.e. $$5^{k+1}-1 = 4J \ \ \ \text{(where J is some integer)}$$\begin{align*} LHS &= 5^{k+1}-1\\ &= 5 \times 5^k -1\\ &= 5 \times (4M+1) -1 \ \ \ \text{(using Step 2)} \\ &= 20M + 4\\ &= 4(5M+1)\\ &= 4J\\ &= RHS\\ \end{align*}Note: $$(5M+1)$$ is an integer because the addition and multiplication of integers produces integers. 4 The result is true for $$n=1$$. If the result is true for $$n=k$$, it is true for $$n=k+1$$. Therefore, by Mathematical Induction, it is true for all integers $$n≥1$$.

### Example 2:

Prove by mathematical induction that $$8^{2n+1} + 6^{2n-1}$$ is divisible by 7, for any $$n≥1$$.

### Solution:

 Steps Working out 1 Prove the result is true for $$n=1$$\begin{align*} LHS &= 8^{2(1)+1}+ 6^{2(1)-1}\\ &= 8^3+6^1\\ &= 512+6\\ &=518\\ \end{align*}Which is divisible by 7, therefore true for $$n=1$$ 2 Assume the statement is true for $$n=k$$i.e.\begin{align*} 8^{2k+1}+6^{2k-1} &= 7M \ \ \ \text{(where M is an integer)}\\ 8^{2k+1}&= 7M-6^{2k-1}\\ \end{align*} 3 Use the assumption to prove it true for $$n=k+1$$i.e. $$8^{2(k+1)+1} +6^{2(k+1)-1}=7J \ \ \text{(where J is some integer)}$$\begin{align*} LHS &= 8^{2(k+1)+1} +6^{2(k+1)-1}\\ &= 8^2 \times 8^{2k+1}+6^{2(k+2)-2}\\ &= 64(7M-6^{2k-1})+6^{2k+2-1} \ \ \text{(using step 2)}\\ &= 448M – 64 \times 6^{2k-1} + 36 \times 6^{2k-1}\\ &= 448M+28 \times 6^{2k-1}\\ &=7(64M + 4 \times 6^{2k-1})\\ &= 7J\\ &=RHS\\ \end{align*}Note: $$64M + 4 \times 6^{2k-1}$$ is an integer because the addition, multiplication and positive integer exponentiation of integers produces integers. 4 The result is true for $$n=1$$. If the result is true for $$n=k$$, it is true for $$n=k+1$$. Therefore, by Mathematical Induction, it is true for all integers $$n≥1$$.

## Further Induction Problems

In this section, we will apply induction to prove results in other topics of the course, such as trigonometry, permutations and combinations, calculus and more. However, note that this is not formally within the Year 12 Mathematics Extension 1 syllabus, but rather an extension for interested students.

### Example 3:

Prove $$\frac{d(x^n)}{dx}=n ⋅x^{n-1}$$ for positive values of using mathematical induction.

### Solution:

 Steps Working out 1 Prove the result is true for $$n=1$$\begin{align*} LHS &= \frac{d(x^1)}{dx} = 1\\ RHS &= 1⋅x^0=1\\ \end{align*}$$LHS=RHS$$, therefore true for $$n=1$$ 2 Assume the statement is true for $$n=k$$i.e. $$\frac{d(x^k)}{dx}=k⋅x^{k-1}$$ 3 Use the assumption to prove it true for $$n=k+1$$\begin{align*} LHS &= \frac{d(x^{k+1})}{dx}\\ &= \frac{d(x^k ⋅ x)}{dx}\\ &= \frac{d(x^k)}{dx} x + \frac{d(x)}{dx} x^k\\ &= k ⋅x^{k-1} ⋅x+x^k \ \ \text{(using steps 1 and 2)}\\ &= k⋅x^k+x^k\\ &= (k+1) ⋅x^k\\ &= RHS\\ \end{align*}$$LHS=RHS$$, therefore true for $$n=k+1$$ 4 The result is true for $$n=1$$. If the result is true for $$n=k$$, it is true for $$n=k+1$$. Therefore, by Mathematical Induction, it is true for all integers $$n≥1$$.

## Concept Check Questions

1. Prove by Mathematical Induction that $$1^3+2^3+3^3+…+n^3 = \frac{n^2}{4}(n+1)^2$$ for all $$n≥1$$

2. Prove by Mathematical Induction that $$2^{n+2}+3^{3n}$$ is divisible by 5 for all $$n≥1$$

3. Use Mathematical Induction to show that $$cos(x+nπ)=(-1)^ncosx$$ for all positive integers $$n≥1$$.

## Want to refine your Mathematical Induction skills?

In our HSC Prep Course, our subject matter experts will revise the core topics in Maths Ext 1 through structured video lessons and provide you with plenty of practice questions and mock exams. Learn more about our HSC Prep Course now.

© Matrix Education and www.matrix.edu.au, 2021. Unauthorised use and/or duplication of this material without express and written permission from this site’s author and/or owner is strictly prohibited. Excerpts and links may be used, provided that full and clear credit is given to Matrix Education and www.matrix.edu.au with appropriate and specific direction to the original content.