Mathematical induction

Maths · Mathematical induction and binomial theorem. The idea in plain words, the rules to remember, the mistake to avoid and a worked example, written and checked by Mega Lecture.

Test this topic free All Maths topics

The idea

Mathematical induction is a method of proving that a statement S(n) is true for every positive integer n. Checking a few values is not a proof, so the method uses two conditions.

Condition 1: show that the statement is true for n = 1. Condition 2: assume it is true for n = k, and use this to prove it is true for n = k + 1. Then the truth passes from 1 to 2, from 2 to 3, and so on without end.

Some statements are false for the first few values, such as n! > 2ⁿ. In the extended form you start at another integer i in place of 1, and the result is then proved for all integers n ≥ i.

Rules to remember

Condition 1: S(1) is true (substitute n = 1 in both sides)
Condition 2: S(k) true implies S(k + 1) true, for any positive integer k
S(k + 1) is found by replacing n with k + 1 everywhere in the statement
Sum of a series: add the (k + 1)th term to both sides of S(k), then simplify the right side to the required form
Divisibility: write the S(k) expression as a multiple, e.g. 5^k − 1 = 4m, then show the (k + 1) expression has the same factor
Extended form: if S(i) is true and S(k) implies S(k + 1) for k ≥ i, then S(n) is true for all integers n ≥ i

Common mistake

Students leave out condition 1, or assume S(k + 1) in place of proving it. Both conditions are needed: condition 2 alone proves nothing if the statement is false at the starting value.

Worked example

Show by mathematical induction that 9ⁿ − 1 is divisible by 8 for every positive integer n.

n = 1: 9¹ − 1 = 8, which is divisible by 8, so condition 1 holds.
Assume it is true for n = k: 9^k − 1 = 8m for some integer m.
For n = k + 1: 9^k+1 − 1 = 9 × 9^k − 1 = 9(9^k − 1) + 8 = 9(8m) + 8.
= 8(9m + 1), which is divisible by 8, so condition 2 holds.

Answer: Both conditions hold, so 9ⁿ − 1 is divisible by 8 for all positive integers n.

Ask about this

Type what you are stuck on. The helper finds the explanation, worked examples and the notes to read, free and instant.

Keep going

← Probability Binomial theorem for positive integral index →Take a Maths test