IB

# 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 × 7n + 1 is divisible by 6, n ∈ ℤ+
1. Write statement in mathematical form
P(n) = 5 × 7n + 1 = 6A, A ∈ ℕ
2. Check for n = 1
P(1) = 5 × 71 + 1 = 36, which is divisible by 6
1. 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 × (7n) − 1 is divisible by 6 for all positive integers.

Induction

1. Check for n = 1
2. Assume true for n = k
3. Show true for n = k +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,

is true for all positive integers.
Shares: