COMP 1002 Unit 6 overview
This unit focuses on one of the most common and useful proof techniques, mathematical induction, and its variants. Here you will learn one powerful way of proving statements of the form ∀ n ∈ ℕ P(n), and see it used to prove some important theorems about numbers, as well as simpler puzzles.
Readings
Most of the material in this unit is covered in sections 5.1 and 5.2 in the textbook.
Learning objectives
The main objective of this unit is to learn to write proofs using mathematical induction, and its (equivalent) variants well-ordering principle and strong induction. You will be expected to be able to do proofs on the final exam that will be similar to proofs in the practice problem set and labs. You will also learn why there are infinitely many prime numbers, and the fundamental theorem of arithmetic that every number can be written as a product of primes (uniquely up to the order).
Make sure to practice writing proofs, rather than just reading examples and watching videos! There are a lot of subtle details that you might not notice unless you are actually writing a proof yourself.
Vocabulary
You need to know the meaning of the following terminology (and respective notation):
- Well-ordering principle
- Mathematical induction, strong induction
- Base case, induction hypothesis, induction proof, predicate being proven.