# Complete Induction

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 completely inductive if it has the property that .

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 is completely inductive and is true. Then .

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 with , there are prime numbers so that we can write .

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 is prime if the only natural numbers which divide are 1 and .

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 for some natural numbers and ; to show 2 is prime means we'll show either or . Now the product of any two natural numbers is at least as large as either factor, so we have and . Since and are natural numbers, and . So we have and . But the only natural numbers between 1 and 2 (inclusive) are 1 and 2. So either or . .

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 by complete induction. We'll refer to as .

(base case: .) is a conditional with a false antecedent; so is true.

(base case: .) 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 . Assume that are all true; that is, assume that any natural number with has a prime factorization. We'll use this assumption to show that has a prime factorization.

If is prime, then there's our prime factorization.

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

By our inductive assumption, has a prime factorization, say . The inductive assumption also applies to to give some primes with .

Then

so has a prime factorization in this case, too.

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

By the Principle of Complete Induction, we must have for all , i.e. any natural number greater than 1 has a prime factorization.

• 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 , for example, then we could use and . Instead of relying on the previous case (), we're relying on and , which are quite far away from .
• 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: and . For any , .

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 , .

Proof. For the inductive step, assume that for all , . We'll show that

To this end, consider the left-hand side.

Now we observe that and , so we can apply the inductive assumption with and , to continue:

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 , we had to look at and ), our inductive step only starts working once we have two steps to rely on. So we need

base case : The statement to prove is . Since , , and , we have the base case.

base case : The statement to prove is . Since , , and , we have the base case.

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

Here's another example:

Claim. For any , and any , .

Proof. Fix .

For the inductive step, assume that for all , . We'll show that

To this end, consider the left-hand side.

Now we observe that and , so we can apply the inductive assumption with and , to continue:

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 : The claim is . Since , this claim is , which is the definition of the Fibonacci numbers.

base case : The claim is . Since and , we need to establish that . But we just proved that above.

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

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 with the properties: and is completely inductive.

Consider the sentence . We'll show first that is always true.

First observe that , which by assumption is true.

Now I claim , that is, is inductive. Assume is true. That is, . Because is completely inductive, we know is true. Then is true.

Thus we have proved, by (ordinary) induction, that .

Why does this establish that ? Because by definition.

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 , then there are nonnegative natural numbers and so that we can write .

Proof.

base case: . Let and .

base case: . Let and .

base case: . Let and .

base case: . Let and .

Now suppose we've established that we can write any number up to and including as a sum of 4s and 5s. We may as well assume since we handled the others already. We'll try to write as a sum of 4s and 5s.

, so we know we can write as a sum of 4s and 5s, say . But then , so we've written as the sum of 4s and 5s. This completes the inductive step, hence the proof.