FA18:Lecture 12 induction

We introduce the proof technique of weak induction.

Induction by example: A ∪ (B1 ∩ ... ∩ Bn) = (A∪B1) ∩ ... ∩ (A∪Bn)

We will prove a variety of claims to demonstrate a new proof technique called induction; we will discuss induction much more later in the semester.

claim 2

We start with a simple version of the claim, which I will refer to as claim 2 (for reasons that will become apparent):

Proof:
Choose arbitrary sets , , and . We want to show to show that every is also in . Choose an arbitrary in the left hand side. Then and . This means either (1) or (2) . In case (1), we have and , so , and thus . Case (2) is similar. In either case, , as required.

claim 3

We now graduate to claim 3:

Proof:
By claim 2 (with and ), we have . Now, we can apply claim 2 to conclude that . In general, if A ⊆ B then A ∩ C ⊆ B ∩ C, so we know that . Putting this together (and using the fact that ⊆ is transitive),

we have

as required.

claim 4

Notice that we used claim 2 to prove claim 3. Similarly, we can use claim 3 to prove claim 4:

Proof: claim 4
By claim 2 (with and ), we have . Now, we can apply claim 3 (above) to conclude that . In general, if A ⊆ B then A ∩ C ⊆ B ∩ C, so we know that . Putting this together (and using the fact that ⊆ is transitive), we have

as required.

claim n

You may have noticed the proofs of claim 3 and claim 4 are almost identical. You might imagine that you could use claim 4 to prove claim 5, and claim 5 to prove claim 6, and so on. Indeed you can, and this is the idea behind induction.

Since we have proved claim 2, and, for any , we can use claim to prove claim (this is called the inductive step), we can conclude claim for any . Here is the general inductive step:

Proof: claim n+1
Since A ∩ (B∪C) ⊆ (A∩B) ∪ (A∩C) (proven above), we have . Now, we can apply claim n (above) to conclude that . In general, if A ⊆ B then A ∩ C ⊆ B ∩ C, so we know that . Putting this together (and using the fact that ⊆ is transitive), we have

as required.

Induction

Because this pattern is so common, there is some stylized language. Typically, instead of "claim n", people often write P(n); this is referred to as the inductive hypothesis. The first proof (in our case, the proof of claim 2) is referred to as the base case. The general proof (using P(n) to prove P(n+1)) is called the inductive step. Here is a stylized induction proof:

For any ,

Proof:
By induction. Let be the statement "."

We must show and assuming .

In the base case, when , we want to show to show that every is also in . Choose an arbitrary in the right hand side. Then and . This means either (1) or (2) . In case (1), we have and , so , and thus . B_2ase (2) is similar. In either case, , as required.

For the inductive step, choose an arbitrary and assume we have already proved . Our goal is to show . We compute:

Example: summation

Here is a straightforward example of induction:

Proof:
We prove this statement by weak induction on . Let

be the statement "". We will show and (assuming ).

Aside: Note that does not include the "for all n". To see why, imagine that it did. Then would say "for all 7, ...",
Aside: A common mistake people make when writing inductive proofs, especially those involving formulas, is to think of as a 'number' and not a statement. If you find yourself writing , you are doing something wrong! Plugging this in would give which doesn't make sense.

In the case where , the left hand side and the right hand side are both 0.

Now, to see , first assume . We want to show , i.e. that . We compute:

as required.

Aside: This proof uses a common pattern in inductive proofs (and in many other proofs too!): in the first few steps, we take what we want to show, and manipulate it so that we can use what we know ( in this case). If you get stuck, it's always good to look at what you've assumed already and try to find a way to apply it.

Example: prime factorization

We now give an example of a inductive proof that doesn't work; we will show how to patch it up in the next lecture.

Before we present the proof, a few (possibly familiar) definitions:

Definition: Composite
A natural number is composite if there exists with and both greater than 1 satisfying .
Definition: Prime

We will attempt to use weak induction to prove the following claim:

For all , if then there exists prime numbers with .
Proof: Attempt with weak induction
We will prove the claim using weak induction. Let be the statement "there exists prime numbers with . We will prove and assuming .

In the base case, when we see that 2 is prime. Therefore, we can choose ; clearly .

For the inductive step, we assume ; our goal is to show , in other words that has a prime factorization.

There are two cases: could be prime or composite. If is prime, we can proceed as in the base case: simply choose .

If, on the other hand, is composite, then we know that for some natural numbers and .

If we knew that and had prime factorizations, then we could combine them to form a prime factorization of . But we don't know that — it is what we are trying to prove. We do have an inductive hypothesis that tells us that has a prime factorization, but that only helps if .

To fix this up, we need to either strengthen our inductive hypothesis or use strong induction.

We will show these techniques in the next lecture.