You want to prove that every amount of postage ≥ 12 cents can be made from 4-cent and 5-cent stamps. To show amount n+1 works, you argue: if n+1 ≥ 17, subtract a 4-cent stamp to get n−3, which must be achievable. But n−3 could be far less than n. Which proof technique is required?
AWeak induction — you only need the previous case (n) to prove n+1.
BStrong induction — the step for n+1 may require cases far below n, not just n itself.
CDirect proof — the result can be verified without induction by a closed-form argument.
DProof by contradiction — assume postage n+1 is impossible and derive a contradiction.
Weak induction hands you only the hypothesis that n works. But when n+1 = 17, you need the hypothesis for 17 − 4 = 13, which could be far below n. Weak induction's single-step hypothesis doesn't reach back to 13. Strong induction's hypothesis — 'all values from the base case up through n work' — covers 13 directly, making the step go through. Whenever the inductive step looks back more than one case, strong induction is the natural tool.
Question 2 Multiple Choice
Why does the proof that every integer n ≥ 2 has a prime factorization require strong induction rather than weak induction?
ABecause n+1 may not equal the 'next' integer in the context of factorization.
BBecause if n+1 is composite, its factors a and b satisfy 2 ≤ a, b < n+1 — requiring the hypothesis for values other than n.
CBecause the base case n = 2 is insufficient to start the induction.
DBecause weak induction does not apply when the domain starts at 2 rather than 1.
If n+1 is composite, it factors as a·b with 2 ≤ a, b < n+1. To argue both a and b have prime factorizations, you need the inductive hypothesis at a and b — which could be as small as 2. Weak induction gives you only the hypothesis at n, which is useless when a = 3 and n = 100. Strong induction's hypothesis 'all integers from 2 through n have prime factorizations' covers every possible factor pair, making the step work for all composite values of n+1.
Question 3 True / False
Strong induction is logically more powerful than weak (ordinary) induction — there exist theorems that can be proved by strong induction but not by weak induction.
TTrue
FFalse
Answer: False
Strong and weak induction are logically equivalent. Any proof by strong induction can be converted to a proof by weak induction by reformulating the predicate: instead of P(n), use Q(n) defined as 'P(k) holds for all k from the base case up to n.' Then weak induction on Q(n) simulates strong induction on P(n) exactly. The choice between them is purely pragmatic: strong induction produces cleaner proofs when the step naturally reaches back multiple cases, without any gain in logical strength.
Question 4 True / False
When using strong induction on a property involving the Fibonacci recurrence Fₙ = Fₙ₋₁ + Fₙ₋₂, the base case must establish the property for both F₁ and F₂.
TTrue
FFalse
Answer: True
The Fibonacci step for F₃ requires both F₂ and F₁. If only F₁ is verified as the base case, the strong inductive hypothesis for n = 2 has only one data point (F₁), and the step for F₃ cannot draw on F₂. You must establish all initial values needed by the recurrence before the strong hypothesis has enough coverage to carry the step. In general, for a recurrence looking back k steps, the base case must verify k starting values.
Question 5 Short Answer
Explain why the inductive step in a strong induction proof can 'look back' multiple cases, and why weak induction's hypothesis is insufficient in those situations.
Think about your answer, then reveal below.
Model answer: Weak induction's hypothesis at step n+1 is only 'P(n) holds.' If the proof of P(n+1) requires P(k) for some k < n, that hypothesis simply does not cover it — the step fails. Strong induction's hypothesis is 'P(k) holds for all k from the base case through n,' which covers every value below n+1 no matter how far back the step reaches. The inductive step can freely cite P(2), P(7), or P(n−3) alike. The tradeoff is only notational: you must state the hypothesis carefully and ensure the base case covers all special cases at the bottom of the recurrence.
Logically, strong induction is no stronger — the two forms are equivalent. But strong induction makes the fuller hypothesis explicit and available at each step, producing proofs that mirror the structure of the argument (especially for recurrences, divisibility arguments, and combinatorial decompositions). The key diagnostic question when drafting an inductive proof is: does the step use only P(n), or does it need P(k) for some k < n? If the latter, use strong induction from the start.