Pdf 5 4 the strong induction principle p 48

Pdf File 90.03 KByte, 1 Pages

These are even more notes for Week 2's lectures. It does not cover all of the material discussed in lectures, but rather is intended to provided extra explanations of material related to the lectures.

The required text is Peter J. Eccles' book An Introduction to Mathematical Reasoning. The section and page numbers refer to his book.

5.4. The strong induction principle (p. 48)

The strong induction principle says that you can prove a statement of the form:

P (n) for each positive integer n.

as follows: Base case: P (1) is true. Strong inductive step: Suppose k is a positive integer such that P (1), P (2), . . . , P (k) are all true. Prove that P (k + 1) is true. So the key step is to show:

P (1), P (2), . . . , and P (k) = P (k + 1) .

So to speak, the statement is true if you can prove that: (1) The first domino has fallen. (2) If k is such that the first k dominos have fallen, then the (k + 1)th domino has fallen. We now give an example of a proof related to prime numbers using strong induction. Definition 2.2.1. (p. 16) Given two integers a and b, we say that b divides a if there is an integer q such that a = bq. Definition. An integer p 2 is called a prime number if the only positive integers that divide p are 1 and p. For example, the first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, ... Fact: If an integer c 2 is a not prime, then there exist integers a and b with 2 a, b c - 1 such that

c = a ? b.

Proposition. Every integer greater than 1 can be written as the product of prime numbers. Think of it this way: Let P (n) be the statement that n can be written as the product of prime numbers. Then the proposition says: P (n) is true for each integer greater or equal to 2. Proof (by strong induction). (1) Base case: 2 is a prime, so it is the product of a single prime. (2) Strong inductive step: Suppose for some k 2 that each integer n with 2 n k may be written as a product of primes. We need to prove that k + 1 is a product of primes. Case (a): Suppose k + 1 is a prime. Then we are done. Case (b): Suppose k + 1 is a not prime. Then by the fact stated above, there exist integers a and b with 2 a, b k such that

k + 1 = a ? b.

By the strong inductive hypothesis, since 2 a, b k, both a and b are the product of primes. Thus k + 1 = a ? b is the product of primes.

(3) We are done by strong induction.


Download Pdf File