When you see how to prove P(k+1) is true from the assumption that P(j) is true for all positive integers j not exceeding k, but yo ucannot see how to prove that P(k+1) follows from just P(k).
¶ Examples of Strong Induction (and why the use of Strong Induction was required)
Show that if n is an integer greater than 1, then n can be written as the product of primes.
Let P(n) be the proposition that n can be written as the product of primes.
Basis Step:P(2) is true because 2 can be written as the product of one prime, itself.
Inductive Step: The inductive hypothesis is assumption that P(j) is true for all integers j with 2≤j≤k. That is, j can be written as the product of primes whenver j is a positive integer at least 2 and not exceeding k.
To complete the inductive step, it must be shown that P(k+1) is true under this assumption, that is, that k+1 is the product of primes.
There are two cases to consider, when k+1 is prime and when k+1 is composite. If k+1 is prime, we immediately see that P(k+1) is true. Otherwise, k+1 is composite and can be written as the product of two positive integers a and b with 2≤a≤b<k+1. Because both a and b are integers at least 2 and not exceeding k, we can use the inductive hypothesis to write both a and b as the product of primes. Thus, if k+1 is composite, it can be written as the product of primes, namely, those primes in the factorization of a and thoser in the factorization of b.
Theorem: For all natural numbers n and m, if m>0, then there are natural numbers q and r such that n=mq+r and r<m (the numbers q and r are called the quotient and remainder when n is divided by m).
Scratch Work: We let m be an arbitrary positive integer and then we use strong induction to prove that ∀n∃q∃r(n=mq+r∧r<m) (for all n∈N there exists a q and r where n is equal to mq+r and r is less than m. According to strong induction, this means we should let n be an arbitrary natural number, assume that ∀k<n∃q∃r(k=mq+r∧r<m) ( P(n) is true for all n≤k) and prove that ∃q∃r(n=mq+r∧r<m).
The goal is an existential statement so we need to come up with values of q and r with the required properties.
If n<m we can just let q=0 and r=n (multiply a number by 0 and add the number to the product to get...itself).
If n≥m, this won't work, since we must have m>r, so we must do something different. The inductive hypothesis starts with ∀k<n, so to apply it we should plug in some nat num smaller than n for k, but what should we plug in?? If we think of division as repeated subtraction, then dividing n by m invovles subtracting m from n repeatedly. The first step would be to compute n−m, which is a natural number smaller than n. Perhaps we should plug in n−m for k. Note that we are using the fact that a quotient and remainder exist for some nat number smaller than n to prove they exist for n, but this smaller number is not n−1 its n−m. This is why we need strong induction.
Proof:
We let m be an arbitrary positive integer and then proceed by strong induction on n.
Suppose n∈N, and for every k<n there are natural numbers q and r such that k=mq+r and m>r.
We proceed by cases.
Case 1:n<m. Let q=0 and r=n. Then clearly n=mq+r and r<m. Case 2:n≥m. Let k=n−m<n and note that since n≥m, k is a natural number. By inductive hypothesis, we can choose q′ and r′ such that k=mq′+r′ and r′<m. Then n−m=mq′+r′, so n=mq′+r′+m=m(q′+1)+r′. Thus, if we let q=q′+1 and r=r′, then we have n=mq+r and r<m, as required. ■.
Scratch: Because F0 and F1 are defined separately from Fn for n≥2, we check the formula for these cases separately. For n≥2, the definition of Fn suggests that we should use the assumption that the formula is correct for Fn−2 and Fn−1 to prove it is correct for Fn. Because we need to know that the formula works for the two previous cases, we must use strong induction rather than regular induction.
Proof: We use strong induction. Let n be an arbitrary natural number, and suppose that for all k<n,