“Induction makes you feel guilty for getting something out of nothing, and it is artificial, but it is one of the greatest ideas of civilization.” - Herbert S. Wilf
“The use of mathematical induction in demonstrations was, in the past, something of a mystery. There seemed no reasonable doubt that it was a valid method of proof, but no one quite knew why it was valid.” - Bertrand Russell
We assume you have already seen proofs by induction in your previous math classes. In this section, we focus on what induction actually is, and why it works.
Proofs by induction are common in mathematics and ubiquitous in Computer Science.
Example
Theorem: for every \(n\in\mathbb{N}\), \(\sum_{i=0}^{n} i \ = \ \frac{n(n+1)}{2}\). > Proof (by induction on the natural numbers): > >- Base case: If \(n = 0\) the equation holds because \(0 = 0\). >- Inductive case: Let \(n\geq 0\) and assume \(n\) satisfies the above equation. Then >\[ >\begin{array}{rcll} > \sum_{i=0}^{n+1} i & = & \left(\sum_{i=0}^{n} i\right) \ + n+1 \\[10pt] > & = & \frac{n(n+1)}{2} + n+1 & \mathrm{(by~IH)} \\[10pt] > & = & \frac{(n+1)((n+1)+1)}{2} \\ > \end{array} >\] >So \(n+1\) satisfies the equation. >QED
Suppose \(P\) is a property that natural numbers can have.
Example
Then induction is a way to prove that \(P\) holds for all natural numbers
Specifically, a proof by induction on the natural numbers is a proof that invokes the following property of the natural numbers, called the Induction Principle for \(\mathbb{N}\):
Definition
Induction Principle for \(\mathbb{N}\) > For any property \(P\) of natural numbers, if > >- \(P(0)\), and >- for every \(n{\in}\mathbb{N}\), if \(P(n)\) then \(P(n+1)\), > then for every \(n{\in}\mathbb{N},\ \ P(n)\). > Or equivalently, >\[ >P(0) \land \bigl(\forall n{\in}\mathbb{N}\ (P(n)\to P(n+1))\bigr) \ \to \ \bigl(\forall n{\in}\mathbb{N}\ P(n)\bigr) >\]
So,
The Example above is a proof by induction in this sense because:
Assume \(P(0)\), and that for every \(n{\in}\mathbb{N}\), if \(P(n)\) then \(P(n+1)\). Then:
Thus for every \(n{\in}\mathbb{N},\ \ P(n)\).
While this makes sense, any proof that ends with “etc.” is hand-waving, and is not a truly solid argument. Plus, the our intuition that this sequence of steps eventually shows every natural number has property \(P\) is essentially the same as our intuition that induction works, so it’s somewhat of a circular argument.
Maybe we can do better?
The following idea is attributed to Peano:
Definition
Here’s how to tell whether a set \(S\) is the set of natural numbers: >
>1. There exists an element \(z\in
S\) and a function \(s : S\to
S\) (such that) >2. \(z\) is
not in the range of \(s\) \(\qquad \qquad\) (i.e. \(z\) is not \(s(x)\) for any \(x\in S\)) >3. \(s\) is injective a.k.a. one-to-one. \(\qquad \qquad\) (i.e. if \(x\not=y\) then \(s(x) \not= s(y)\).) >4. For any property
\(P\), if \(P(z)\) and \(\forall x{\in}S\ (\, P(x)\to P(s(x))\,)\)
then \(\forall x{\in} S\ \
P(x)\).
> \(\qquad \qquad \qquad \qquad \qquad
\qquad \qquad\) (i.e. Induction works for \(S\).)
Then we define \(\mathbb{N}\) to be a set with these four properties. Since one of those properties is that induction works, we know that induction works for \(\mathbb{N}\)!
(This argument is completely rigorous, but perhaps not completely satisfying. We’ll consider one more approach to justifying Induction at the end of this section.)
We can also do induction starting at 1, at 2, etc. \[ P(1) \land \bigl(\,\forall n{\geq 1}\ (P(n){\to}P(n+1))\,\bigr) \ \to \ \bigl(\forall n{\geq}1\ P(n)\bigr) \] \[ P(2) \land \bigl(\,\forall n{\geq 2}\ (P(n){\to}P(n+1))\,\bigr) \ \to \ \bigl(\forall n{\geq}2\ P(n)\bigr) \] We can justify the first as follows:
In general, we can apply induction to any set which is isomorphic to \(\mathbb{N}\).
Sometimes, it seems like we need something “stronger” than the usual induction principle.
Example
The following proof has a flaw: > >Theorem: Every natural number \(n\geq 2\) is a product of primes. > >Proof (by induction on the natural numbers): > >- Base case: If \(n = 2\), the factorization is just \(2\). > >- Inductive case: Let \(n\geq 2\) and assume \(n\) is a product of primes. We must show that \(n+1\) is a product of primes. > > - If \(n+1\) is prime, we are done. > - If \(n+1\) is not prime, then \(n+1 = ab\) with > \(2 \leq a,b \leq n\). By the Inductive Hypothesis, \(a\) and \(b\) are both products of primes, so \(n+1 = ab\) is too. > > In either case, though, \(n+1\) is a product of primes. >QED
The problem is that we are applying the inductive hypothesis to \(a\) and \(b\), but we only assumed that \(n\) was a product of primes. To make this proof work, we need to assume that all numbers between 2 and \(n\) are product of primes, not just \(n\).
One option is to switch from the Induction Principle to the Strong Induction Principle:
Definition
Strong Induction Principle for \(\mathbb{N}\) > For any property \(P\) of natural numbers, if > >- P(0) >- for every \(n\geq 1\): if \(P(k)\) for all \(k<n\) then \(P(n)\). > Then \(\forall n\in\mathbb{N}\ P(n)\). > >— > Equivalently, >\[ >\forall n{\in}\mathbb{N}\ \biggl((\forall k{<}n\ P(n))\to P(n)\biggr)\ \ \ \to \ \ \ \bigl(\forall n{\in}\mathbb{N}\ P(n)\bigr) >\]
(The symbolic form might look like it’s missing the base case, but when \(n\) is zero the assumption \(\forall k{<}n\ P(n)\) is trivially true and doesn’t provide any help in proving \(P(0)\); as a result, we normally have to prove the \(n=0\) case with a separate argument.)
Now we can fix our proof:
Example
Theorem: Every natural number \(n\geq 2\) is a product of primes. > Proof (by strong induction on the natural numbers): > >- Base case: If \(n = 2\), the factorization is just \(2\). > >- Inductive case: Let \(n>2\) and assume every number between 2 and \(n\) inclusive is a product of primes . We must show that \(n+1\) is a product of primes. > > - If \(n+1\) is prime, we are done. > - If \(n+1\) is not prime, then \(n+1 = ab\) with \(2 \leq a,b \leq n\). By the Inductive Hypothesis, \(a\) and \(b\) are both products of primes, so \(n+1 = ab\) is too. > > In either case, though, \(n+1\) is a product of primes. >QED
Of course, with a little more thought, we can see that we could have gotten the same result with the standard Induction Principle. In fact, any proof that uses Strong Induction could be done with the standard Induction Principle by strengthening the induction hypothesis; strong induction isn’t actually stronger! (And the Strong Induction Principle can be proved correct using the Induction Principle.)
Example
Theorem: For every natural number \(n\geq 2\), every number between 2 and \(n\) inclusive is a product of primes > Proof (by “standard” induction on the natural numbers): > >- Base case: If \(n = 2\), the factorization is just \(2\). > >- Inductive case: Let \(n>2\) and assume every number between 2 and \(n\) inclusive is a product of primes . We must show that every number between 2 and \(n{+}1\) inclusive is a product of primes . > > We only need to check \(n{+}1\); everything else was already assumed to work! > > - If \(n+1\) is prime, we are done. > - If \(n+1\) is not prime, then \(n+1 = ab\) with \(2 \leq a,b \leq n\). By the Inductive Hypothesis, \(a\) and \(b\) are both products of primes, so \(n+1 = ab\) is too. > > In either case, though, \(n+1\) is a product of primes. >QED
Finally, here is one more way we could define the natural numbers:
Definition
\(\mathbb{N}\) can alternatively be defined as the smallest set \(S\) such that > >1. \(\mathsf{z}\in S\) \(\qquad \qquad\) (\(S\) contains zero) >2. If \(x\in S\) then \(\mathsf{s}x\in S\) \(\qquad \qquad\) (\(S\) is closed under successor)
This definition is perfectly rigorous. (One can show that there really is a unique smallest such set; it is equal to the infinite intersection of all sets \(S\) with those two properties.) Intuitively, it defines the natural numbers as the set of strings \[ \{\mathsf{z},\mathsf{sz},\mathsf{ssz},\mathsf{sssz},\ldots\} \] (though the definition doesn’t appeal to informal ideas like “…”). Since this is basically unary notation, all the usual operations like + and < can be defined on these strings; this set really is equivalent to what we think of as the natural numbers.
The cool thing about this definition is that we can prove that induction works!
If \(P(\mathsf{z})\) and \(\bigl(\forall n{\in}\mathbb{N},\ \ P(n)\to P(\mathsf{s}n)\bigr)\), then \(\forall n{\in}\mathbb{N}\ \ P(n)\).
Proof: 1. Suppose \(P(\mathsf{z})\) and that \(\forall n\in\mathbb{N}\ \ \bigl(P(n)\to P(\mathsf{s}n)\bigr)\) . 2. Define \[ Y \ :=\ \{\ n\in\mathbb{N}\ |\ P(n)\ \}. \] 3. Obviously \(Y \subseteq \mathbb{N}\). 4. But \(Y\) contains \(\mathsf{z}\) (because we assumed \(P(\mathsf{z})\) is true), 5. and \(Y\) is closed under successor (because if \(n\in Y\) then \(P(n)\) so \(P(\mathsf{s}n)\) and hence \(\mathsf{s}n\in Y\). 6. Since \(\mathbb{N}\) was defined as the smallest such set, it must be that \(\mathbb{N}\subseteq Y\). 7. Since \(Y \subseteq \mathbb{N}\) and \(\mathbb{N}\subseteq Y\), we conclude \(Y = \mathbb{N}\). 8. But all the members of \(Y\) of satisfy \(P\), so
\[ \forall n{\in}\mathbb{N}\ \ P(n). \] QED
Previous: 2.3 Predicate Rules of Natural Deduction
Next: 3.2 Proofs for Humans