loopinvariants

Loop invariants are conditions that must hold before and after every iteration of a loop. They are a central tool in reasoning about program correctness, linking the state at the start of the loop to the state after it finishes.

To prove a loop correct, one typically shows three properties. Initialization: the invariant holds before the first iteration. Maintenance: if the invariant holds at the start of an iteration, the loop body preserves it. Termination: when the loop exits, the invariant together with the negation of the loop condition implies the loop’s postcondition. If these are established, the loop satisfies its specification.

Common examples include maintaining partial results such as sums or maxima, or preserving data-structure properties. Example: to sum an array A[0..n-1], initialize S = 0 and i = 0. The invariant can be stated as S equals the sum of A[0..i-1] and i is the number of processed elements. Initialization holds with S = 0 and i = 0. Maintenance: after processing A[i], S becomes the sum of A[0..i], and i increments to i+1, preserving the invariant. Termination: when i = n, S equals the sum of all elements, the desired postcondition.

Loop invariants are used in formal verification methods such as Hoare logic and weakest preconditions, and in software verification tools. They can express data-structure invariants and loop-carried properties. A well-chosen invariant is neither too strong nor too weak; a poorly chosen invariant can prevent proving correctness or conceal bugs. In addition to the invariant, a loop variant—a measure that decreases with each iteration—is often used to prove termination.