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?

The failure here is not a subtle logical error. It is an accounting error: the proof covers a smaller set of inputs than its author thought, and the uncovered sizes are precisely the small ones nobody exercises. ## The coverage set Every induction proof implicitly defines a set: the sizes it actually establishes. That set is - the sizes discharged directly as base cases, plus - the sizes the step can produce, given that everything it depends on is already in the set. So the review question is never "is the step valid?" but "**for which k is the step's own argument valid**, and what does it need in hand when it fires?" ## Where the hidden precondition hides Steps rarely announce their preconditions. Typical smuggled assumptions: - "Split the input into two non-empty parts" - impossible below two blocks. - "Each part is itself a combining node with two children" - needs at least two blocks per part, so at least four overall. - "Take the middle element" - assumes an odd count, or at least a non-empty remainder. - "For n large enough, the term dominates" - honest, and frequently never converted into a stated threshold. Each of these raises the smallest k at which the step is genuinely proved, and none of them raises the base case to match. ## Why the gap does not stay local Suppose the base is size 1 and the step's argument needs two parts of at least two blocks each, so it first applies at size 4 and it needs sizes 2 and 3 available. 1. Size 1: established, directly. 2. Sizes 2 and 3: the step cannot produce them - its argument does not apply - and no base case covers them. Unproved. 3. Size 4: the step applies, but it consumes the claim at sizes 2 and 3. Those are unproved, so nothing is derived. 4. Size 5 and beyond: each one depends on smaller sizes that include the unproved ones. The failure propagates. The naive reading - "only sizes 2 and 3 are missing" - understates it. **Everything above the gap collapses with it**, and the proof supports only the base case. That is the answer an interviewer is listening for, because it explains why the routine "works on large inputs": it was never proved to, it was only tested to. ## How to audit a proof for this in two minutes | Ask | Write down | |---|---| | What sizes are proved directly? | The base set | | What is the smallest k for which every sentence of the step is true? | The step's threshold | | What does the step consume when it fires? | Its dependencies | | Is every dependency in the covered set? | If not, the gap | Do this and off-by-one base cases stop being a matter of luck. In practice the fix is mechanical: add base cases for every size below the step's threshold, then check the routine really does behave correctly on those sizes - which is where a genuine bug usually surfaces, because the small cases are the ones written last and tested least. ## The two symmetric mistakes - **Base too low.** The one above: a base at size 1 under a step that begins at 4. - **Base too high.** The claim says "for all n >= 1" but only n = 3 is discharged and the step climbs upward, so sizes 1 and 2 are outside the proof while inside the claim. Either restate the claim as `n >= 3` or prove the small cases. Both are caught by the same discipline: write the range in the claim, write the range the step covers, and compare them explicitly instead of trusting that they line up. ## What this looks like on the ground A correctness argument that silently starts at four blocks, paired with test data that never goes below a hundred, is a defect waiting for the first empty or single-item input in production. The mathematics is not decoration here: the sizes the proof cannot reach are a precise list of the inputs nobody reasoned about.