Lecture 6: Induction, I

\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,\vert\,#2\}} \newcommand{\size}[1]{\vert#1\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \)

Administrivia

We're having some real issues with homework legibility, and so are adopting a new policy: Starting with the homework assigned today (and due next Wednesday), you'll receive “one-point coupon” for each exercise prepared using LaTeX, e.g., if you receive a 3 point deduction, the coupon will reduce that penalty by 1 point, and only two points will be deducted.

Induction, I

Today begins a three-lecture unit on proofs by induction. The goal is to improve your familiarity and confidence with proofs by induction. Yes, we really do expect you to master and apply this skill! Like any such skill, the way to learn is through observation, mimicry, practice, practice, and practice.

The basic idea is to prove a universal statement $\forall n,\, \varphi(n)$ we show the basis case $\varphi(0)$, and inductive step $\varphi(n) \limplies \varphi(n+1)$ for all $n$. We can then think of the inductive step as showing us how to build a proof of $\varphi(1)$ from our proof of $\varphi(0)$, how to build a proof of $\varphi(2)$ from a proof of $\varphi(1)$, etc.

Another way to think about this is that if a universal statement $\forall n,\, \varphi(n)$ is false, then the set of counter-examples $C = \comprehension{n\in\mathbb{N}}{\lnot \varphi(n)}$ is non-empty, and so must have a least element. The hypotheses of a proof by induction rule out the possibility that $0$ is a least counter-example, or that a successor is the least-counterexample, for the latter, using the fact that if $S \, n$ is the least counterexample of $\forall n,\, \varphi(n)$, then $\varphi(n)$ must be true.

In a slight variation on this theme, we want to prove an almost-universal statement, e.g., $\forall n \geq k, \varphi(n)$. In such a case, it is easier, as well as conceptually more natural, to do an induction on the formula $\varphi(n)$ with a basis case $n = k$, rather than trying to prove the slightly more complicated $n > k \limplies \varphi(n)$ starting at $0$.

But whatever the precise details, a proof by induction should be written as follows:

  1. Statement: Begin with a precise statement of the formula to be proven, and the variable you'll be inducting over.
  2. The Basis Case: State the number $k$ where you're starting your induction, and the formula $\varphi(k)$ to be proven, and then prove it.
  3. The Induction Case: State the inductive hypothesis $\varphi(n)$, and the formula $\varphi(n+1)$ to be proven. Prove the result, clearly indicating when the inductive hypothesis (often abbreviated IH) is used.

A simple sum

There's a story that's told about the famous mathematician Carl Friedrich Gauss, as a young boy. He was assigned the busy-work task of computing $1 + 2 + \ldots + 100$, in the hope it would keep him occupied for a while. It didn't. Instead, he wrote

\begin{align*} x &= \phantom{00}1 \,+ \, \phantom{0}2 \, + \, \ldots \, + \, 99 \, + \, 100\\ x &= 100 \, + \, 99 \, + \, \ldots \, + \, \phantom{0}2 \, + \, \phantom{00}1\\ \end{align*}

and then added the two lines,

\begin{align*} 2 \cdot x &= 101 + 101 + \ldots + 101 + 101\\ 2 \cdot x &= 100 \mult 101\\ x &= 50 \mult 101\\ x &= 5050 \end{align*}

Applying the same technique more generally, with $n$ rather than $100$, we arrive at the following summation formula:

\begin{equation*} 1 + 2 + \ldots + n = n \mult (n+1) \, / \, 2 \end{equation*}

Such sums occur often, and so we have a special notation for them:

\begin{equation*} \sum_{i=1}^n a_i = a_1 + a_2 + \ldots + a_n \end{equation*}

and with this, can recast our formula as follows:

Theorem 6.1 For all $n \geq 1$, \begin{equation*} \sum_{i=1}^n i = {n (n+1) \over 2} \end{equation*}

Proof By induction on $n$.

Basis Case: $n=1$. We must show $\sum_{i=1}^1 = 1 \mult (1+1) \, / \, 2$, but this is trivial, as both equal $1$.

Inductive Case: Our inductive hypothesis is $\sum_{i=1}^n i = n (n+1) \, / \, 2$, and we must prove $\sum_{i=1}^{n+1} i = (n+1) (n+2) \, / \, 2$. We compute as follows:

\begin{align*} \sum_{i=1}^{n+1} i &= \sum_{i=1}^{n} i + (n+1)\tag{Break off last term of sum} \\ &= n (n+1) \, / \, 2 +(n+1) \tag{By IH}\\ &= (n+1) (n \,/\, 2 + 1)\tag{Factor out $(n+1)$}\\ &= (n+1) (n \,/\, 2 + 2 \,/\, 2)\\ &= (n+1) (n+2) \,/\, 2 \end{align*}

$\Box$ Theorem 6.1

Of course, you may ask why it was deemed necessary to give an inductive proof, as Gauss's demonstration seems perfectly clear. Much of this has to do with our standards of proof: Gauss's argument is suggestive, with ellipses used to suggest a process that differs in small but predictable ways as we compute summations up to different $n$. The inductive proof avoids “suggestiveness” in favor of axiomatic rigor. Moreover, we'll see that there's a real value in learning both the sources of mathematical inspiration (like Gauss's) and the formal tools needed to rigorously prove the conjectures that flow from these inspirations. This is a pattern we'll see repeated through the course.

Another summation

Gauss's strategy for summing the first $n$ integers involved a simple insight. But sometimes, rather than working from the bottom up, i.e., from a problem to an answer, we can get a top-down insight, by working from an answer to a problem. For example, let's suppose we wanted to develop a summation formula like this: $$\sum_{i=1}^n f(i) = n^2.$$ How would we proceed? Naturally enough, by considering the difference between two consecutive squares. Let's first reason geometrically:

diagram of squares

From this, we can see that passing from the square of $n-1$ to the square of $n$ requires adding two edges of size $n-1$ and a corner piece of size $1$. Thus $(n-1)^2 + 2 \mult (n-1) + 1 = n^2$, a fact we can easily verify algebraically.

\begin{align*} (n-1)^2 + 2 \mult (n-1) + 1 &= (n^2 - 2 n + 1) + 2 n - 2 + 1 \\ &= n^2 - 2 n + 1 + 2 n -1\\ &= n^2 \end{align*}

As $2\mult(n-1)+1 = 2 n -1$, we conjecture:

Theorem 6.2 For all $n\geq 1$,

\begin{equation*} \sum_{i = 1}^n (2 i - 1) = n^2 \end{equation*}

Note: Summation binds more tightly than ordinary arithmetic operations, necessitating our use of parentheses above.

Proof By induction on $n$.

Basis Case: $n=1$. We have to show $\sum_{i=1}^1 (2 i - 1) = 1^2$. This is trivial, as both equal $1$.

Inductive Case: Our inductive hypothesis is $\sum_{i = 1}^n (2 i - 1) = n^2$, and we have to show $\sum_{i = 1}^{n+1} (2 i - 1) = (n+1)^2$. To that end, we compute

\begin{align*} \sum_{i = 1}^{n+1} (2 i - 1) &= \sum_{i = 1}^{n} (2 i - 1) + 2 \mult(n+1) - 1\tag{Break off last term of sum.}\\ &= n^2 + 2n +2 -1\tag{By IH.}\\ &= n^2 + 2n + 1\\ &= (n+1)^2 \end{align*}

$\Box$ Theorem 6.2

There's a third approach we can take to obtain the same result, which involves building a small amount of general purpose machinery that we can use to manipulate sums.

*Exercise 6.3 Prove $\sum_{i=1}^n 1 = n$ for all $n \geq 1$ by induction on $n$.

Theorem 6.4 For all $n\geq 1$,

\begin{equation*} \sum_{i=1}^n (a_i + b_i) = \sum_{i=1}^n a_i + \sum_{i=1}^n b_i \end{equation*}

Proof By induction on $n$.

Basis Case: $n=1$. We have to show $\sum_{i=1}^1 (a_i + b_i) = \sum_{i=1}^1 a_i + \sum_{i=1}^1 b_i$, which follows from the observation that both equal $a_1 + b_1$.

Inductive Case: We assume

\begin{equation*} \sum_{i=1}^n (a_i + b_i) = \sum_{i=1}^n a_i + \sum_{i=1}^n b_i \end{equation*}

as our inductive hypothesis, and must show

\begin{equation*} \sum_{i=1}^{n+1} (a_i + b_i) = \sum_{i=1}^{n+1} a_i + \sum_{i=1}^{n+1} b_i. \end{equation*}

To that end,

\begin{align*} \sum_{i=1}^{n+1} (a_i + b_i) &= \sum_{i=1}^n (a_i + b_i) + (a_{n+1} + b_{n+1}) \tag{Breaking off the last term.}\\ &= \sum_{i=1}^n a_i + \sum_{i=1}^n b_i + a_{n+1} + b_{n+1} \tag{By IH.}\\ &= (\sum_{i=1}^n a_i + a_{n+1}) + (\sum_{i=1}^n b_i + b_{n+1})\\ &= \sum_{i=1}^{n+1} a_i + \sum_{i=1}^{n+1} b_i \end{align*}

$\Box$ Theorem 6.4

*Exercise 6.5 Prove $\sum_{i=1}^n c \mult a_i = c \mult \sum_{i=1}^n a_i$ for all $n \geq 1$ by induction on $n$.

These last few facts enable us to deal with summations such as $\sum_{i = 1}^{n+1} (2 i - 1)$ by distributing the summation across sums (or differences), and multiplication (or division) by a constant, and then finally appealing to a small list of standard summation formula. Thus,

\begin{align*} \sum_{i=1}^n (2 i - 1) &= \sum_{i=1}^n 2i - \sum_{i=1}^n 1 \\ &= 2 \sum_{i=1}^n i - n\\ &= 2 n (n+1)/2 -n\\ &= n (n+1) - n\\ &= n^2 + n - n\\ &= n^2 \end{align*}

Exercise 6.6 Compute $\sum_{i=1}^n (3i+4)$.

Exercise 6.7 Compute $\sum_{x=1}^n \sum_{y=1}^n(x+y-1)$.

Exercise 6.8 This sort of approach can be used to derive new summation formula. For example, by extending from two dimensions to three the approach we used to guess $\sum_{i = 1}^n (2 i - 1) = n^2$, we could guess $\sum_{i=1}^n 3 (i-1)^2 + 3(i-1) + 1 = n^3$.

The Peano Axioms

We'll see soon enough that induction isn't just for the natural numbers, but the natural numbers and their properties provide the paradigmatic context for learning about proofs by induction

As we mentioned in the first lecture, $\mathscr{L}_{\text{PA}} = \set{S,+,\times,0,\le}$, i.e., the language of Peano arithmetic includes the constant symbol $0$, a unary function symbol $S$, binary function symbols $+$ and $\times$, and a binary relation symbol $\le$. The axioms come in several groups.

I strongly recommend that you work through this material out of class, providing the necessary inductive proofs. Not only is it good practice, there's something intensely satisfying about revisiting these old results, and proving for yourself what you've thus far had to take on authority and intuition.

Successor axioms

The properties of $S$ are critical:

The definition of $+$

The addition function $+$ is defined here by induction on its first argument, and that means that the definition is asymmetric in how it handles the arguments of $+$. A first crucial step in developing the theory is to re-establish that symmetry.

The definition of $\times$

Note again the asymmetry in how the arguments of $\times$ are handled by this definition.

The definition of $\leq$

The elementary theory of arithmetic

In this section, we're just going to state a sequence of lemmas and theorems, each of which can be proven by induction, which build up the standard properties of the natural numbers. It is worthwhile working through each, as a way of practicing this proof technique.

The first two lemmas establish symmetry in how $S$ and $+$ interact:

Lemma 6.9 $\forall n,\, n+0 = n$.

Lemma 6.10 $\forall n\,m,\, n+S\,m = S \, (n+m)$.

This sets us up to prove the commutative and associative laws for addition:

Theorem 6.11 (The Commutative Law for Addition) $\forall n\, m,\, n+m = m+n$.

Theorem 6.12 (The Associative Law for Addition) $\forall n\, m\, p,\, n + (m+p) = (n+m) + p$.

Both of these can be proven by induction on $n$.

Next, we establish symmetry in how $S$ and $\times$ interact.

Lemma 6.13 $\forall n,\, n\times 0 = 0$.

Lemma 6.14 $\forall n\,m,\, n \times S\,m = n + (n\times m)$.

As before, we can use to prove commutative, associative, and distributive laws for multiplication:

Theorem 6.15 (The Commutative Law for Multiplication) $\forall n\, m,\, n\times m = m \times n$.

Theorem 6.16 (The Associative Law for Multiplication) $\forall n\, m\, p,\, n \times (m \times p) = (n\times m) \times p$.

Theorem 6.17 (The Distributive Law for Multiplication over Addition) $\forall n\, m\, p,\, n \times (m + p) = (n\times m) + (n \times p)$.