1.1 Induction

This week first involves a little bit more about statements, namely those that involve the natural numbers \(\mathbb{N}\). Suppose we have a statement \(P(n)\) which depends on a natural number \(n\). If we want to prove this true for all natural numbers, we use the principle of mathematical induction.

Firstly, let \(\Lambda \subseteq \mathbb{N}\) be the set of all \(n \in \mathbb{N}\) such that \(P(n)\) is true. Then, to prove something by induction, we use the following procedure:

1. Show \(1 \in \Lambda\).
2. Assume \(k \in \Lambda\) for some \(k \in \mathbb{N}\). Prove \(k + 1 \in \Lambda\).

If these two steps are satisfied, then \(\Lambda = \mathbb{N}\), and \(P(n)\) holds for all natural numbers \(n\). You may come across different styles of inductive proofs from different lecturers at Bath, but as long as you write everything logically, these are fine for this course too!