Concepts and theorems · Intermediate

Loop invariants: what remains true at iteration boundaries

Prove initialization, preservation, and the exit result for an array sum, then check termination separately.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. An invariant is a proposition
  2. A worked array-sum example
  3. Three proof obligations
  4. Termination needs another argument
  5. Ask Logeia about this articleCheck your understanding

An invariant is a proposition

A loop invariant is a proposition that holds at a specified boundary of each iteration. It does not mean that every variable keeps a constant value. An index and an accumulated sum can both change while the relationship between them remains true. State the boundary explicitly, such as immediately before testing the loop condition. An implementation can temporarily break the relationship inside the body and restore it before reaching that boundary again. This makes invariants a tool for describing progress precisely rather than a requirement that computation leave all state unchanged.

A worked array-sum example

For an array a of length n, initialize i=0 and s=0. Use the invariant that 0≤i≤n and s equals the sum of a[0] through a[i−1]. Initially the processed prefix is empty, whose sum is zero. While i<n, add a[i] to s and then increment i. At the next boundary, the processed prefix has gained exactly that element, preserving the statement. On exit, the invariant together with i≥n yields i=n and identifies s as the complete array sum.

python
def prefix_sum(a):
    i, s = 0, 0
    while i < len(a):
        # Invariant: s == sum(a[:i])
        s += a[i]
        i += 1
    return s

Three proof obligations

Separate initialization, preservation, and the final implication. A proposition such as i is an integer might remain true but be too weak to prove the desired sum. Conversely, an attractive final equation is not useful unless the initial state establishes it and every iteration preserves it. Array bounds and arithmetic semantics also belong in the reasoning. A mathematical proof using unbounded integers does not automatically justify a fixed-width implementation that can overflow. Match preconditions, invariant, and postcondition to the actual language behavior and the required result.

Termination needs another argument

Preserving an invariant alone does not prove that a loop terminates. In the sum example, n−i is a nonnegative integer that decreases on each iteration, supplying a separate termination argument. A faulty body that leaves i unchanged can preserve some true propositions indefinitely without reaching the goal. Tests can expose such failures for selected inputs, but do not replace reasoning about all inputs allowed by the precondition. Pair a useful invariant with a decreasing bounded measure so that the argument covers both the correctness of the result and eventual arrival at the exit.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 2

Choose a learning path