Induction

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.

Induction

Use induction to prove that 5 × 7ⁿ + 1 is divisible by 6, n ∈ ℤ⁺

Write statement in mathematical form

P(n) = 5 × 7ⁿ + 1 = 6A, A ∈ ℕ

2. Check for n = 1

P(1) = 5 × 7¹ + 1 = 36, which is divisible by 6

Assume true for n = k

4. Show true for n = k+1

5. Write concluding sentence

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ⁿ) − 1 is divisible by 6 for all positive integers.