Summary

This chapter developed the principle of mathematical induction, the standard tool for proving a statement $P(n)$ true for every natural number $n$ (or every $n$ from some starting value $n_0$ onward).

• Natural numbers as the least inductive subset of $\mathbb{R}$. $N$ is the smallest subset of $\mathbb{R}$ containing $1$ and closed under adding $1$; this is exactly why a two-step verification suffices to cover every natural number.
• The principle itself. If $P(n_0)$ is true (base case) and $P(k) \Rightarrow P(k+1)$ for every $k \ge n_0$ (inductive step, using the inductive hypothesis $P(k)$), then $P(n)$ is true for every $n \ge n_0$.
• Summation formulas. Prove $S(k+1)=S(k)+a_{k+1}$ simplifies to the claimed closed form, using the inductive hypothesis to replace $S(k)$.
• Divisibility results. Express $g(k+1)$ in terms of $g(k)$ plus (or times) a visibly-divisible adjustment, so the inductive hypothesis's divisibility of $g(k)$ carries through to $g(k+1)$.
• Inequalities. Chain the inductive hypothesis together with auxiliary true inequalities; watch for statements whose base case must be shifted away from $n=1$ to some larger $n_0$ where the statement first becomes true.

Both the base case and the inductive step are indispensable -- a proof that skips either one is not a valid induction proof, however plausible the missing half might seem. …