Complete Induction – Foundations of Mathematics

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

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$