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:
![induction](https://revisiontown.com/wp-content/uploads/2023/04/Screenshot-2023-04-16-at-5.07.19-PM-768x201.png)
Common types: f(n) > g(n), f(n) = g(n), f(n) < g(n), Σ, P(n) is a multiple / divisible.
- Write statement in mathematical form
- Assume true for n = k
![induction](https://revisiontown.com/wp-content/uploads/2023/04/Screenshot-2023-04-16-at-5.17.02-PM-300x58.png)
![induction](https://revisiontown.com/wp-content/uploads/2023/04/Screenshot-2023-04-16-at-5.18.57-PM-300x151.png)
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
![induction](https://revisiontown.com/wp-content/uploads/2023/04/Screenshot-2023-04-16-at-5.22.10-PM.png)
- Check for n = 1
![induction](https://revisiontown.com/wp-content/uploads/2023/04/Screenshot-2023-04-16-at-5.27.44-PM-300x80.png)
![induction](https://revisiontown.com/wp-content/uploads/2023/04/Screenshot-2023-04-16-at-5.27.51-PM-300x65.png)
![induction](https://revisiontown.com/wp-content/uploads/2023/04/Screenshot-2023-04-16-at-5.28.00-PM-300x265.png)
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,
![induction](https://revisiontown.com/wp-content/uploads/2023/04/Screenshot-2023-04-16-at-5.35.59-PM-300x64.png)