Your weak spots

Insights load after your first practice round.

Module 5 · L2 of 20 ~40 min ⚡ +95 XP available

The Principle of Mathematical Induction

Imagine an infinite line of dominoes. Push the first one — they all fall. Mathematical induction works exactly the same way: prove the first case works, then prove each case knocks over the next. In this lesson you'll master the three-step induction template that unlocks Module 5 completely.

Today's hook — The formula $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ works for $n = 1, 2, 3, \ldots$ Before the lesson: verify it for $n = 1$ and $n = 2$ by hand. Then ask yourself: how could you ever prove it works for ALL positive integers?

0/5QUESTS

Recall — your gut answer first

+5 XP warm-up

Verify that $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ holds for $n = 1$ and $n = 2$ by substituting directly. Then write: could you check every positive integer this way? Why or why not?

auto-saved

Think first — the domino analogy

+5 XP to read

Mathematical induction is logically identical to this domino argument:

The first domino falls (base case: the statement is true for $n = 1$).
Each domino knocks over the next (inductive step: if true for $n = k$, prove true for $n = k+1$).

If both facts are established, every domino must fall — that is, the statement is true for every positive integer. The brilliance is that the inductive step handles infinitely many cases with one algebraic argument.

Why it works logically. Step 1 guarantees $n=1$ is true. Step 2 then gives $n=2$ (since $k=1$ implies $k+1=2$), then $n=3$, then $n=4$, and so on without end. Together they cover all $n \geq 1$.

What you'll master

Know

Key facts

The three steps of induction: base case, inductive hypothesis, inductive step
The standard concluding statement required in the HSC
The base case value depends on the domain of the statement

Understand

Concepts

Why both base case and inductive step are essential (removing either breaks the proof)
The logical structure: base case + inductive step $\Rightarrow$ all cases
The difference between assuming for $n = k$ and proving for $n = k+1$

Can do

Skills

Write a complete three-step induction proof with proper notation
Correctly state the inductive hypothesis
Write the required HSC concluding sentence

Key terms

Proof by inductionA proof technique for statements about all integers $n \geq n_0$ using a base case and an inductive step.

Base caseVerify the statement is true for the smallest value in its domain, usually $n = 1$ (but sometimes $n = 0$ or $n = 2$).

Inductive hypothesisThe assumption that the statement is true for $n = k$, written as: "Assume the statement holds for $n = k$."

Inductive stepUsing the inductive hypothesis to prove the statement for $n = k + 1$. This is the main algebraic work of the proof.

$n = k$The case you assume is true. Always use the letter $k$ (not $n$) when stating the hypothesis to avoid confusion.

$n = k+1$The case you must prove using the assumption for $n = k$.

The three steps of induction

core concept

Every induction proof has exactly the same three-step structure. Memorise this template — it is your HSC blueprint.

INDUCTION TEMPLATE

Step 1 — Base Case: Prove the statement is true for $n = 1$ (or the smallest relevant value). Show LHS $=$ RHS explicitly.

Step 2 — Inductive Hypothesis: Assume the statement is true for $n = k$, where $k$ is a positive integer. Write the assumed equation clearly.

Step 3 — Inductive Step: Using the inductive hypothesis, prove the statement is true for $n = k+1$. Start from one side of the $n=k+1$ equation and use algebra + hypothesis to reach the other side.

Conclusion: "By the principle of mathematical induction, the statement is true for all integers $n \geq 1$."

HSC marking note. You must explicitly state all three steps and write a conclusion. Markers award separate marks for the base case, the hypothesis statement, the algebraic inductive step, and the conclusion. Missing any one costs marks.

Every induction proof has exactly the same three-step structure. Memorise this template — it is your HSC blueprint.

Pause — copy the complete three-step induction template (base, hypothesis, step) plus the required HSC conclusion sentence verbatim into your book.

Quick check: In a proof by induction, the inductive hypothesis is the statement that:

How to execute the inductive step

core concept

We just saw the three-step induction template: base case, inductive hypothesis (assume for $n=k$), inductive step (prove for $n=k+1$), plus a mandatory conclusion. That raises a question: exactly how do you manipulate the $k+1$ case so the hypothesis slots in and the algebra closes? This card answers it → add the $(k+1)$-th term to both sides of the hypothesis, combine over the common denominator, then factorise $(k+1)$.

The inductive step is the algebraic heart of the proof. The strategy is:

Write the LHS for $n = k+1$. For a sum formula, this is the sum to $k+1$ terms.
Split off the last term. Write the sum to $k+1$ terms as (sum to $k$ terms) + $(k+1)$-th term.
Apply the inductive hypothesis. Replace the "sum to $k$ terms" with the assumed formula.
Simplify algebraically until you reach the RHS for $n = k+1$.

For the formula $\displaystyle\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$, the inductive step looks like this:

LHS for $n=k+1$: $\displaystyle\sum_{i=1}^{k+1} i = \underbrace{\sum_{i=1}^{k} i}_{\text{use hypothesis}} + (k+1)$

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

This equals RHS with $n = k+1$. $\checkmark$

Key technique. When you apply the inductive hypothesis, always write a clear note: "by the inductive hypothesis." This signals to the marker that you know exactly where you used the assumption.

The inductive step is the algebraic heart of the proof. The strategy is:

Pause — copy the four-step execution strategy: write LHS for $k+1$, split off the last term, apply hypothesis, simplify to reach the target RHS into your book.

Did you get this? True or false: in the inductive step for a sum formula, you split the sum to $k+1$ terms into (sum to $k$ terms) plus the $(k+1)$-th term, then apply the hypothesis.

Worked examples · 3 in a row, reveal as you go

PROBLEM 1 · SUM FORMULA

Prove by mathematical induction that $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ for all positive integers $n$.

Base case ($n = 1$): LHS $= 1$. RHS $= \dfrac{1(2)}{2} = 1$. LHS $=$ RHS. $\checkmark$ True for $n = 1$.

Substitute $n = 1$ into both sides and verify they are equal. This is the foundation of the entire proof.

PROBLEM 2 · SPOT THE ERROR

A student writes: "Assume true for $n = k$. Then it's true for $n = k+1$ by the same reasoning. Since we showed it works, the proof is complete." What is wrong?

Error 1: There is no base case. The student never proved the statement for any specific value of $n$.

Without a base case, the domino chain starts nowhere. Even if the inductive step is valid, there's no first domino to begin the chain.

PROBLEM 3 · BASE CASE $n = 0$

Prove by induction that $1 + 3 + 5 + \cdots + (2n-1) = n^2$ for all positive integers $n$. (The sum of the first $n$ odd numbers.)

Base case ($n = 1$): LHS $= 1$. RHS $= 1^2 = 1$. LHS $=$ RHS. $\checkmark$

The first odd number is $2(1)-1 = 1$, so the LHS with one term is just $1$. This equals $1^2 = 1$.

Fill the gap: In the inductive step for $\sum_{i=1}^n i = \dfrac{n(n+1)}{2}$, after applying the hypothesis we get $\dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k+\,}$$)}{2}$.

Misconceptions to fix · the 3 traps that cost marks

Trap 01

Forgetting the base case

Without a base case, the inductive step proves nothing. Imagine an inductive step saying "if domino $k$ falls, domino $k+1$ falls" — if no domino ever starts falling, the argument is useless. Always prove the first case explicitly.

Trap 02

Assuming what you're trying to prove

In the inductive step, you may only assume the formula for $n = k$. You cannot assume it for $n = k+1$ — that is what you are trying to prove. Starting with the $n=k+1$ formula and working backwards is circular reasoning and scores zero.

Trap 03

Using $n$ in the hypothesis

Write the inductive hypothesis using the letter $k$, not $n$. Writing "assume true for $n$" is ambiguous — $n$ is already the variable in the statement. The convention is: $k$ for the assumed case, $k+1$ for the target case.

Did you get this? True or false: you can write a valid induction proof that has an inductive step but no base case, as long as the algebra in the step is correct.

Work mode · how are you completing this lesson?

Activities · practice with the ideas

State the three steps of proof by mathematical induction in your own words.

For the statement $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$, write out the inductive hypothesis (Step 2) in full.

Verify the base case ($n=1$) for the formula $1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$.

In a student's induction proof, the "hypothesis" reads: "Assume $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$." Identify the error in notation.

Explain in one sentence why an induction proof without a base case is invalid, using the domino analogy.

Odd one out: Three of these are required components of a valid induction proof. Which one is NOT a required component?

Revisit your thinking

At the start of this lesson you verified $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$ for $n = 1$ and $n = 2$, and asked how you could ever prove it for ALL positive integers.

Now you know: the base case handles $n = 1$, and the inductive step proves that each true case forces the next. Together, they cover all $n \geq 1$ with a finite argument.

auto-saved

Multiple choice

+5 XP per correct · +25 XP all-correct

Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.

Short answer

UnderstandBand 32 marks

Q1. State the three steps of proof by mathematical induction. (2 marks)

auto-saved

UnderstandBand 42 marks

Q2. Explain why the base case is necessary in an induction proof. Use the domino analogy in your answer. (2 marks)

auto-saved

ApplyBand 54 marks

Q3. Prove by mathematical induction that $1 + 3 + 5 + \cdots + (2n-1) = n^2$ for all positive integers $n$. (4 marks)

auto-saved

Comprehensive answers (click to reveal)

Activity answers:

1. Step 1: Prove true for $n=1$. Step 2: Assume true for $n=k$. Step 3: Prove true for $n=k+1$ using the hypothesis. Conclude.

2. "Assume true for $n = k$: $1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$."

3. LHS $= 1^2 = 1$. RHS $= \dfrac{1(2)(3)}{6} = 1$. LHS $=$ RHS. $\checkmark$

4. The variable $n$ is already used in the statement. The hypothesis must use a different letter, conventionally $k$: "Assume true for $n = k$: $1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$."

5. Without the base case, there is no first domino to push — the inductive step can only show that if one falls the next falls, but nothing guarantees the first ever falls.

Q1 (2 marks): Step 1: prove true for $n = 1$ [½]. Step 2: assume true for $n = k$ [½]. Step 3: prove true for $n = k+1$ using step 2 [½]. Conclude with the principle of mathematical induction [½]. Award 1 for two correct steps, 2 for all three steps + conclusion.

Q2 (2 marks): The inductive step only shows that IF one domino falls, the next falls [1]. Without a base case (the first domino), there is no starting point and the chain never begins — the argument proves nothing [1].

Q3 (4 marks):
Base case ($n=1$): LHS $= 1$, RHS $= 1^2 = 1$. $\checkmark$ [1]
Hypothesis: Assume $1 + 3 + \cdots + (2k-1) = k^2$ for some $k \geq 1$. [1]
Step: LHS for $k+1$: $1 + 3 + \cdots + (2k-1) + (2k+1) = k^2 + (2k+1)$ [by hypothesis] $= (k+1)^2$. $\checkmark$ [1]
Conclusion: By the principle of mathematical induction, the result holds for all positive integers $n$. $\blacksquare$ [1]

Boss battle · The Induction Master

earn bronze · silver · gold

Five timed questions. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.

⚔ Enter the arena

Science Jump · platform challenge

Climb platforms by answering induction questions. Lighter alternative to the boss.

Mark lesson as complete

Tick when you've finished the practice and review.

← Lesson 1 · Introduction to Mathematical Proof Lesson 3 · Induction for Sum of First $n$ Integers →

Module overview · Extension 1 · Checkpoint 1