Andrew Cooper

Here’s a nice fact about the natural numbers:

Well-Ordering Principle. Every nonempty collection of natural numbers has a least element.

Observe, before we prove this, that a similar statement is not true of many sets of numbers. The interval $(0,1)$, for example, has no least element. The set of even integers has no least element. The set of natural numbers has no greatest element.

Proof. We’ll prove the contrapositive, namely, that if a collection of natural numbers has no least element, then it must be empty.

Let $T$ be a nonempty collection of natural numbers. Consider $S$, the natural numbers that aren’t in $T$ (in set notation, $S=\mathbb{N}\setminus T$). Since $T$ isn’t empty, $S$ isn’t all of $\mathbb{N}$. We’ll show that, for all $n\in\mathbb{N}$, $n$ is in $S$.

base case $n=1$: If $1\in T$, then $1$ is least. So $1\notin T$, i.e. $1\in S$.

inductive step: Suppose $n\in S$. If any of the numbers less than $n$ were in $T$, then one of them would be least (since there are only finitely many such numbers and we proved every finite set has a least element). So none of the numbers $1,\ldots,n$ is in $T$. If $n+1\in T$, then $n+1$ would be least. So $n+1\notin T$, i.e. $n+1\in S$. This completes the inductive step.

So we’ve shown that every natural number is in $S$, which means that $T$ must be empty. This establishes the contrapositive of the theorem.$\Box$

The Well-Ordering Principle can be used to prove all sort of theorems about natural numbers, usually by assuming some set $T$ is nonempty, finding a least element $n$ of $T$, and “inducting backwards” to find an element of $T$ less than $n$–thus yielding a contradiction and proving that $T$ is empty. In this sense, the Well-Ordering Principle and the Principle of Mathematical Induction are just two ways of looking at the same thing.

Indeed, one can prove that WOP, PCI, and PMI are all logically equivalent, so we could have taken any one of them as our fifth axiom for the natural numbers.

Fundamental Theorem of Arithmetic. Any natural number greater than 1 can be written as the product of primes.

Proof. Let $S$ be the set of natural numbers greater than 1 which cannot be written as the product of primes. By WOP, $S$ has a least element $n$.

Clearly $n$ cannot be prime, so $n$ is composite. Then we can write $n=ab$, where neither of $a$ and $b$ is 1. So $a<n$ and $b<n$. If both of $a$ and $b$ had prime factorizations, then so would $n$. Therefore at least one of $a$ and $b$ does not have a prime factorization (by relabeling, we can assume it’s $a$). But $a<n$ and $a\in S$, so $n$ was not least in $S$.

This contradiction establishes that $S$ has no least element, hence by WOP must be empty. So every natural number greater than 1 can be written as the product of primes.$\Box$

Observe that this proof has more or less the same “juicy bits” as the proof by PCI.

The Division Algorithm. Let $a,b$ be natural numbers. Then there are nonnegative integers $q,r$ so that $0\leq r<b$ and $a=bq+r$. Moreover, $q$ and $r$ are unique. We call $q$ the quotient and $r$ the remainder.

This theorem is called the Division Algorithm because it asserts that any natural number can be divided, with remainder, by any other natural number.

Proof. Given $a$ and $b$, if $a<b$, then set $q=0$ and $r=a$. Then $0\leq r<b$, and $a=qb+r$ as required.

If $a=b$, set $q=1$ and $r=0$.

We are left with the case $a>b$. Consider the set $S=\left\{n\in\mathbb{N}\middle| a-nb< 0\right\}$. Since $b\geq 1$, $kb\geq k$ for all $k\in\mathbb{N}$. In particular, $ab\geq a$, or equivalently $a-ab\leq 0$. So $a-(a+1)b<0$, hence $a+1\in S$.

Since $S$ is nonempty, by WOP, $S$ has a least element, which we’ll call $s$. Set $q=s-1$ and $r=a-qb$. By choice of $r$, we have $a=qb+r$, but we need to show that $0\leq r<b$.

Since $s$ is least in $S$, $q=s-1$ cannot be an element of $S$. So $r=a-qb\geq 0$.

We need to show that $r<b$. Suppose, to the contrary, that $r\geq b$. Then\begin{align*}
r&\geq b\\
a-qb&\geq b\\
a-qb-b&\geq 0\\
a-(q+1)b&\geq 0
\end{align*}

so that $q+1\notin S$. But $q+1=s$, which is an element of $S$. This contradiction establishes that $r< b$ as required.

Now that we have established the existence of $q$ and $r$, let us prove their uniqueness. Consider two pairs $(q,r)$, $(q’,r’)$ so that\begin{align*}
a&=qb+r\\
a&=q’b+r’
\end{align*}

Without loss of generality, assume $r\geq r’$. We have\begin{align*}
q’b+r’&=qb+r\\
q’b-qb&=r-r’\\
(q’-q)b&=r-r’
\end{align*}

Since $b\geq 1$, this means that $r\geq r’$ guarantees $q\leq q’$, and that $q=q’$ iff $r=r’$. We will show that $q=q’$, hence $r=r’$, i.e. the quotient-remainder pair is unique.

Consider the set $S$ as above, with least element $s$. If $q’>s-1$, then $q’\geq s$, so $q’\in S$. But then $q’$ cannot be a quotient. So $q’\leq s-1$. On the other hand, if $q'<s-1$, then\begin{align*}
b> r’&=a-q’b\\
&> a-(s-1)b
\end{align*}

and subtracting $b$ from both sides we have $0>a-(s-1)b$. But $s$ is least, so $s-1\notin S$. This contradiction establishes that $q’\geq s-1$.

So we see that $q’=s-1$. But the same argument applies to $q$, hence $q=q’$.$\Box$

Corollary. Any integer is either even or odd.

Proof. Given an integer $n$, if $n$ is even we’re done. So suppose $n$ is not even, i.e. we know that we cannot write $n=2k$ for any $k$.

The division algorithm says we must be able to write $n=2k+r$ for some $0\leq r<2$. Since we ruled out $r=0$, we must have $r=1$, i.e. $n=2r+1$ is odd. $\Box$

Note that we established previously that no integer could be both even and odd. Now we know that “odd” and “not even” are, in fact, synonyms.

“Disguised” Induction Proofs

We can use the WOP to give a kind of induction proof in disguise. Consider:

Claim. The sum of the first $n$ natural numbers is $\frac{n(n+1)}{2}$.

Ordinarily, we’d prove this by induction.

Exercise. Write a proof of this claim by ordinary induction.

But we can set up a proof that uses the Well-Ordering Principle, like this:

Proof. Suppose not. Then there is some natural number (call it $p$) so that the sum of the first $p$ natural numbers isn’t $\frac{p(p+1)}{2}$. Consider the set of all such numbers:

$$A=\left\{k\middle\vert 1+\cdots+k\neq \frac{k(k+1)}{2}\right\}$$

Our assumption is that $p\in A$; in particular $A$ is not empty. (We believe in our hearts that there are no such numbers, i.e. that $A$ is empty. But this is a reductio ad absurdum proof, so we’ll have to roll with it.)

By the Well-Ordering Principle, $A$ has a least element, which we’ll call $N$.

Maybe $N=1$? No, because $1=\frac{1\cdot (1+1)}{2}$. So $N>1$. But then $N$ has a predecessor, $n=N-1$.

Since $n<N$, we know $n\notin A$ ($N$, after all, was least among the elements of $A$).

That is, $1+2+\cdots+n=\frac{n(n+1)}{2}$.

Now, consider $1+2+\cdots+N$:

\begin{align*}

1+2+\cdots+N&=1+2+\cdots+n+(n+1)\\

&=\frac{n(n+1)}{2}+n+1\\

&=\frac{n(n+1)}{2}+\frac{2(n+1)}{2}\\

&=\frac{n^2+n+2(n+1)}{2}\\

&=\frac{n^2+3n+2}{2}\\

&=\frac{(n+1)(n+2)}{2}=\frac{N(N+1)}{2}\end{align*}

which shows that actually, $N\notin A$. But this is a contradiction! So our initial supposition was incorrect, and thus the claim is true. $\Box$.

Now, I’ve highlighted some parts of the proof in green and orange. Why? The green part is what would be the base case if we wrote an ordinary induction proof. The orange part is the inductive step (from $n=N-1$ to $n+1=N$).

In fact any proof by ordinary induction can be gussied up this way, if you desire.

[callout headingicon=”noicon” textalign=”textright” type=”basic”]

Travel isn’t always pretty. It isn’t always comfortable. Sometimes it hurts, it even breaks your heart. But that’s okay. The journey changes you; it should change you. It leaves marks on your memory, on your consciousness, on your heart, and on your body. You take something with you. alravel isn’t always pretty. It isn’t always comfortable. Sometimes it hurts, it even breaks your heart. But that’s okay. The journey changes you; it should change you. It leaves marks on your memory, on your consciousness, on your heart, and on your body. You take something with you.

Anthony Bourdain, No Reservations: Around the World on an Empty Stomach

[/callout]

Induction is like climbing a ladder. But there are other ways to climb besides ladders. Rock climbers don’t just stand on one step. To get up the rock, a rock climber needs to use all four limbs (not just, like the ladder climber, the previous step).

Like the rock climber, we are allowed to remember not just that we are only one step away from where we’re trying to get, but also how we got to where we are. Why not look back as many steps as we need?

Definition. We call an open sentence $P(n)$ completely inductive if it has the property that $P(1)\wedge P(2)\wedge\cdots\wedge P(n)\Rightarrow P(n+1)$.

If inductive sentences represent hereditary properties, completely inductive sentences represent properties which pass to the next generation but possibly only if the entirety of the lineage had the property.

Principle of Complete Induction. Suppose $P(n)$ is completely inductive and $P(1)$ is true. Then $\forall n, P(n)$.

How might we use a statement like the Principle of Complete Induction? Let’s see an example, and then come back to the justification that PCI works.

Fundamental Theorem of Arithmetic. Every natural number greater than 1 has a prime factorization; that is, given any $n\in\mathbb{N}$ with $n\neq 1$, there are prime numbers $p_1,p_2,\ldots, p_k$ so that we can write $n=p_1\cdot p_2\cdot \cdots \cdot p_k$.

The statement of this theorem contains two new terms: prime number and prime factorization. In the statement itself, we’ve explained what prime factorization means; but we still need to know what a prime number is.

Definition. A natural number $p>1$ is prime if the only natural numbers which divide $p$ are 1 and $p$.

Let’s get an example of a prime number.

Lemma. 2 is a prime number.

Proof. We attempt to factor 2; that is, to write $2=ab$ for some natural numbers $a$ and $b$; to show 2 is prime means we’ll show either $a=1$ or $a=2$. Now the product of any two natural numbers is at least as large as either factor, so we have $a\leq 2$ and $b\leq 2$. Since $a$ and $b$ are natural numbers, $1\leq a$ and $1\leq b$. So we have $1\leq a\leq 2$ and $1\leq b\leq 2$. But the only natural numbers between 1 and 2 (inclusive) are 1 and 2. So either $a=1$ or $a=2$. $\Box$.

Exercise. Adapt this proof to show that 3 is a prime number.

Exercise. Show that 5 is a prime number.

Now we’re ready to prove the Fundamental Theorem of Arithmetic.

Proof of the Fundamental Theorem of Arithmetic. We’ll prove the claim $\forall n, \left(n>1\Rightarrow n\text{ has a prime factorization}\right)$ by complete induction. We’ll refer to $n>1\Rightarrow n\text{ has a prime factorization}$ as $P(n)$.

(base case: $n=1$.) $P(1)$ is a conditional with a false antecedent; so $P(1)$ is true.

(base case: $n=2$.) $P(2)$ is “If 2>1 then 2 has a prime factorization.” 2 is prime, so there’s the prime factorization.

(inductive step.) Consider some natural number $K>2$. Assume that $P(1), P(2),\ldots, P(K-1)$ are all true; that is, assume that any natural number $n$ with $1<n<K$ has a prime factorization. We’ll use this assumption to show that $K$ has a prime factorization.

If $K$ is prime, then there’s our prime factorization.

If $K$ is not prime, then $K$ has a factor other than itself and 1. Call this number $a$. We have $K=ab$ for some natural number $b$. Because $a\neq 1$, we have $b\neq K$. Moreover, the product of any two natural numbers is at least as large as either factor, so we know $1\leq a\leq K$ and $1\leq b\leq K$. Because $a\neq 1$, $b\neq K$. All in all, we have$$1<a<K,1<b<K$$

By our inductive assumption, $a$ has a prime factorization, say $a=p_1\ldots p_k$. The inductive assumption also applies to $b$ to give some primes $q_1,\ldots,q_\ell$ with $b=q_1\cdots q_\ell$.

Then $$K=ab=p_1\ldots p_k\cdot q_1\cdots q_\ell$$

so $K$ has a prime factorization in this case, too.

In either case, $K$ has a prime factorization; this completes the inductive step.

By the Principle of Complete Induction, we must have $P(n)$ for all $n$, i.e. any natural number greater than 1 has a prime factorization.$\Box$

A few things to note about this proof:

• This use of the Principle of Complete Induction makes it look much more powerful than the Principle of Mathematical Induction. Instead of “looking back” one step, we got to “look back” as far as we needed. If we take $K=60$, for example, then we could use $a=5$ and $b=12$. Instead of relying on the previous case ($K=59$), we’re relying on $K=5$ and $K=12$, which are quite far away from $K=60$.
• This proof actually provides something of an algorithm for finding prime factorizations, probably the same one you were taught in grade school.
• Just like ordinary inductive proofs, complete induction proofs have a base case and an inductive step.

One large class of examples of PCI proofs involves taking just a few steps back. (If you think about it, this is how stairs, ladders, and walking really work.) Here’s a fun definition.

Definition. The Fibonacci numbers are defined as follows: $f_1=1$ and $f_2=1$. For any $k>2$, $f_k=f_{k-1}+f_{k-2}$.

We call definitions like this completely inductive definitions because they look back more than one step.

Exercise. Compute the first 10 Fibonacci numbers.

Typically, proofs involving the Fibonacci numbers require a proof by complete induction. For example:

Claim. For any $n$, $f_n+2f_{n+1}=f_{n+3}$.

Proof. For the inductive step, assume that for all $k\leq n$, $f_k+2f_{k+1}=f_{k+3}$. We’ll show that $$f_{n+1}+2f_{(n+1)+1}=f_{(n+1)+3}$$

To this end, consider the left-hand side. \begin{align*}f_{n+1}+2f_{(n+1)+1}&=f_{n}+f_{n-1}+2\left(f_{n+1}+f_n\right)\\&=f_n+2f_{n+1}+f_{n-1}+2f_n\end{align*}

Now we observe that $n\leq n$ and $n-1\leq n$, so we can apply the inductive assumption with $k=n$ and $k=n-1$, to continue:\begin{align*}f_n+2f_{n+1}+f_{n-1}+2f_n&=f_{n+3}+f_{n+2}&=f_{n+4}\end{align*} by the definition of the Fibonacci numbers. This completes the inductive step.

Now for the base case. Observe that since we had to take two steps back in our inductive step (to prove the claim at $n+1$, we had to look at $n$ and $n-1$), our inductive step only starts working once we have two steps to rely on. So we need

base case $n=1$: The statement to prove is $f_1+2f_2=f_4$. Since $f_1=1$, $f_2=1$, and $f_4=3$, we have the base case.

base case $n=2$: The statement to prove is $f_2+2f_3=f_5$. Since $f_2=1$, $f_3=2$, and $f_5=5$, we have the base case.

By the Principle of Complete Induction, we have established the claim. $\Box$

Here’s another example:

Claim. For any $n$, and any $a$, $f_af_n+f_{a+1}f_{n+1}=f_{a+n+1}$.

Proof. Fix $a$.

For the inductive step, assume that for all $k\leq n$, $f_af_k+f_{a+1}f_{k+1}=f_{a+k+1}$. We’ll show that $$f_af_{n+1}+f_{a+1}f_{(n+1)+1}=f_{a+(n+1)+1}$$

To this end, consider the left-hand side. \begin{align*}f_af_{n+1}+f_{a+1}f_{n+2}&=f_a\left(f_{n}+f_{n-1}\right)+f_{a+1}\left(f_{n+1}+f_n\right)\\ &=f_af_n+f_af_{n-1}+f_{a+1}f_{n+1}+f_{a+1}f_n\\&=f_af_n+f_{a+1}f_{n+1}+f_af_{n-1}+f_{a+1}f_n\end{align*}

Now we observe that $n\leq n$ and $n-1\leq n$, so we can apply the inductive assumption with $k=n$ and $k=n-1$, to continue:\begin{align*}\overbrace{f_af_n+f_{a+1}f_{n+1}}+\overbrace{f_af_{n-1}+f_{a+1}f_n}&=f_{a+n+1}+f_{a+(n-1)+1}\\&=f_{a+n+1}+f_{a+n}=f_{a+n+2}\end{align*}

This completes the inductive step.

Now for the base case. Again we need two base cases, because our inductive step looked back two steps:

base case $n=1$: The claim is $f_{a}f_1+f_{a+1}f_2=f_{a+2}$. Since $f_1=f_2=1$, this claim is $f_a+f_{a+1}=f_{a+2}$, which is the definition of the Fibonacci numbers.

base case $n=2$: The claim is $f_{a}f_2+f_{a+1}f_3=f_{a+3}$. Since $f_2=1$ and $f_3=2$, we need to establish that $f_a+2f_{a+1}=f_{a+3}$. But we just proved that above.

By the Principle of Complete Induction, we have established the claim. $\Box$

Now that we’ve seen how complete induction works, let’s explain why complete induction works:

Proof of the Principle of Complete Induction. We are given an open sentence $P(n)$ with the properties: $P(1)$ and $P$ is completely inductive.

Consider the sentence $Q(n)=P(1)\wedge P(2)\wedge\cdots\wedge P(n)$. We’ll show first that $Q(n)$ is always true.

First observe that $Q(1)=P(1)$, which by assumption is true.

Now I claim $Q(n)\Rightarrow Q(n+1)$, that is, $Q$ is inductive. Assume $Q(n)$ is true. That is, $P(1)\wedge P(2)\wedge\cdots\wedge P(n)$. Because $P$ is completely inductive, we know $P(n+1)$ is true. Then $Q(n+1)=Q(n)\wedge P(n+1)$ is true.

Thus we have proved, by (ordinary) induction, that $\forall n,Q(n)$.

Why does this establish that $\forall n,P(n)$? Because $Q(n)=P(1)\wedge\cdots\wedge P(n) \Rightarrow P(n)$ by definition.$\Box$

The converse is also true: we could have taken the Principle of Complete Induction as an axiom, and used it to prove the Principle of Mathematical Induction. In fact you’ll do that for homework.

Here’s another example of a proof by complete induction, which shows we might need to go back quite a few steps (hence, have quite a number of base cases to build on):

Claim. If $n\geq 12$, then there are nonnegative natural numbers $k$ and $l$ so that we can write $n=4k+5l$.

Proof.

base case: $n=12$. Let $k=3$ and $l=0$.

base case: $n=13$. Let $k=2$ and $l=1$.

base case: $n=14$. Let $k=1$ and $l=2$.

base case: $n=15$. Let $k=0$ and $l=3$.

Now suppose we’ve established that we can write any number up to and including $n$ as a sum of 4s and 5s. We may as well assume $n\geq 15$ since we handled the others already. We’ll try to write $n+1$ as a sum of 4s and 5s.

$(n+1)-4=n-3\geq 12$, so we know we can write $(n+1)-4$ as a sum of 4s and 5s, say $(n+1)-4=4k+5l$. But then $n+1=4k+4+5l=4(k+1)+5l$, so we’ve written $n+1$ as the sum of 4s and 5s. This completes the inductive step, hence the proof. $\Box$

 

[callout headingicon=”noicon” textalign=”textright” type=”basic”]

千里之行，始於足下

The journey of a thousand miles starts with a single step.

Lao Tzu

[/callout]

Many statements in mathematics are true {\em for any natural number}. For example.

Fundamental Theorem of Arithmetic. Every natural number has a unique prime decomposition.

Theorem. Every natural number is either even or odd.

Power Rule for Differentiation. For any natural number $n$, $\frac{d}{dx}\left[x^n\right]=nx^{n-1}$.

Our first use of the definition of $\mathbb{N}$ (other than to prove facts about arithmetic) will be to establish a way to prove statements like this. But to do that, we need to make sure our definition of $\mathbb{N}$ is formal enough to serve as the backbone of a proof. To do this, we’ll focus on the structure of the open sentences involved. Since we are interested only in statements that involve the natural numbers somehow, we’re going to assume that the variables we’re dealing with represent natural numbers unless otherwise specified. That is, we’re taking the universe for everything to be $\mathbb{N}$ until further notice.

Definition. We call an open sentence $P(n)$ inductive if it has the property: $\forall n, P(n)\Rightarrow P(n+1)$.

We can think of inductive sentences as representing hereditary properties — that is, they pass down to successors. Being royal, for example, is an inductive property.

Equipped with this definition, we can state axiom 5 of the natural numbers as a formal symbolic sentence. (If you recall, we stated the first four axioms as formal symbolic sentences, but left the fifth axiom just in terms of words.) Here goes:

The Inductive Axiom. Let $P(n)$ be an open sentence whose variable $n$ represents a natural number. Suppose that:

• $P(1)$ is true, and
• $P$ is inductive.

Then $\forall n, P(n)$.

This version still has a few words in it, but we could make it purely symbolic:$$\left(P(1)\wedge \left[\forall n, P(n)\Rightarrow P(n+1)\right]\right)\Rightarrow \forall k,P(k)$$

To see that this version is the same as the wordier version we gave before, let’s take $P(n)$ to be “$n$ can be reached from 1 by a sequence of successions“. It’s clear that this $P$ is inductive: if $n$ can be reached from 1 by successions, so can its successor. Clearly 1 can be reached from 1 by a(n extremely short) sequence of successions. So $P$ meets both criteria — the Inductive Axiom says “any natural number can be reached from 1 by a sequence of successions“.

The Inductive Axiom is also known as the Principle of Mathematical Induction, or PMI for short. It’s the engine that will let us prove lots of statements of the form $\forall n, P(n)$, because that’s the conclusion of PMI.

To use PMI in this way, you need to a few things:

• identify what $P(n)$ is
• verify that $P(1)$ is true (we call this the “base case”)
• show that $P(n)$ is inductive, which means to prove $\forall n, P(n)\Rightarrow P(n+1)$ (we call this the “inductive step”)

Luckily, we already know how to prove universal claims, and we already know how to prove conditionals. So a general outline of a proof by induction goes like this:

Proof. (by induction)
base case: $n=1$. [Establish $P(1)$]

inductive step: Let $n$ be a natural number. Assume $P(n)$ is true.
[. . . some work goes here . . .]
Conclude $P(n+1)$.

$\Box$

Let’s write an example proof by induction to show how this outline works. I’ll put my commentary in blue parentheses.

Claim. I can reach any rung of any ladder which is standing on the ground.

Proof. Given a ladder, we’ll show that for any $n$, I can reach the $n^{th}$ rung of that ladder. (Here $P(n)$ is the statement “I can reach the $n^{th}$ rung of the ladder.”)

I can reach the first rung by taking a step — after all, the ladder is standing on the ground. (We’ve just proved $P(1)$.)

Now suppose I’m standing on the $n^{th}$ rung. (This is assuming $P(n)$.) Then I can take a step (These are the “juicy bits” of the proof.), and get to the $(n+1)^{th}$ step. (We’ve concluded $P(n+1)$.)

By the Principle of Mathematical Induction, this shows we can reach any rung of the ladder.  $\Box$

Here’s an example where $P(n)$ is “more mathematical”.

Claim. For any natural number $n$, $1+4+7+\cdots+(3n+1)=\frac{3}{2}n^2+\frac{5}{2}n+1$.

Proof. (base case) When $n=1$, the left-hand side is $1+4=5$. The right-hand side is $\frac{3}{2}\cdot 1^2+\frac{5}{2}\cdot 1+1=\frac{3}{2}+\frac{5}{2}+1=4+1=5$. So the equality is true when $n=1$.

(inductive step) Let $n$ be a natural number. Assume $1+4+7+\cdots+(3n+1)=\frac{3}{2}n^2+\frac{5}{2}n+1$. Consider the left-hand side of $P(n+1)$:\begin{align*} 1+4+7+\cdots+(3(n+1)+1)&=1+4+7+\cdots+3n+(3(n+1)+1)\\ &=\frac{3}{2}n^2+\frac{5}{2}n+1+3(n+1)+1\\&=\frac{3}{2}n^2+\frac{5}{2}n+3n+5\end{align*}Here we have used the assumption $P(n)$.

Now we work on the right-hand side of $P(n+1)$:\begin{align*} \frac{3}{2}(n+1)^2+\frac{5}{2}(n+1)+1&=\frac{3}{2}(n^2+2n+1)+\frac{5}{2}(n+1)+1\\&=\frac{3}{2}n^2+\frac{5}{2}n+3n+\frac{3}{2}+\frac{5}{2}+1\\&=\frac{3}{2}n^2+\frac{5}{2}n+3n+5\end{align*}

Since the left-hand side of $P(n+1)$ and the right-hand side of $P(n+1)$ are both equal to $\frac{3}{2}n^2+\frac{5}{2}n+3n+5$, they are equal to each other. That is, $P(n+1)$ is true. This completes the inductive step.

By the Principle of Mathematical Induction, we have established the claim. $\Box$.

A few things to note here. First, the base case is usually pretty obvious. Second, the fun (i.e. hard) part of the proof is figuring out how to use $P(n)$ to get $P(n+1)$.

It’s not always obvious what the natural number (or inductive variable) is. Often it’s the size of something (since the natural numbers are for counting!). If your inductive variable isn’t obvious from the problem statement, it’s good form to let the reader know what you’ll be inducting on.

Claim. Every finite set of real numbers has a least element.

Proof. We will proceed by induction on the size of the set.

(base case) Suppose the set has exactly one element. Then that element is least.

(inductive step) Assume we’ve proved that any set of real numbers with exactly $n$ distinct elements has a least element. We’ll show that any set of real numbers with exactly $n+1$ distinct elements has a least element.

Let $S$ be such a set, and label its elements $a_1,a_2,\ldots, a_n,a_{n+1}$. There are two possibilities for how $a_{n+1}$ is related to the other elements of the set.

case: $a_{n+1}<a_k$ for all $k\leq n$. Then $a_{n+1}$ is least.

case: There is some $k\leq n$ with $a_k<a_{n+1}$. Then consider the set $S’$ which consists of all of the $a$s except $a_{n+1}$. $S’$ has exactly $n$ elements, so by our inductive assumption, there is a least element of $S’$ (call it $b$). Then $b\leq a_k<a_{n+1}$, so $b$ is also least in $S$.

In either case, $S$ has a least element, thus completing the inductive step, hence (by PMI) the proof. $\Box$

“Generalized” induction

Now consider the following:

Claim. If I am standing in a second story window, I can get to any rung of any ladder standing on the ground, provided that rung is at least the $15^{th}$ rung.

The form of this claim is: $\forall n, \left(n\geq 15\Rightarrow P(n)\right)$, or $\forall n\geq 15,P(n)$.

Proof. Since I’m in the second story window, I can step out onto the $15^{th}$ rung. (Prove $P(15)$.)

Now if I’m on any rung, I can take a step to get to the next rung. (Prove that $P(n)$ guarantees $P(n+1)$.)

So no matter what rung (above the $15^{th}$) I want to get to, I can. $\Box$.

This technique of starting someplace other than 1 is sometimes called generalized induction, but it really doesn’t deserve such a fancy name. It’s just regular induction, but starting from some number other than 1.

[callout headingicon=”noicon” textalign=”textright” type=”basic”]

Die ganzen Zahlen hat der liebe Gott gemacht; alles andere ist Menschenwerk.

Beloved God made the integers; everything else is the work of human hands.

Leopold Kronecker

[/callout]

Most informal definitions of the natural numbers call them the “counting numbers”. This is correct, but it’s not a mathematical definition. To make a mathematical definition, we need to think a bit more carefully about how counting works.

Activity. Think about how you count. Really think about it. If someone gives you a stack of bills, how you do go about counting it?

 

Overview of the Natural Numbers and Induction

• The Natural Numbers (this page).  Natural numbers are the numbers used for counting.
• Proof by Induction. The structure of $\mathbb{N}$ provides a handy way to prove statements of the form $\forall n\in\mathbb{N}, P(n)$.
• Other Uses of Induction.
• Complete Induction. The inductive idea can be pushed into some interesting places.
• The Well-Ordering Principle. Induction, in disguise!
• The Integers and Induction. Technically induction only applies to claims quantified over $\mathbb{N}$, but we can usually use it for claims about the integers, too.

 

What are the Natural Numbers?

Definition. The natural numbers (denoted $\mathbb{N}$) satisfy the following properties:

1. 1 is a natural number.
2. Each natural number $n$ has a unique successor $S(n)$, which is a natural number.
3. If two natural numbers have the same successor, they are the same.
4. 1 is nobody’s successor.
5. Any natural number can be reached from 1 by a chain of successions.

We call these the Peano axioms, after Giuseppe Peano. They were first published in 1889.

Exercise. Write clauses 2, 3, and 4 as symbolic sentences. Then compute their symbolic and English denials.

We normally represent the natural numbers as dots on a line:
\begin{tikzpicture}

\filldraw (0,0) circle (3pt) node[align=left, below]{$1$} (2,0) circle (3pt) node[align=left, above]{$S(1)$}  (4,0) circle (3pt) node[align=left, below]{$S(S(1))$}  (6,0) circle (3pt) node[align=left, above]{$S(S(S(1)))$}  (8,0) circle (3pt) node[align=left, below]{$S(S(S(S(1))))$};

\draw[->, line width=2pt] (0,0) — (2,0);

\draw[->, line width=2pt] (2,0) — (4,0);

\draw[->, line width=2pt] (4,0) — (6,0);

\draw[->, line width=2pt] (6,0) — (8,0);

\draw[->, line width=2pt] (8,0) — (10,0);

\end{tikzpicture}

where each dot is a natural number, and the arrow points from a number to its successor. We also adopt the symbols 2 for $S(1)$, 3 for $S(S(1))$, 4 for $S(S(S(1)))$, etc.

Each clause of this definition is necessary in order for counting to work. (1) is obvious, but the others are also necessary. Without the others, we might have “number lines” that look very different.

For example, we might have number systems like:

\begin{tikzpicture}

\filldraw (0,0) circle (3pt) node[align=left, below]{$1$} (2,0) circle (3pt) node[align=left, above]{$S(1)$} ;

\draw[->, line width=2pt] (0,0) — (2,0);

\end{tikzpicture}

which satisfies axioms 1, 3, 4, and 5, but not axiom 2.

Or this:

\begin{tikzpicture}

\filldraw (0,1) circle (3pt) node[align=left, below]{$1$} (2,2) circle (3pt) node[align=left, above]{$S(1)$}  (4,2) circle (3pt) node[align=left, below]{$S(S(1))$}  (6,2) circle (3pt) node[align=left, above]{$S(S(S(1)))$}  (8,2) circle (3pt) node[align=left, below]{$S(S(S(S(1))))$};

\draw[->, line width=2pt] (0,1) — (2,2);

\draw[->, line width=2pt] (2,2) — (4,2);

\draw[->, line width=2pt] (4,2) — (6,2);

\draw[->, line width=2pt] (6,2) — (8,2);

\draw[->, line width=2pt] (8,2) — (10,2);

\filldraw (0,1) circle (3pt) node[align=left, above]{$1$} (2,0) circle (3pt) node[align=left, below]{$S(1)$}  (4,0) circle (3pt) node[align=left, above]{$S(S(1))$}  (6,0) circle (3pt) node[align=left, below]{$S(S(S(1)))$}  (8,0) circle (3pt) node[align=left, above]{$S(S(S(S(1))))$};

\draw[->, line width=2pt] (0,1) — (2,0);

\draw[->, line width=2pt] (2,0) — (4,0);

\draw[->, line width=2pt] (4,0) — (6,0);

\draw[->, line width=2pt] (6,0) — (8,0);

\draw[->, line width=2pt] (8,0) — (10,0);

\end{tikzpicture}

which also satisfies axioms 1, 3, 4, and 5, but not axiom 2.

or

\begin{tikzpicture}

\filldraw (0,0) circle (3pt) node[align=left, below]{$1$} (2,0) circle (3pt) node[align=left, right]{$S(1)$} ;

\draw[->, line width=2pt] (0,0) — (2,0);

\draw[->, line width=2pt] plot [smooth cycle, tension=1] coordinates {(2,0) (3,1) (4,0) (3,-1)};

\end{tikzpicture}

or

\begin{tikzpicture}

\filldraw (0,0) circle (3pt) node[align=left, below]{$1$} (2,0) circle (3pt) node[align=left, right]{$S(1)$} ;

\draw[->, line width=2pt] (0,0) .. controls (.5,.5) and  (1.5,.5) ..(2,0);

\draw[->, line width=2pt] (2,0) ..controls (1.5,-.5) and  (.5,-.5) .. (0,0);

\end{tikzpicture}

Exercise. Identify which Peano axioms each of the “number lines” above satisfies, and which axioms they do not satisfy.

Exercise. Draw a “number line” which satisfies axioms 1, 2, 3, and 4 but not axiom 5.

Peano’s definition of the natural numbers is called an axiomatic definition because it’s really just a list of axioms, or desirable properties. When we make an axiomatic definition, we specify some of the properties we want the object we’re defining has. This is somewhat of a balancing act: if we list too many such properties, it might be that our list is too much to ask for, and no such object exists. If we ask for too few, on the other hand, then maybe there are many different objects which satisfy our definition.

For now, we’ll take it on faith that there’s a unique system satisfying axioms 1 – 5, which we’ll refer to as the natural numbers.