STEP-BY-STEP LESSON · §5.4
Strong Mathematical Induction and the Well-Ordering Principle for the Integers
Understand why strong induction makes all smaller cases available.
Before you begin
Mathematical Induction I: Proving Formulas
P(n) must be a specific statement for every integer n in the stated range.
P(n): 1+2+…+n = n(n+1)/2, n≥1
Verify P(1) separately. Then choose arbitrary k≥1 and temporarily assume P(k).
1 = 1·2/2
Split the sum through k+1 into the known sum through k and the final term.
k(k+1)/2+(k+1)=(k+1)(k+2)/2
Direct Proof and Counterexample I: Introduction
Integer n is even iff there is an integer k with n=2k. Evenness gives this representation, and the representation gives evenness.
n even ↔ ∃k∈ℤ: n=2k
For “every odd integer has an odd square”, testing 3,5,7 suggests a pattern but leaves infinitely many cases. Write an arbitrary odd integer as 2k+1 with integer k; no special value is assumed.
n=2k+1; k∈ℤ
Symbols
- 2≤j≤k
- all indices from 2 through k
- P(j)
- a statement about the integer index j
Definitions and notation for this topic
Mathematical induction
To establish P(n) for all integers n≥n₀, prove P(n₀), then prove P(k)→P(k+1) for an arbitrary integer k≥n₀.
The base starts the argument and the arbitrary step propagates it. A displayed P(k)→P(k+1) alone omits the base and is not a complete induction proof.
Separate glossary example
For n≥1, 1+…+n=n(n+1)/2. Base n=1: 1=1. If the formula holds at k, add k+1 to get (k+1)(k+2)/2.
P(1); for every k≥1, P(k)⇒P(k+1).
Strong induction
To prove P(n) for integers n≥n₀, prove the starting case, then prove P(k+1) using the hypothesis that P(j) holds for every n₀≤j≤k.
The smaller factors need not equal n−1, so access to all earlier cases is useful. State enough base cases for the recurrence or construction actually used.
Separate glossary example
Every integer n≥2 is a product of primes. Base: 2. If n is composite, write n=ab with 2≤a,b<n and apply the hypothesis to both factors; if n is prime, it is already a one-factor product.
Step by step
Step 1 / 6
Broaden the assumption
For our example, P(n) says that integer n≥2 has a prime factorization. To prove P(k+1), assume P(j) for every integer j from 2 through k. Strong induction permits all these earlier cases, not just P(k).
P(2),P(3),…,P(k) ⇒ P(k+1)
The earlier index needed may depend on the object.
Worked example
Why does every integer n≥2 have a prime factorization?
- Base n=2: it is prime, a product with one prime factor.
- Assume the claim for 2,…,k. If k+1 is prime, we are done.
- If k+1=ab is composite, both factors lie between 2 and k. Factor them using the hypothesis and combine the products.
Optional self-check
Why can cases 3 and 4 be used for n=12?
Show answer
12=3·4; both indices are below 12 and at least the starting value 2.