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!
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.
Students should be proficient in the following outcomes after studies in this topic:
Students should have a basic understanding of factorials and algebraic manipulations.
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 case
We 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 | Conclusion
Conclude the proof by stating something similar to: |
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.
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.
Prove by mathematical induction that \(1+2+3+…+n= \frac{n(n+1)}{2}\) for all \(n≥1\)
| Steps | Working out |
| 1 | Prove the result is true for \(n=1\)
\begin{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*} |
| 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\). |
Prove by mathematical induction that \(n!+(n-1)!+(n-2)!=n^2(n-2)!\) for all \(n≥2\)
| Steps | Working out |
| 1 | Prove the result is true for \(n=2\)
\begin{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*} |
| 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\). |
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.
Prove by mathematical induction that \(5^n-1\) is divisible by 4, for any \(n≥1\)
| Steps | Working out |
| 1 | Prove the result is true for \(n=1\)
\begin{align*} Which is divisible by 4, therefore true for \(n=1\) |
| 2 | Assume the statement is true for \(n=k\)
i.e. \begin{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*} 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\). |
Prove by mathematical induction that \(8^{2n+1} + 6^{2n-1}\) is divisible by 7, for any \(n≥1\).
| Steps | Working out |
| 1 | Prove the result is true for \(n=1\)
\begin{align*} Which is divisible by 7, therefore true for \(n=1\) |
| 2 | Assume the statement is true for \(n=k\)
i.e. \begin{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*} 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\). |
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.
Prove \(\frac{d(x^n)}{dx}=n ⋅x^{n-1}\) for positive values of using mathematical induction.
| Steps | Working out |
| 1 | Prove the result is true for \(n=1\)
\begin{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=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\). |
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\).
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, 2023. 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.
