Ultimate Guide to Proof by Mathematical Induction in HSC Maths Ext 1

Introduction

In mathematics, guessing a pattern isn't enough; you must prove that the pattern holds true forever, up to infinity. This is where Proof by Mathematical Induction becomes one of your most powerful tools. Introduced in the Year 12 Mathematics Extension 1 course, it is a beautifully logical method used to prove that a mathematical statement is true for all integers.

This ultimate guide will break down the exact structure of an inductive proof, showing you how to conquer sum and divisibility problems, and how to spot the subtle errors in false proofs.

Executive Summary

The "Proof by mathematical induction" topic (aligned with outcome ME1-12-01) teaches students to construct rigorous mathematical arguments. You will learn to establish a base case, form an inductive hypothesis, and execute the crucial inductive step to prove results involving series/sums and divisibility. You will also develop the critical thinking skills required to identify logical flaws in invalid proofs.

What is this about?

This detailed guide is broken down into three essential areas:

The Nature of Inductive Proof: Understanding the domino effect—the base case, the assumption, and the inductive step.
Proving Sums and Divisibility: Step-by-step guides on how to structure and execute the two most common types of induction problems in the HSC.
Identifying Errors: Learning why a proof might look correct but is fundamentally flawed if one of the critical steps fails.

Let's explore the logic of induction.

Main Content

1. The Nature of Inductive Proof

Proof by mathematical induction is often compared to a line of falling dominoes. If you can prove that the first domino falls (the base case), and you can prove that if any one domino falls, it guarantees the next one will fall (the inductive step), then you have proven that all the dominoes will fall.

Every proof by mathematical induction MUST contain these three clearly defined steps:

The Statement: Let $P(n)$ be the proposition to be proved for integers $n \ge a$ (where $a$ is usually 1).
Step 1: The Base Case: Prove that $P(a)$ is true. Show that the formula works for the very first number.
Step 2: The Inductive Hypothesis and Step:
- Assume that $P(k)$ is true for some arbitrary integer $k \ge a$ . This is your inductive assumption.
- Prove that $P(k+1)$ is true, using the assumption that $P(k)$ is true.

If Step 1 and Step 2 are both valid, the statement is true for all integers $n \ge a$ by the principle of mathematical induction.

2. Proving Results for Sums

This is the most common application in the Extension 1 course. You will be asked to prove that the sum of a sequence equals a specific formula.

Example: Prove that $\sum_{r=1}^{n} (2r - 1) = n^2$ for $n \ge 1$ .

Step 1: Base Case ( $n=1$ )

LHS = $2(1) - 1 = 1$
RHS = $1^2 = 1$
Since LHS = RHS, $P(1)$ is true.

Step 2: Inductive Step

Assume $P(k)$ is true for some integer $k \ge 1$ : $\sum_{r=1}^{k} (2r - 1) = k^2$
Prove $P(k+1)$ is true: Required to prove (RTP): $\sum_{r=1}^{k+1} (2r - 1) = (k+1)^2$
Proof: LHS $= \sum_{r=1}^{k+1} (2r - 1)$ LHS $= \left( \sum_{r=1}^{k} (2r - 1) \right) + (2(k+1) - 1)$ (Splitting the sum into the first $k$ terms plus the $(k+1)$ th term) LHS $= k^2 + (2k + 2 - 1)$ (Substituting our assumption! This is the most important step) LHS $= k^2 + 2k + 1$ LHS $= (k+1)^2 =$ RHS.

Since $P(1)$ is true, and $P(k)$ implies $P(k+1)$ , by mathematical induction, the statement is true for all $n \ge 1$ .

3. Proving Divisibility Results

Divisibility proofs follow the exact same logical structure, but the algebra is slightly different.

Example: Prove $3^n + 7^n$ is divisible by 10 for all odd positive integers $n$ . Note: Because $n$ must be odd, we can define $n = 2m - 1$ for $m \ge 1$ , or test steps of $+2$ . Let's assume the question meant all odd integers. The base case is $n=1$ , and we must prove that if it holds for $k$ , it holds for $k+2$ .

Alternatively, a simpler standard HSC example: Prove $5^n - 1$ is divisible by 4 for $n \ge 1$ .

Assume for $n=k$ : $5^k - 1 = 4M$ (where $M$ is an integer). Therefore, $5^k = 4M + 1$ .
Prove for $n=k+1$ : $5^{k+1} - 1 = 4P$ (where $P$ is an integer).
Proof: $5^{k+1} - 1 = 5 \cdot 5^k - 1$ . Substitute the assumption: $= 5(4M + 1) - 1 = 20M + 5 - 1 = 20M + 4 = 4(5M + 1)$ . Since $M$ is an integer, $(5M+1)$ is an integer, so the expression is divisible by 4.

4. Identifying Errors in False Proofs

Not all proofs are valid! A critical skill is being able to spot why a "proof" is mathematically unsound. Usually, this happens when one of the two steps fails.

Example of a False Proof: Consider the proposition: $1 + 2 + 3 + \dots + n = \frac{1}{2}(n-1)(n+2)$ for $n \ge 1$ .

If you test the inductive step (assuming it works for $k$ and proving for $k+1$ ), the algebra actually works out perfectly! You can successfully "prove" the inductive step.
However, if you test the base case ( $n=1$ ): LHS = 1, but RHS = $\frac{1}{2}(0)(3) = 0$ . Since LHS $\neq$ RHS, the base case fails.

The dominoes are set up perfectly to knock each other down, but there is no first domino to start the chain reaction. Therefore, the entire proposition is false.

mini-FAQ page

Q: Do I have to write the concluding sentence at the end of the proof? A: Yes! Mathematical induction is a formal logical argument. Omitting the concluding statement (e.g., "Since P(1) is true and P(k) implies P(k+1)...") will result in a loss of marks in the HSC.

Q: In a sum proof, how do I know what the $(k+1)$ th term is? A: Look at the general term inside the summation (the sigma notation $\sum$ ). Replace the index variable with $(k+1)$ to generate the exact term you need to add to your assumption.

Q: What does it mean when a question asks for $n \ge 0$ ? A: It simply means your base case is $n=0$ instead of $n=1$ . Make sure you read the domain of the proposition carefully!

Common mistakes to avoid

Failing to explicitly state the assumption: You must write "Assume true for $n=k$ " and write down the equation you are assuming. If you do not explicitly state what you are assuming, the examiner cannot award you marks for using it.
Not identifying where you used the assumption: In the inductive step, it is highly recommended to write "(using assumption)" next to the line of algebra where you substitute your $P(k)$ expression. This proves to the marker you understand the logic.
Fudging the algebra: Markers know what the final line of your proof is supposed to look like. If your algebra doesn't actually lead to that final line, do not just skip to the end and pretend it works. You will lose marks for invalid logic.

Practice on Vu's Maths Hub

Mathematical induction is a skill that requires repetitive practice to master the algebraic tricks (especially for divisibility).

Perfect your proofs with our specialised resources on Vu's Maths Hub:

Master every variation of these questions with our comprehensive HSC Induction booklet.
Strengthen your general logical arguments with our HSC Proofs resources.
Test your ability to spot errors in false proofs by practicing with our detailed Worked Solutions.

Connect with me

Ready to guarantee full marks on your induction questions? Join Vu's Maths Hub today and gain access to our extensive collection of Maths Booklets, Worked Solutions, and Trial Papers tailored specifically to help you conquer the NSW HSC curriculum.