objective and principle of strong induction
Answers
Answer:
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.
Step-by-step explanation: