FA18:Lecture 13 strong induction and euclidean division
We introduced strong induction and used it to complete our proof that Every natural number is a product of primes. We then started our discussion of number theory with the euclidean division algorithm.
In this lecture, we will use a bit of shorthand for representing (finite) sequences:
This takes a lot of writing, and also requires us to introduce the variable there exists such that ".(which often just adds complexity). So, we will abbreviate this to "
We will also abbreviate sums and products of all the values:denotes the sum of the and denotes their product. We won't worry too much about the indices; unless otherwise specified, we just mean add (or multiply) all of them.
Strengthing the inductive hypothesis
Sometimes, when doing an inductive proof, the inductive hypothesis doesn't quite say enough to be useful in the inductive step. In this situation, it can sometimes (ironically) be 'easier' to prove a stronger result than the original claim. Although this means you will have more to prove, it also means you will have more facts that you can use inside your inductive step.
For example, Here is a corrected version of the proof that Every natural number has a prime factorization wherein we strengthen the inductive hypothesis. You may find it useful to read them side by side to understand the differences.
There is a lot of technicality involved in this proof that doesn't really help explain what's going on; it is much clearer to write essentially the same proof using strong induction. This is an example to demonstrate that you can always rewrite a strong induction proof using weak induction.
The key idea is that, instead of proving that every number prime factorization, we prove that, for any given , every number has a prime factorization. Of course, this means that itself has a prime factorization, but by proving even more, we allow our inductive step to go through.has a
If we knew that prime factorizations, then we could combine them to form a prime factorization of . But now we do know that! Since and , we see that ; similarly . Therefore we can apply to conclude that and have prime factorizations.We can therefore finish the proof: Let and had be the prime factorization of , and let be the prime factorization of . If we let be the sequence starting with the and ending with the s (in other words, ). Then clearly .
Strengthening the inductive hypothesis in this way (from to ) is so common that it has some specialized terminology: we refer to such proofs as proofs by strong induction:Strong induction is similar to weak induction, except that you make additional assumptions in the inductive step.
- prove base case), and (this is called the
- for an arbitrary , prove , assuming (this is the inductive step)
More concisely, the inductive step requires you to prove for all .assuming
The intuition for why strong induction works is the same reason as that for weak induction: in order to prove , for example, I would first use the base case to conclude . Next, I would use the inductive step to prove ; this inductive step may use but that's ok, because we've already proved . I would then use the inductive step to conclude ; this may use both and , but that's okay because we've already proved and . Next, I would again use the inductive step to conclude ; as before, this may use , , or , but this is not a problem since we have already proved those three facts. Similarly, we can use the inductive step to conclude P(4), P(5), etc.
Note that you can always use strong induction instead of weak induction. Using weak induction is just a matter of style: by avoiding unneeded assumptions, you reduce the complexity of your proof, and clearly indicate to the reader what assumptions you are actually planning to use. I often start inductive proofs by not specifying whether they are proofs by strong or weak induction; once I know which inductive hypothesis I actually need, I go back and fill in the beginning of my inductive step.
We use strong induction to avoid the notational overhead of strengthening the inductive hypothesis. This proof has the simplicity of the incorrect weak induction proof, but it actually works. You should compare the three versions of the proofs to understand the differences.
Since prime factorizations.Let and must be less than , we can apply and to conclude that both and have be the prime factorization of , and let be the prime factorization of . If we let be the sequence starting with the and ending with the s (in other words, ). Then clearly .
While studying number theory, we will be primarily interested in the properties of the integers and natural numbers. This means that if we want to write something like " ", we'll have to be very careful to check that divides . This makes everything very complicated, so instead, we'll avoid dividing natural numbers.
In the latter case, we can let and . Then . Again it is clear that .In either case, we have shown that there exist and satisfying (1) and (2), as required.
Proofs and algorithms
Most proofs that something exists give you instructions for finding it. For example, inside the proof that the quotient and remainder exist, is an algorithm for finding them: If , follow the instructions in the base case; if , then first find the quotient q' and remainder r' for and , then follow the instructions in the inductive step. Of course, while we are finding and , we may need to also find the quotient and remainder of and , and so on.
We will cover several examples of such algorithms/proofs:
- The euclidean division algorithm
- The base b representation
- The Bézout coefficients
- The Proof:Cantor-Schroeder-Bernstein theorem
- The Prime factorization of a natural number
- most of the proofs] of existentially quantified statements.
In fact, there are whole programming languages where instead of writing a program, you write a proof; after the computer checks your proof, it extracts a program for you (which is guaranteed to be correct!).
Uniqueness of euclidean division
We havePlugging this back in to the equation , so . This means that is a multiple of ; it could be any of . However, since we have and , we have . Thus, the only possible value of is 0, so . shows that either or . Since we have defined the quotient and remainder by , we must have , so and thus .