skip to content

Strong & Structural Induction

14 roadmaps5 questions

Proving a claim for every n from a base case and a step, including strong induction and induction over a tree. Interviewers probe it when a recursive routine needs a correctness argument.

part ofComputer science fundamentalsoverview, primer and where to startread it →
on this pageshow

explore

questions

5

When a reviewer calls an induction proof circular, what does the inductive hypothesis actually let you assume?

level: middleimportance: must knowfreq 62%

answer

  1. two obligations, not one
  2. an implication, not a fact
  3. modus ponens, repeated
  4. the base anchors the chain
  5. smaller cases only

basics

~20 s

Only smaller cases, never the case being proved. The step establishes an implication - if the claim holds at k, it holds at k+1 - and the base case supplies the first true instance, so nothing is assumed about the target.

solid answer

~40 s

An induction proof has two obligations. The base case establishes the claim outright at the smallest value it covers. The inductive step establishes an *implication*: assuming `P(k)`, derive `P(k+1)`. The step never asserts that `P(k)` is true, so it never assumes the conclusion; it shows that truth propagates. Combine the two and you have a recipe that produces, for any particular n, a finite chain of steps from the base up to n. Circularity would mean using `P(n)` while proving `P(n)` - assuming a smaller, already-linked case is the opposite of that. The base case is what makes the chain start somewhere true: without it you have a valid implication chain anchored to nothing.

go deeper

for a junior

Recall the two parts by name - a base case proved outright, and a step that moves from one value to the next - and that the step is where the hypothesis is allowed.

for a middle

Explain that the step proves an implication rather than a fact, and unroll it for a small n so the chain of detachments is visible. That unrolling is the answer to the circularity objection.

for a senior

Show where real arguments break: a valid step with no base, or a step whose own reasoning needs k above the base. Say what range of n the proof therefore covers.

for a principal

Frame it as a proof obligation on a design: which claims about a system are worth stating in a form that induction can discharge, and who re-checks them when the definition underneath changes.

Induction proves a statement `P(n)` for infinitely many values of `n` by proving two finite things. The "it assumes what it proves" objection comes from misreading the second one. ## The two obligations 1. **Base case.** Establish `P(n0)` outright for the smallest value the claim covers, by direct argument and with no hypothesis available. 2. **Inductive step.** Establish the implication `P(k) -> P(k+1)` for every `k >= n0`. Inside this argument you may use `P(k)`, the **inductive hypothesis**, as a premise. That is the whole proof. What you have when both are done is not a single statement about "a general n" but a *generator*: a finite procedure that, for any specific n you name, produces a finite proof of `P(n)`. ## Why assuming P(k) is not assuming the conclusion The step does not claim that `P(k)` holds. It claims that *if* it held, `P(k+1)` would follow. That implication can be true even when both sides are false, and proving it commits you to nothing about the truth of either side. The truth enters exactly once, at the base case. The cleanest way to see this is to unroll. Suppose the base is `P(1)` and you want `P(5)`: - `P(1)` is proved directly. - The step at `k = 1` gives `P(1) -> P(2)`; with `P(1)`, detach `P(2)`. - The step at `k = 2` gives `P(2) -> P(3)`; detach `P(3)`. - Two more detachments give `P(4)` and then `P(5)`. Every link is an ordinary application of a proved implication to an already-established fact. Nothing in that chain ever used `P(5)` to get `P(5)`. Induction is the observation that you do not have to write the chain out - proving the base and the generic step guarantees the chain exists for every n. ## What the hypothesis may and may not do | Move | Legitimate? | Why | |---|---|---| | Use `P(k)` while deriving `P(k+1)` | Yes | This is the hypothesis; the step is an implication | | Use `P(j)` for every j from the base up to k | Yes | The strong form, sound for the same reason | | Use `P(k+1)` while deriving `P(k+1)` | No | Genuinely circular - the conclusion as its own premise | | Use `P(k+2)` to get `P(k+1)` | No | The hypothesis reaches downward, not upward | | Verify a handful of values of k | No | The step must hold for **every** k in range | The fourth row is worth dwelling on. Direction is the thing beginners lose: the argument flows from smaller to larger, so the hypothesis is only ever about cases the chain has already reached. ## What actually goes wrong Real broken proofs rarely fail by circularity. They fail in two other ways: - **No base case.** The claim `n = n + 1` has a perfectly valid step: if `n = n + 1`, then adding one to both sides gives `n + 1 = n + 2`. The step is genuinely correct, and the claim is genuinely false, because no instance is ever established. A valid step with no anchor proves nothing at all. - **A step that does not cover its whole range.** If the argument inside the step quietly needs `k >= 3` - it splits something into two non-empty pieces, or assumes a node has two children - then the implications below that point were never proved, and the chain cannot climb past the missing link. A third, softer failure is checking `P(1)`, `P(2)`, `P(3)` and declaring the pattern proved. Sampling is evidence for a conjecture, not a proof; the step is what turns finitely many checks into a claim about every n. ## How to say it in an interview When challenged on circularity, name the implication. "I am not asserting the claim at k; I am proving that the claim at k forces it at k+1. The base case is where anything is asserted, and it is proved without a hypothesis." Then offer the unrolling: for n = 5, here are the five links, each one modus ponens. That answer takes fifteen seconds and settles the objection, because it shows the proof is a finite recipe rather than a leap.

  • If the inductive step is proved for every k but the base case is never checked, what has been established?
    Only a conditional chain hanging on nothing. The claim `n = n + 1` has a valid step - add one to both sides - yet it is false for every n, precisely because no instance is ever established directly. The base case is the sole point where truth enters the argument.
  • Must the base case be at the smallest number the claim mentions?
    No. You prove the claim for all `n >= n0` and pick `n0` to suit the argument. What matters is that the statement you are proving says `n >= n0` too. Values below `n0` are simply outside the claim; if the result is needed there, they must be handled separately.
  • Why must the step be proved for a generic k rather than for several sample values?
    Because the chain must have a link at every position. A step verified at k = 1, 2, 3 gives three implications and nothing above P(4). The generic argument is what produces infinitely many links from one page of reasoning.

It is the domino rule: you show each tile is close enough to knock the next one over, then you push exactly one tile. Spacing the tiles proves nothing until something falls.

saying these in an interview costs you the question

  • Says induction assumes the very thing it proves
  • Checks a few values of n and calls the claim proved
  • Treats the base case as optional bookkeeping
  • Uses the hypothesis at a larger value than the case in hand
  • Proves the step only at the base value of k
  • Cannot say what the step's conclusion is without the hypothesis
open as a page

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

level: middleimportance: must knowfreq 52%

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.

open as a page

A recursive routine works on large inputs but fails on two-block inputs, yet its induction proof checked a one-block base case - where is the gap?

level: seniorimportance: should knowfreq 38%

basics

~20 s

Almost certainly in the step's own preconditions: it needs more than one block before its argument applies, so it never links the one-block base to the next size up. Because every later case rests on the missing ones, nothing above the base is proved.

open as a page

For a hash tree defined recursively over data blocks, how do you prove a property of every such tree without an integer n?

level: seniorimportance: should knowfreq 44%

basics

~20 s

Induct over the data definition instead of a number: prove the property for each base constructor, such as a leaf holding one block, then for each combining constructor while assuming it of the immediate subtrees. Every finitely built tree is then covered.

open as a page

A proposal adds a third node kind to a recursively defined hash tree - how should the induction burden it creates weigh in that decision?

level: principalimportance: nice to knowfreq 22%

basics

~20 s

Every constructor in a definition is a case in every structural-induction argument over it, for all the properties and all the years that definition lives. Price the new kind as one extra case per property, and prefer a derived form that expands into the existing constructors.

open as a page