8: Proof by Induction
- Page ID
- 23933
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
Mathematicians aren’t satisfied because they know there are no solutions up to four million or four billion, they really want to know that there are no solutions up to infinity.
attributed to Andrew Wiles (1953–), British mathematician
You are familiar with many of the properties of natural numbers, such as:
- the commutative laws: \(x + y = y + x\) and \(xy = yx\),
- the associative laws: \((x + y) + z = x + (y + z)\) and \((xy)z = x(yz)\), and
- the distributive laws: \(x(y + z) = xy + xz\) and \((y + z)x = yx + zx\).
These properties are also true for integers, for rational numbers, and for real numbers.
In this chapter, we discuss a very useful property of \(\mathbb{N}\) that is not true of \(\mathbb{Z}\) or \(\mathbb{Q}\) or \(\mathbb{R}\). It is often very useful for proving assertions about natural numbers, and requires an understanding of sets and predicates (which were introduced in Chapter 3), but not the full theory of First-Order Logic.