proving correctness, not plausibility

Imagine you wrote a program to sort a list. You run it on a handful of lists, the answers look right, and you declare victory. But you have only checked that it works on those few inputs. Maybe it breaks on an empty list, or on a list that is already sorted, or on one with repeated values. 'It looked right on my examples' is a feeling of plausibility, not a guarantee. Proving correctness means showing the algorithm gives the right answer on every allowed input, including the ones you never tried.

The difference is the difference between evidence and proof. Testing samples a few points in an enormous space of possible inputs; even billions of passing tests leave infinitely many untested cases. A correctness proof instead argues about all inputs at once, using a fixed, finite chain of reasoning. The main tools for this are the loop invariant (a property kept true on every pass of a loop) and mathematical induction (proving something for all sizes by proving a base case and a step). A typical proof says: state precisely what the algorithm is supposed to do, then show by invariant or induction that it always does exactly that, and finally show it always stops.

This matters because plausible-looking algorithms are wrong all the time: a binary search with an off-by-one bound, a greedy rule that is optimal on your examples but not in general, a recursion that loops forever on one weird input. Tests are still valuable and catch real mistakes cheaply, but they can only show the presence of bugs, never their absence. A proof is what lets you trust an algorithm you cannot exhaustively test.