SP20:Lecture 12 Induction
We introduce the proof technique of weak induction.
Induction by example: A ∪ (B1 ∩ ... ∩ Bn) = (A∪B1) ∩ ... ∩ (A∪Bn)
We start with a simple version of the claim, which I will refer to as claim 2 (for reasons that will become apparent):
We now graduate to claim 3:
Notice that we used claim 2 to prove claim 3. Similarly, we can use claim 3 to prove claim 4:
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.
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:
We must showand 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.
Here is a straightforward example of induction:
be the statement "We will show and (assuming ).".
Aside: Note that for all n". To see why, imagine that it did. Then would say "for all 7, ...",does not include the "
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.
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
Before we present the proof, a few (possibly familiar) definitions:
We will attempt to use weak induction to prove the following claim:
If we knew that 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 and had strengthen our inductive hypothesis or use strong induction.
We will show these techniques in the next lecture.