How to Learn Algorithm Correctness Proofs: Preconditions, Loop Invariants, Induction and Termination

Wait, What?

A program can pass every test you wrote and still be wrong.

Testing tells us what happened on the cases we tried. A correctness proof asks a stronger question: why should this algorithm satisfy its specification for every valid input covered by the claim? That difference is one of the major transitions from learning to code toward learning to reason about algorithms.

Quick Answer

Learn correctness proofs in this order: state the contract → trace examples → identify what must remain true → prove initialization → prove preservation → connect termination to the required result → prove that termination actually occurs. For recursive algorithms, use a closely related structure: prove the base case, assume correctness on smaller instances, show the recursive step preserves the claim, and prove that each call moves toward a base case.

1. Start With the Contract, Not the Proof

A correctness argument cannot be stronger than the specification it is trying to prove. Write the problem contract first.

Precondition: what must be true before the algorithm starts?
Postcondition: what must be true when the algorithm finishes?
Domain: which inputs are covered?
Output meaning: what exactly does a returned value certify?
Failure behaviour: what happens when no valid answer exists?

For binary search, “find a target” is too vague. The sortedness assumption matters. So does the meaning of “not found.” If the precondition is omitted, a proof may quietly rely on a property that the caller never promised.

2. Trace Before You Prove

Novices are often asked to invent an invariant before they can see what the algorithm is preserving. Reverse that order. Trace several executions and ask what remains true after every completed iteration.

What part of the input has already been settled?
What part remains unresolved?
Which relationship between variables is still guaranteed?
What information has never been discarded?
What fact would make the final postcondition almost automatic once the loop stops?

This turns an invariant from a mysterious sentence into a compressed description of repeated algorithm behaviour.

3. Learn the Three-Part Loop-Invariant Proof

Initialization. Show that the invariant is true before the first iteration begins.

Preservation. Assume the invariant is true at the start of an iteration and show that executing the body restores it for the next iteration.

Termination link. When the loop condition becomes false, combine that fact with the invariant to derive the postcondition. If the invariant does not help you reach the required result, it may be true but too weak.

Cornell’s CS 2112 notes present the same core structure as establishment, preservation and using the invariant to reason about the final state. See Cornell CS 2112 lecture material on loop invariants and correctness.

4. Correctness Also Requires Termination

Showing that a loop would be correct if it stops is only partial correctness. To establish total correctness, also show that execution cannot continue forever under the stated preconditions.

A common technique is to identify a non-negative quantity that strictly decreases on every iteration. Depending on the algorithm, that quantity might be the number of unresolved items, the width of a search interval, remaining capacity, or another well-founded measure.

5. Recursive Correctness Uses Induction

For recursive algorithms, the proof often mirrors mathematical induction.

Base case: prove the smallest valid instance is handled correctly.
Inductive hypothesis: assume recursive calls correctly solve the smaller instances they receive.
Inductive step: prove that combining those correct smaller results produces a correct result for the current instance.
Progress: prove recursive calls actually move toward a base case.

6. A Worked Learning Pattern: Binary Search

A strong way to learn the proof is not to memorise a finished paragraph. Reconstruct the proof around the unresolved search interval. Ask: if the target exists, where can it still be? Why is discarding half the interval safe after each comparison? Why does the interval shrink? What does an empty interval mean?

This connects naturally to How to Learn Searching Algorithms, which owns the search-learning pathway. This page owns the general proof method.

7. Proof Failure Modes

Testing disguised as proof: “It worked on ten examples.”
Restating the goal: the proposed invariant is simply the final result and has not been shown to hold during execution.
True but useless invariant: the statement is preserved but cannot imply the postcondition.
Missing boundary case: empty, singleton or duplicate inputs fall outside the argument.
Hidden precondition: sortedness, uniqueness or positivity is assumed without being stated.
Missing termination argument: preservation is proved but infinite execution has not been excluded.
Implementation drift: the proof describes one algorithm while the code implements a subtly different one.

8. The Scaffold-Fade Learning Ladder

Level 1: trace a complete worked algorithm and highlight what stays true.
Level 2: complete missing parts of a proof skeleton.
Level 3: choose between several candidate invariants and justify the choice.
Level 4: repair a deliberately weak or false invariant.
Level 5: derive an invariant from the postcondition and loop structure.
Level 6: prove a new algorithm with no supplied proof template.
Level 7: compare two correct algorithms and explain how their proofs reveal different structural ideas.

Programming-education research supports making procedural subgoals visible for novices and then fading support. Subgoal-labelled worked examples have improved near-term problem solving in introductory programming, although gains do not automatically transfer to every later assessment. See Margulieux, Morrison and Decker (2020). Parsons-style ordering tasks can reduce syntax demands while learners focus on structure; see Szabo et al. (2025).

9. Immediate, Delayed and Transfer Checks

Immediate: can the learner explain each proof obligation?
Delayed: can they reconstruct the invariant after a gap?
Counterexample: can they break an incorrect proof claim?
Transfer: can they derive an invariant for a different loop structure?
Implementation alignment: can they show which exact code statements preserve the invariant?

10. AI Assistance Boundary

AI can be useful as a proof critic: ask it to search for a counterexample, question an unstated assumption or challenge a proposed invariant. But if it supplies the entire invariant and proof before the learner has tried to derive them, the most valuable reasoning step disappears. A stronger sequence is attempt → state claim → request critique → repair → reproduce independently.

Teaching Guide for Parents, Tutors and Teachers

When a learner says “I know it works,” do not immediately ask for formal notation. Ask progressively stronger questions: “What are you assuming about the input?”, “What remains true after every repetition?”, “Why is this case safely discarded?”, “What becomes smaller?”, and “How does the final state give the answer?” The goal is to make proof grow out of algorithm understanding rather than become a separate ritual.

Professional Direction

At professional and research levels, correctness arguments become more formal and may use specification languages, theorem provers or verified libraries. The foundational habit remains the same: define the claim precisely, expose assumptions, identify preserved structure, prove progress and keep the proof aligned with the implementation.

Algorithm-learning rule: a correctness proof is not decorative mathematics attached after coding. It is a disciplined explanation of why the algorithm’s structure is sufficient to deliver the promised result for the entire stated input domain.