skip to content

Why does proving that every integer above 1 factors into primes require strong induction?

level: middleimportance: must knowfreq 52%

answer

  1. how much does the hypothesis give you
  2. one predecessor, or all smaller
  3. factors land wherever arithmetic puts them
  4. the split is not n minus one
  5. same power, different convenience

basics

~20 s

Because a composite splits as n = a times b, where a and b can be far smaller than n - 1. A previous-value hypothesis says nothing about them; the strong form assumes the claim for every value below n, which does cover both factors.

solid answer

~40 s

Ordinary induction hands you one hypothesis, `P(k)`, and asks for `P(k+1)`. Strong induction hands you `P(j)` for *every* j from the base up to `k`. The factorization argument needs the second shape: if n is prime it is its own factorization, and if n is composite then `n = a * b` with `1 < a, b < n` - but a and b are wherever the arithmetic puts them, perhaps 2 and n/2, not n - 1. With all smaller cases assumed, you take the factorizations of a and b and concatenate them. The two forms are equally powerful in principle: applying ordinary induction to the statement "the claim holds for every value up to k" yields the strong form. The difference is which hypothesis is *available in the shape the argument needs*.

go deeper

for a junior

Recall that the hypothesis can be given to you in two sizes: the previous value only, or every value below the one in hand. The second is called the strong form.

for a middle

Explain why a decomposition into unpredictable pieces forces the strong hypothesis, and walk the prime and composite branches of the factorization argument without notes.

for a senior

Spot the quiet defect in someone else's proof: a hypothesis cited at a size the decomposition never guarantees, and the smallest sizes left unchecked. Say which repair you would apply.

for a principal

Judge how much formal argument a recursive design warrants at all, and insist that the decomposition a proof assumes is the one the implementation actually performs.

The two forms of induction differ in one respect only: how much the hypothesis gives you. That difference decides whether an argument that splits a problem into unpredictable pieces can be written at all. ## The two hypotheses side by side | | Ordinary (weak) form | Strong form | |---|---|---| | Hypothesis available | `P(k)` alone | `P(j)` for every j with `n0 <= j <= k` | | Natural fit | Claims that grow by one - a sum, a counter, one more element | Claims where the case decomposes into pieces of unknown size | | Logical power | Same | Same | | Base cases | Usually one | Every size the step cannot decompose | The "same power" row surprises people. Define `Q(k)` to mean "`P(j)` holds for every j from the base to k". Ordinary induction applied to `Q` gives exactly strong induction on `P`. Neither form can prove something the other cannot; strong induction is a convenience, and the right question is never "is this claim strong enough for the weak form" but "does my step need facts about cases other than the immediate predecessor". ## Why factorization needs the strong hypothesis The claim: every integer `n >= 2` is a product of one or more primes. Fix n and assume the claim for every integer from 2 up to `n - 1`. 1. **n is prime.** Then n is already a product of one prime - itself. This case uses no hypothesis at all, which is why it doubles as the base: at `n = 2` there are no smaller cases and 2 is prime. 2. **n is composite.** By definition there are integers a and b with `n = a * b` and `1 < a < n`, `1 < b < n`. Both are strictly smaller than n, so the hypothesis applies to each. 3. **Concatenate.** The hypothesis gives a prime product for a and one for b; their concatenation is a prime product equal to `a * b`, which is n. Step 2 is where the weak form dies. The hypothesis would give you a factorization of `n - 1`, and `n - 1` is an entirely different number from a or b - knowing how 35 factors tells you nothing about 36. The step needs facts about the numbers the arithmetic actually produced, and it cannot predict which ones those will be. ## Applying the hypothesis to a size you do not actually get The mirror-image defect is common and quiet: writing a step that splits a structure and then invoking the hypothesis "at n/2" when nothing guarantees the split is even. If the decomposition can be lopsided - one part of size 1 and one of size n - 1 - the hypothesis you cited was never established for the sizes you got. There are two honest repairs: - Take the strong hypothesis, so *every* smaller size is available and the split may fall wherever it likes. - Or prove the split really is even, and then the weak-form citation at a fixed size is legitimate. What is not legitimate is naming a convenient size in the proof while the code or the arithmetic produces another. (Turning such a split into a running-time formula is a separate subject with its own owner; the point here is purely which hypothesis instances exist.) ## Where the base cases go A strong-induction proof often looks as though it has no base case, and that is a presentation habit rather than a licence. The honest rule: **the step must stand up when there are no smaller cases to assume.** In the factorization argument that happens at `n = 2`, where the hypothesis is empty and the prime branch carries the whole argument. If your step secretly needs at least one smaller case to exist, then the smallest sizes are unproved and must be discharged by hand. ## How this shows up in interviews Interviewers rarely ask "state strong induction". They ask why an argument about a recursive routine is incomplete, and the answer is usually one of three things: the hypothesis was cited at a size the decomposition does not guarantee; only the predecessor was assumed when the step needs more; or the smallest sizes were never checked. Naming which of the three, and which hypothesis shape repairs it, is the whole answer.

  • Is strong induction a logically stronger principle than the ordinary form?
    No - each derives the other. Apply ordinary induction to the statement "the claim holds for every value up to k" and you get the strong form. What differs is the shape of hypothesis available inside the step, which is a question of convenience, not of what is provable.
  • A routine splits its input into two parts of unpredictable sizes. Which hypothesis instances may its correctness step use?
    Any strictly smaller size, which is exactly the strong form. Citing the hypothesis "at half the input" is only sound if the split is guaranteed even; when it can be lopsided, the size you assumed is not the size you got, and the step is broken even though it reads plausibly.
  • Where is the base case in a factorization proof that never names one?
    At n = 2, where the hypothesis is empty and the prime branch alone must carry the argument. A strong-induction step is only base-case-free when it genuinely works with nothing assumed; if it quietly needs a smaller case to exist, the smallest sizes are unproved.

saying these in an interview costs you the question

  • Claims strong induction proves things ordinary induction cannot
  • Assumes a composite splits into n - 1 and 1
  • Cites the hypothesis at half the input when the split can be lopsided
  • Thinks a prime has no factorization at all
  • Forgets that both factors must be strictly below n
  • Skips the smallest sizes because the step 'obviously' covers them