Proof by mathematical induction
Mathematical induction allows us to prove each of an infinite sequence of logical statements, p1, p2, ..., is true. The argument involves two steps:
- Basis step: Prove p1 is true.
- Inductive step: For a fixed i ≥ 2 value, assume pi-1 is true and prove pi is true.
If both steps are done successfully, the conclusion is that p1, p2, ... are all true.
But how can we make this conclusion? The idea is that we have shown p1 is true and that each pi is true assuming pi-1 is true. Therefore, let i = 1, then p2 is true. Let i = 2, then p3 is true. Let i = 3, then p4 is true. This pattern continues indefinitely, so each pn must be true.
Mathematical induction can be thought of as an infinite line of dominoes standing on their edges. If you knock one over, it falls into the next, which falls into the next, which falls into the next, and on and on.
This discussion is admittedly a bit abstract, so let's actually do some proofs...
