SP20:Lecture 13 Strong induction and Euclidean division

From CS2800 wiki

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 quotient and remainder.

Notation: sequences

In this lecture, we will use a bit of shorthand for representing (finite) sequences:

We often want to prove that there exists a sequence of values [math]a_0, a_1, \dots, a_k [/math], all in [math]X [/math], satisfying some property. Formally, we would say "there exists [math]k \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] and values [math]a_0, a_1, \dots, a_k \href{/cs2800/wiki/index.php/%E2%88%88}{∈} X [/math] such that [math]\dots [/math]".

This takes a lot of writing, and also requires us to introduce the variable [math]k [/math] (which often just adds complexity). So, we will abbreviate this to "there exists [math](a_i) \href{/cs2800/wiki/index.php/%E2%88%88}{∈} X [/math] such that [math]\dots [/math]".

We will also abbreviate sums and products of all the values: [math]\sum_i a_i [/math] denotes the sum of the [math]a_i [/math] and [math]\prod_i a_i [/math] denotes their product. We won't worry too much about the indices; unless otherwise specified, we just mean add (or multiply) all of them.

Note: there is ambiguity in this notation about whether we allow finite or infinite sequences. I will only use this notation for finite sequences.

Strong induction

In the last lecture, we tried to prove that every natural number has a prime factorization.

We begin this lecture by showing how to modify that proof by strengthening the inductive hypothesis, and then we introduce the general technique of strong induction.

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 [math]n [/math] has a prime factorization, we prove that, for any given [math]n [/math], every number [math]2, 3, 4, \dots, n [/math] has a prime factorization. Of course, this means that [math]n [/math] itself has a prime factorization, but by proving even more, we allow our inductive step to go through.

For all [math]n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], if [math]n ≥ 2 [/math] then there exists prime numbers [math]a_0, a_1, \dots, a_k [/math] with [math]n = a_1 \cdot a_2 \cdots a_k [/math].
We will prove the claim using weak induction, but with a strengthened induction hypothesis. Let [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math] be the statement "for all [math]k [/math] with [math]2 ≤ k ≤ n [/math], there exists prime numbers [math](a_i) [/math] with [math]k = \prod_i a_i [/math]. We will prove [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(2)} [/math] and [math]P(n) [/math] assuming [math]P(n-1) [/math].

In the base case, when [math]n = 2 [/math], we will choose an arbitrary [math]k [/math] between [math]2 [/math] and [math]2 [/math]; we see that [math]k [/math] must be 2. 2 is prime. Therefore, we can choose [math]a_0 = 2 [/math]; clearly [math]2 = 2 [/math].

For the inductive step, we assume [math]P(n-1) [/math]; our goal is to show [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math], in other words that every [math]k ≤ n [/math] has a prime factorization.

Choose an arbitrary [math]k ≤ n [/math]. Since [math]k [/math] and [math]n [/math] are natural numbers, we see that either [math]k ≤ n-1 [/math] or [math]k = n [/math]. If [math]k ≤ n-1 [/math], then we can apply [math]P(n-1) [/math] to find a prime factorization for [math]k [/math]. Thus, the only remaining case is when [math]k = n [/math].

There are two cases: [math]n [/math] could be prime or composite. If [math]n [/math] is prime, we can proceed as in the base case: simply choose [math]a_0 = n [/math].

If, on the other hand, [math]n [/math] is composite, then we know that [math]n = ab [/math] for some natural numbers [math]a [/math] and [math]b [/math].

If we knew that [math]a [/math] and [math]b [/math] had prime factorizations, then we could combine them to form a prime factorization of [math]n [/math]. But now we do know that! Since [math]a \gt 1 [/math] and [math]n = ab [/math], we see that [math]b \leq n - 1 [/math]; similarly [math]a \leq n - 1 [/math]. Therefore we can apply [math]P(n-1) [/math] to conclude that [math]a [/math] and [math]b [/math] have prime factorizations.

We can therefore finish the proof: Let [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(a_i)} [/math] be the prime factorization of [math]a [/math], and let [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(b_i)} [/math] be the prime factorization of [math]b [/math]. If we let [math](c_i) [/math] be the sequence starting with the [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(a_i)} [/math] and ending with the [math]\href{/cs2800/wiki/index.php/Sequence_notation}{b_i} [/math]s (in other words, [math]c_0, c_1, \dots = a_0,a_1,\dots,a_p,b_0, b_1, \dots, b_q [/math]). Then clearly [math]n = \prod c_i [/math].

Strong induction

Strengthening the inductive hypothesis in this way (from [math]P(n) [/math] to [math]∀k ≤ n, P(n) [/math]) 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.

To prove "for all [math]n \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], P(n)" by strong induction, you must

  • prove [math]P(0) [/math] (this is called the base case), and
  • for an arbitrary [math]n [/math], prove [math]P(n) [/math], assuming [math]P(n-1),P(n-2),\dots,P(0) [/math] (this is the inductive step)

More concisely, the inductive step requires you to prove [math]P(n) [/math] assuming [math]P(k) [/math] for all [math]k \lt n [/math].

The difference between strong induction and weak induction is only the set of assumptions made in the inductive step.

The intuition for why strong induction works is the same reason as that for weak induction: in order to prove [math]P(5) [/math], for example, I would first use the base case to conclude [math]P(0) [/math]. Next, I would use the inductive step to prove [math]P(1) [/math]; this inductive step may use [math]P(0) [/math] but that's ok, because we've already proved [math]P(0) [/math]. I would then use the inductive step to conclude [math]P(2) [/math]; this may use both [math]P(0) [/math] and [math]P(1) [/math], but that's okay because we've already proved [math]P(0) [/math] and [math]P(1) [/math]. Next, I would again use the inductive step to conclude [math]P(3) [/math]; as before, this may use [math]P(0) [/math], [math]P(1) [/math], or [math]P(2) [/math], 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.

Here is a simplified version of the proof that every natural number has a prime factorization.

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.

For all [math]n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], if [math]n ≥ 2 [/math] then there exists prime numbers [math]a_0, a_1, \dots, a_k [/math] with [math]n = a_1 \cdot a_2 \cdots a_k [/math].
Proof: using strong induction
We will prove the claim using strong induction. Let [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math] be the statement that "there exists prime numbers [math]a_0, a_1, \dots, a_i [/math] with [math]n = a_1 \cdot a_2 \cdots a_i [/math]. We will prove [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(2)} [/math] and [math]P(n) [/math] assuming [math]P(0), P(1), \dots, P(n-1) [/math].

In the base case, when [math]n = 2 [/math] we see that 2 is prime. Therefore, we can choose [math]a_0 = 2 [/math]; clearly [math]2 = 2 [/math].

For the inductive step, we assume [math]P(n-1), P(n-2), \dots, P(2) [/math] (or in other words, we strong induction [math]P(k) [/math] for all [math]k \lt n [/math]; our goal is to show [math]P(n) [/math], in other words that [math]n [/math] has a prime factorization.

There are two cases: [math]n [/math] could be prime or composite. If [math]n [/math] is prime, we can proceed as in the base case: simply choose [math]a_0 = n [/math].

If, on the other hand, [math]n [/math] is composite, then we know that [math]n = ab [/math] for some natural numbers [math]a [/math] and [math]b [/math].

Since [math]a [/math] and [math]b [/math] must be less than [math]n [/math], we can apply [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(a)} [/math] and [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(b)} [/math] to conclude that both [math]a [/math] and [math]b [/math] have prime factorizations.

Let [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(a_i)} [/math] be the prime factorization of [math]a [/math], and let [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(b_i)} [/math] be the prime factorization of [math]b [/math]. If we let [math](c_i) [/math] be the sequence starting with the [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(a_i)} [/math] and ending with the [math]\href{/cs2800/wiki/index.php/Sequence_notation}{b_i} [/math]s (in other words, [math]c_0, c_1, \dots = a_0,a_1,\dots,a_p,b_0, b_1, \dots, b_q [/math]). Then clearly [math]n = \prod c_i [/math].

Variations on induction

There are many variants of induction: For example, in the inductive step, you may assume [math]P(n-1) [/math] and prove [math]P(n) [/math]:

To prove [math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php?title=Natural_numbers&action=edit&redlink=1}{\mathbb{N}} [/math] by weak induction, you can prove [math]P(0) [/math] and prove [math]P(n) [/math] for an arbitrary [math]n\gt 0 [/math], assuming [math]P(n-1) [/math].

This is just a change of variables, but it occasionally makes the notation a bit easier to work with.


There are other variants that you can use. For example, if you only care about [math]P(n) [/math] for [math]n \geq k [/math], you can use the following principle:

To prove [math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \geq k, P(n) [/math] using weak induction, you can prove [math]P(k) [/math] and prove [math]P(n+1) [/math] for an arbitrary [math]n \geq k [/math], assuming [math]P(n) [/math].

This is also equivalent to weak induction.


In fact, one can even convert a proof by strong induction into a proof by weak induction.


You can mix and match these variations. If you're using an unfamiliar variation, you should check that it makes sense intuitively, and if possible, show how to convert it to a proof by weak induction. For example, you should be sure to avoid a backwards proof while doing induction.

Proofs that variants are equivalent to the basic weak induction principle

In this lecture we argued that these variants are equivalent to the basic weak induction principle:

To prove "[math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \href{/cs2800/wiki/index.php/%5Cin}{\in} \mathbb{N},P(n) [/math]" using weak induction, you must prove [math]P(0) [/math] (this is often called the base case), and then you must prove [math]P(n+1) [/math] for an arbitrary [math]n [/math], assuming [math]P(n) [/math] (this is called the inductive step).

Here are links to the proofs; these are good exercises in using your proof techniques, although they can be a bit abstract:

Euclidean division

With these basic techniques (weak induction and strong induction) under our belt, we can begin the study of number theory.

For our purposes, refers to the study of the natural numbers and the integers. We will also introduce and study a closely related class of objects, the modular numbers.

Number theory is useful in several areas of computer science, including number representations, digital logic, information theory, and cryptography.

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 "[math]a/b [/math]", we'll have to be very careful to check that [math]b [/math] divides [math]a [/math]. This makes everything very complicated, so instead, we'll avoid dividing natural numbers.

We can, however, do division with remainder. The Euclidean division algorithm is just a fancy way of saying this:

For all [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] and all [math]b \gt 0 [/math], there exists numbers [math]q [/math] and [math]r \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] such that
  1. [math]a = qb + r [/math]
  2. [math]0 \leq r \lt b [/math]

Here [math]q [/math] and [math]r [/math] are the quotient and remainder of [math]a [/math] over [math]b [/math]:

Definition: Quotient
We say [math]q \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math] is a quotient of [math]a [/math] over [math]b [/math] if [math]a = qb + r [/math] for some [math]r \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math] with [math]0 \leq r \lt b [/math]. We write [math]q = quot(a,b) [/math] (note that quot is a well defined function).
Definition: Remainder
We say [math]r \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math] is a remainder of [math]a [/math] over [math]b [/math] if [math]a = qb + r [/math] for some [math]q \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math] and [math]0 \leq r \lt b [/math]. We write [math]r = rem(a,b) [/math] (note that rem is a well defined function).

Note that all this is a theorem, it is called the "Euclidean division algorithm" because its proof contains an algorithm.

Proof:
We prove this by weak induction on [math]a [/math]. Let [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(a)} [/math] be the statement "for all [math]b \gt 0 [/math], there exists [math]q, r \href{/cs2800/wiki/index.php/%E2%88%88}{∈} ℕ [/math] satisfying (1) and (2) above." We will show [math]P(0) [/math] and [math]P(a+1) [/math] assuming [math]P(a) [/math].


Base case: We want to show P(0). Let [math]q = r = 0 [/math]. Then [math]qb + r = 0b + 0 = 0 = a [/math] and [math]0 \leq r \lt b [/math] since [math]r = 0 [/math].


Inductive step: Assume [math]P(a) [/math]; we want to show [math]P(a+1) [/math]. By [math]P(a) [/math], we know that there exists numbers [math]q' [/math] and [math]r' [/math] such that [math]a = q'b + r' [/math]. We want to show that there exists numbers [math]q [/math] and [math]r [/math] such that [math]a + 1 = qb + r [/math].

Since [math]r' \lt b [/math], we know that either [math]r' + 1 \lt b [/math] or [math]r' + 1 = b [/math]. In the former case, we can let [math]q = q' [/math] and [math]r = r' + 1 [/math]. Then [math]qb + r = q'b + r' + 1 = a + 1 [/math] (and clearly [math]0 \leq r \lt b [/math]).

In the latter case, we can let [math]q = q' + 1 [/math] and [math]r = 0 [/math]. Then [math]qb + r = (q' + 1)b + 0 = q'b + (r' + 1) = a + 1 [/math]. Again it is clear that [math]0 \leq r \lt b [/math].

In either case, we have shown that there exist [math]q [/math] and [math]r [/math] satisfying (1) and (2), as required.