Study guides · Introductory

Induction and loop invariants: explain why repetition is correct

Use initialization, maintenance, and termination to reason about a loop that sums an array.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Turn repeated success into a general argument
  2. State an invariant for a sum
  3. Use the exit condition and prove progress
  4. Keep the mathematical model aligned with execution
  5. Use the empty case to inspect initialization
  6. Ask Logeia about this articleCheck your understanding

Turn repeated success into a general argument

A few successful runs do not establish correctness for arrays of every length. Mathematical induction proves a starting case and shows that an assumed property at one stage carries to the next. Loop invariants adapt this idea to program execution. Choose a statement that remains true at a precise point in every iteration and connects the program state to its intended result, rather than merely describing the next instruction.

State an invariant for a sum

Let i be the index of the next element to read and total the running sum. An appropriate invariant says that total equals the sum of elements with indices from zero up to, but not including, i. Initially i and total are zero, so the processed range is empty and its sum is zero. Adding a[i] and advancing i preserves the statement because exactly that element joins the processed range.

python
values = [2, 4, 6]
total = 0
for i in range(len(values)):
    # Before this addition, total == sum(values[:i]).
    total += values[i]

Use the exit condition and prove progress

When the loop exits with i equal to the array length n, the invariant implies that total equals the sum of the whole array. This establishes what is true if the loop finishes. To show that it does finish, consider the number of unprocessed elements, n minus i. It is a nonnegative integer that decreases on every iteration. Separating partial correctness from termination prevents an argument from overlooking an infinite loop that would never return its otherwise correct answer.

Keep the mathematical model aligned with execution

The reasoning assumes stable array contents and an arithmetic model in which the sum is representable. A fixed-width integer can overflow even when the mathematical argument is correct over unbounded integers. Concurrent mutation can also invalidate the relation between the processed prefix and the stored total. Write down such assumptions before claiming correctness. Tests can investigate implementation boundaries and violations of those assumptions, while the invariant explains the general relationship maintained by the algorithm.

Use the empty case to inspect initialization

For an empty array, the loop performs no iterations. The initialized value zero is nevertheless the correct sum, and the same invariant and exit reasoning explain why. No unrelated special case is necessary. Now imagine initializing the total to one and identify the first proof obligation that fails. This counterexample makes the initialization step concrete and shows how boundary inputs can reveal a mismatch between a proposed invariant and the actual program state.

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

Learn this in order

Build your CS foundations · STEP 14

Choose a learning path