In this text we started by doing a little bit of sets and a little logic. The aim of these brief introductions was to get you — our reader — started proving things as quickly as possible. We continued with a some basic logical equivalence to show us how to prove cases, biconditionals and contrapositives, and how to work with quantified statements. We have put these methods to work on some basic results on parity and divisibility; while those result were not terribly deep, their simplicity made them good places to learn our proof basics. We will soon apply all 77 of proof skills to more general mathematical problems, but we will first introduce a more specialised, but still extremely useful proof method. Mathematical induction is a method for proving statements of the form
\begin{gather*}
\forall n \in \mathbb{N}, P(n).
\end{gather*}
The archetypal induction-proof example is the result
\begin{equation*}
\text{For all } n\in\mathbb{N}, 1+2+3+\cdots+n = \frac{n(n+1)}{2}.
\end{equation*}
or, to write it in a slightly more compact way
\begin{equation*}
\forall n \in \mathbb{N}, \sum_{k=1}^n k = \frac{n(n+1)}{2}
\end{equation*}
Warning7.0.1.The law of the instrument.
Like any tool, induction is not guaranteed to work everywhere. However, like any tool, it is useful to have and part of learning to use the tool is to understand when it might help and when it might not. There is a tendency when one learns a nice new mathematical method that one tries to apply it to every problem that one comes across. This is often summarised as the law of the instrument — being the tendency to always use the same tool, even when it isn’t the best tool for the job 78 . Anyway, with that caveat, the authors should get on with it and start talking about induction.
We still need to learn about proof by contradiction, but this author likes to leave that topic until the reader has had a chance to practice other proof methods.
There are also variations of this rule that make reference to hammers — when you have a fancy new hammer, everything is a nail.
