BrightPath Back to Course
Year 12 Maths

Proof by Mathematical Induction

Master the technique of mathematical induction to prove statements about natural numbers, including summation formulas and divisibility results.

What Is Mathematical Induction?

Mathematical induction is a method of proof used to establish that a given statement is true for all natural numbers (or all integers from some starting point). Think of it like an infinite chain of dominoes: if you knock over the first one, and each domino is guaranteed to knock over the next, then every domino falls.

The process has two essential parts:

1

Base Case

Show the statement is true for the initial value (usually n = 1).

2

Inductive Step

Assume the statement is true for n = k (the inductive hypothesis), then prove it is true for n = k + 1.

The Structure of an Induction Proof

Every induction proof follows a clear, structured format. In HSC exams, you should present your work using these headings:

  1. Step 1: State the proposition — Write "Let P(n) be the statement..." and clearly define what you are proving.
  2. Step 2: Base case — Test P(1). Show LHS = RHS or verify the condition holds.
  3. Step 3: Inductive hypothesis — "Assume P(k) is true for some integer k ≥ 1." Write out what this assumption gives you.
  4. Step 4: Inductive step — Prove P(k+1) is true. Use the assumption from Step 3 to reach the required result.
  5. Step 5: Conclusion — "Since P(1) is true and P(k) true implies P(k+1) true, by mathematical induction P(n) is true for all n ≥ 1."

Summation and Divisibility Proofs

Two of the most common types of induction proof in HSC Maths are summation proofs (proving a formula for 1 + 2 + ... + n, etc.) and divisibility proofs (proving that an expression is divisible by a given integer).

Summation Proofs

For the inductive step, add the (k+1)th term to both sides and simplify to show the formula holds for n = k + 1.

Divisibility Proofs

Express the (k+1) case in terms of the k case. Substitute the inductive hypothesis and factor to reveal the required divisor.

Key Vocabulary

Base Case

The first step of an induction proof where you verify the statement holds for the initial value (usually n = 1).

Inductive Hypothesis

The assumption that the statement is true for n = k, which you use to prove the n = k + 1 case.

Inductive Step

The core argument where you prove that P(k) being true implies P(k+1) is also true.

Proposition P(n)

The statement involving n that you aim to prove is true for all natural numbers.

Worked Examples

1

Prove by induction: 1 + 2 + 3 + ... + n = n(n + 1)/2 for all n ≥ 1.

Base case (n = 1): LHS = 1. RHS = 1(1 + 1)/2 = 1. LHS = RHS, so P(1) is true.

Inductive hypothesis: Assume P(k) is true: 1 + 2 + ... + k = k(k + 1)/2.

Inductive step (prove P(k+1)): We need to show 1 + 2 + ... + k + (k + 1) = (k + 1)(k + 2)/2.

LHS = k(k + 1)/2 + (k + 1) = (k + 1)[k/2 + 1] = (k + 1)(k + 2)/2 = RHS.

Conclusion: By mathematical induction, the statement is true for all n ≥ 1.

2

Prove by induction: 3n − 1 is divisible by 2 for all n ≥ 1.

Base case (n = 1): 31 − 1 = 2, which is divisible by 2. P(1) is true.

Inductive hypothesis: Assume 3k − 1 = 2m for some integer m.

Inductive step: 3k+1 − 1 = 3 · 3k − 1 = 3(2m + 1) − 1 = 6m + 3 − 1 = 6m + 2 = 2(3m + 1).

Since 3m + 1 is an integer, 3k+1 − 1 is divisible by 2.

Conclusion: By mathematical induction, 3n − 1 is divisible by 2 for all n ≥ 1.

3

Prove by induction: 12 + 22 + ... + n2 = n(n + 1)(2n + 1)/6 for all n ≥ 1.

Base case (n = 1): LHS = 1. RHS = 1(2)(3)/6 = 1. P(1) is true.

Inductive hypothesis: Assume 12 + 22 + ... + k2 = k(k + 1)(2k + 1)/6.

Inductive step: LHS for k+1 = k(k + 1)(2k + 1)/6 + (k + 1)2

= (k + 1)[k(2k + 1)/6 + (k + 1)] = (k + 1)[k(2k + 1) + 6(k + 1)] / 6

= (k + 1)(2k2 + 7k + 6) / 6 = (k + 1)(k + 2)(2k + 3) / 6 = RHS for k + 1.

Conclusion: By mathematical induction, the formula holds for all n ≥ 1.

Knowledge Check

Select the correct answer for each question. Click "Check Answer" to see if you are right.

Question 1

In a proof by induction, what is the first step you must complete?

Question 2

When proving 1 + 2 + ... + n = n(n+1)/2 by induction, what is the value of both sides when n = 1?

Question 3

In the inductive step, you assume P(k) is true. This assumption is called the:

Question 4

To prove 5n − 1 is divisible by 4 at the base case n = 1, what value do you calculate?

Question 5

In a divisibility proof by induction for 3n − 1 divisible by 2, after assuming 3k − 1 = 2m, you write 3k+1 − 1 as:

Key Concepts Summary

Year 12: Calculus Integration Year 12: Vectors in 2D