Unlike direct proofs, where the result follows as a logical step, mathematical induction is a form of indirect proof (the only one covered in the IB syllabus). Indirect proofs tend to require a ‘creative’ step, however through training one can recognise most forms of induction.

Proof by induction can always be split up into three components, that together prove the wanted statement:

Common types: f(n) > g(n), f(n) = g(n), f(n) < g(n), Σ, P(n) is a multiple / divisible.

^{n}+ 1 is divisible by 6, n ∈ ℤ

^{+}

- Write statement in mathematical form

^{n}+ 1 = 6A, A ∈ ℕ

^{1}+ 1 = 36, which is divisible by 6

- Assume true for n = k

Hence, since P (1) true and assuming P(k) true, we have shown by the principle of mathematical induction that P(k + 1) true. Therefore, 5 × (7^{n}) − 1 is divisible by 6 for all positive integers.

Induction

- Check for n = 1

4. Write concluding statement

Hence, since n = 1 is true and assuming n = k true, we have shown by the principle of mathematical induction that n = k + 1 true. Therefore,