Induction: One Step at a Time

The most useful proof technique in computer science is mathematical induction. It is the primary way in which we: (A) Prove theorems and (B) construct and define objects.

In science, the term "induction" refers to the process of going from a particular series of observations of a certain phenomenon to the statement of a general law governing all occurrences of this phenomenon. The prediction that the sun will rise tomorrow is about as certain as anything can be, but it still does not have the same power as a theorem proved by strict logical or mathematical reasoning.

Mathematical induction is used to establish the truth of a mathematical statement for an infinite sequence of cases. In essence, if we know that the first instance of a proposition is true and the second instance can be derived from the first one, making it true, and the pattern repeats itself, then we know that the final result must also be true. On the other hand, if the first instance, or any of the other instances following the first, turns out to be false, the final result is false.

Falling Dominoes

To see what is going on, let us start with dominoes. Suppose we stand dominoes up on end in a long, closely spaced row. We knock the first domino down. What happens to the last domino?

We know a couple of things.

• Domino 0 was knocked down.
• If the kth domino is knocked down, then it will knock down the domino.

So first the 0th domino gets knocked down. But that means it knocks down the first domino, which knocks down the second domino, which knocks down the third domino, etc. Thus, the fall cascades all the way to the last domino: when the next-to-last domino falls, the last domino also falls.

Here is a formal proof by contradiction of this assertion. Suppose the dominoes do not all fall over. Let be the lowest-numbered domino that remains standing. Domino did fall, and will knock over domino . Thus, domino must both fall and remain standing. This is a contradiction. Hence, knock the first domino over, and they will all fall.

Basic Induction

This reasoning is the foundation of mathematical induction. Here is the most basic form of induction.

Suppose we wanted to prove a statement is true for all the natural numbers . We can do this in two parts.

1. First, prove the base case:
2. Next, prove the inductive step: .

In effect, assume hypothetically that for any particular is true. This is called the "induction hypothesis." Use the induction hypothesis to prove that follows.

TODO: Point out how this only applies to statements about natural numbers, say that this really isn't a constraint.

TODO: Tell them to come back here after the Cantor's legacy lecture to appreciate this even more.

Example

Here is a basic proof using mathematical induction. This example is here to give you an idea of the flavor of an inductive proof; we'll talk later about good technique in writing inductive proofs.

Theorem. For , .

Proof. By induction.

• Base case: . The sum of the first 0 numbers is 0.
• Inductive hypothesis: Assume that for some ,
• Inductive Step: We want to prove that . By our IH, we know that
  

Solving Inductive Problems

Remember how we talked about exemplification as a problem solving technique? It works really really well with induction. You can use exemplification to guess a formula , then use induction to prove the formula is true.

Heh...here's a fun problem to attack. This was the very first inductive proof ever written :).

Problem. Find a formula for the sum of the first odd numbers.

Well, we can start by checking it out for small values.

Fairly suggestive. It seems reasonable to try and prove the following.

Theorem. The sum of the first odd numbers is .

After all, if we're wrong then our inductive proof will fail. So let's try proving this.

First step is the base case. Be careful about this! Some theorems will only apply if , for example, so don't use as the base case if that's true. In this case, is meaningless, so let's prove .

Base case. The sum of the first odd number is . Hence, is true.

Now we need to prove that . Here's what we'll do: we'll assume that is true, then show that must also be true. The assumption that is true is called the inductive hypothesis.

Induction hypothesis: For ,

Inductive step:We want to prove that . To do this, add to both sides of the inductive hypothesis.

We obtain the sum of the first odd numbers, .

By induction, therefore, is true.

In setting up an induction proof, keep the following tips in mind.

• State the variable or structure on which you are performing the induction.
• Show your base case and induction hypothesis clearly.
• It often helps to write down what you need to prove based on your induction hypothesis.
• In your proof, clearly label where you used the induction hypothesis.

Basic variants

Many basic applications of induction don't need much stronger machinery than the formulaic approach given above. However, in order to grasp the nature of inductive reasoning, you need to be comfortable with tuning and tweaking inductive proofs. This type of proof can be generalized in several ways.

• Perhaps we only want to prove a statement is true for all (or more generally, .) In this case, the only change we'd make is to use as our base case.
• What if we only want to prove that a statement or formula is true for a finite subset of the natural numbers? In this case, we can use different inductive steps. Examples
  • Showing that is true for all positive multiples of 5. Show that is true, then show that .
  • Showing that is true for all positive powers of two. Show that is true, then show that .
• Even if we want to show something is true for all natural numbers , we don't have to use . For example, if we showed and as base cases, then proved that , this would be a valid inductive proof too (note that this example is basically an inductive proof that cases based on whether is even or odd.)

There is a very good exercise that you should try to become comfortable with these. Don't use for this!

Exercise. The National Bank of Aldouria mints coins with denominations of either 5 or 9 Aldourian pounds. A sum of money is called round if it can be made up of Aldourian coins. Prove that any sum 32 or more is round using induction.

Primality

A natural number is prime if it has no divisors besides 1 and itself. Note that 1 is not considered prime. Here is a theorem you may have seen before.

Theorem. Every natural number greater than 1 can be written as a product of prime numbers.

Note that it is much more subtle to argue for the existence of a unique prime factorization. For now, we'll just prove that every number has at least one prime factorization.

You can try to solve the above using the induction machinery covered to date. Not an easy task :(. Even availing yourself of the tricks mentioned above don't seem to help. In order to solve this problem, we're going to introduce our first major induction variant: strong induction.

Strong Induction

In the basic induction above, we basically set things up akin to a row of dominoes. Sure, we played tricks like making dominoes knock down others 5 places ahead of it, or starting by knocking down the 10th domino instead of the first, but there was still this linear chain of implications that we used. Here's how strong induction works.

• Establish base case:
  
• Establish that
  
  • Let be any natural number.
    
  • Induction hypothesis: Assume .
    
• Use that to derive .

Instead of just relying on one previous case to help prove , we allow ourselves to use all previous cases to show .

Despite its name, strong induction is no stronger than standard induction. Technically, it is possible to repackage a strong induction proof as standard induction (although the result might not be very pretty.) Strong induction does makes it easier to prove a much greater set of statements, though.

With this, its fairly easy to prove the theorem above. You may want to solve it yourself before looking at the example below.

Example: Prime factorization

Theorem. Every natural number greater than 1 can be written as a product of prime numbers.

Proof. By induction

• Base case: 2 is prime. This establishes the base case.

• Induction hypothesis: Assume that can all be factored into primes (or, equivalently, written as a product of primes).

• Need to Show: can be factored into primes.

• Inductive Step: If is prime, there is nothing more to do. If not, where ; hence and can be factored into primes. Thus, is the product of the factors of and the factors of .

Least Counterexample

There's another proof technique that we could use to solve this problem. This is our second major variant on induction: least counterexample. Its a fairly tricky proof technique to use, but you should consider trying it if other induction methods are failing. Here's what a least counterexample proof looks like.

• Establish base case: .
  
• Establish that .
  
  • Assume that is the least counterexample.
    
  • Derive the existence of a smaller counterexample.

Example

As an example, let's see what our theorem above would look like using a least counterexample proof.

Theorem. Every natural number greater than 1 can be written as a product of prime numbers.

Proof. Clearly this is true for . Assume this theorem is false. Let be the least counterexample — the smallest number such that is false.

Because is the least counterexample, must not be prime, so . If both and had prime factorizations, then would also have a prime factorization. Thus, either or is a smaller counterexample. This contradicts the assumption that is the least counterexample. Hence, all numbers greater than 1 have a prime factorization.

Pierre Fermat generalized this approach as the method of infinite descent. In this approach, we show that for any counterexample, we can find a smaller one. Thus, if a counterexample exists there would be an infinite sequence of smaller and smaller counterexamples.

Invariants (IMPORTANT)

Invariants are one of the most important things to know / be comfortable with as a computer scientist. Regardless whether you want to become a hardcore hacker or rarefied theoretician, knowing invariants well will be of great help. In addition to this course, you'll also spend time learning about them in 15-212. -- SeventhGuest - 10 Feb 2007

Yet another way of packaging inductive reasoning is to define invariants. By invariant, we can mean any one of several things, depending on the context.

• Not varying; constant.
• In mathematics: unaffected by a designated operation, such as a transformation of coordinates.
• In programming, a rule, such as the ordering of an ordered list or heap, that applies throughout the life of a data structure or procedure. Each change to the data structure must maintain the correctness of the invariant.

Invariants are crucial in proving programs correct. We maintain invariance in a program in the sense that, for example, some index i is going to be between 0 and the upper bound of an array and never call for a value outside that array.

We use invariant induction when we have a time-varying state. For example, in a computer, the state can change with every clock cycle, going through a range of states.

In invariant induction, suppose that we have a time-varying world state: Each state change is assumed to come from a list of permissible operations. We seek to prove that statement S is true of all future worlds.

We start by arguing that S is true of the initial world, . We then show that, if S is true for some world, then S remains true of any world obtained by applying a permissible operation to .

Example

Theorem. At any party, the number of people who have shaken hands an odd number of times is even.

Proof. Define a person's parity as odd or even according to the number of hands that person has shaken. We prove the following invariant: the number of people of odd parity must be even.

At the beginning, zero hands have been shaken at the start of a party, so zero people have odd parity. If two people of different parities shake hands, then they both swap parities and the odd parity count is unchanged. If two people of the same parity—odd or even—shake hands, they both change and hence the odd parity count changes by 2—and remains even.

TODO: More invariant examples would be nice.

Exercises

TODO: Somebody should create answers to these (one page per problem) and link to them. Also correct the problem description if there are any typos :).

• Let be the claim that . Give a complete inductive proof that is true for all .

• Prove by induction that . Using this result, prove the following:

• The ''n''th harmonic number is defined as . Hence, , , etc.  
  1. Prove by induction that .
  2. Prove by induction that for all , .

• Prove by induction that is divisible by for all . Note that denotes the set of all positive integers .

• 1.pdf: Exercise 1

• 2.pdf: Exercise 2

• TWiki_Induction_Answers.pdf: Answers to Exercise 3 & 4

TODO: More exercises below. Either get rid of them or add them to the list.

Exercises

Prove by induction the following statements: d196 1