S3U

Science / Programming basics / Undergraduate / scd70

Programming Basics: Prove a Loop Invariant

Prove that a counting loop sums the integers from 1 through n.

All worksheets
5 questions0m 0s

Prerequisites

Sequential program semantics, mathematical induction, logic and reasoning with unbounded integers.

Learn the skill

Use mathematical integers with no overflow and input n >= 0. Set i = 0 and total = 0. WHILE i < n: SET i TO i + 1; SET total TO total + i; END. At each loop head, invariant: 0 <= i <= n and total = i(i + 1)/2.

Worked example

For n = 3, loop-head states (i, total) are (0,0), (1,1), (2,3), (3,6). The invariant holds initially, survives each iteration and, with the false guard, gives total = n(n + 1)/2.

For n equal to three, the loop-head pairs of i and total are zero and zero, one and one, two and three, three and six. Each pair satisfies total equals i times i plus one divided by two.
For n equal to three, the loop-head pairs of i and total are zero and zero, one and one, two and three, three and six. Each pair satisfies total equals i times i plus one divided by two.
Question 1 What is total when n = 3 and the loop finishes?
Question 2 Why does the invariant hold initially?
Question 3 Which expression decreases by one on every iteration?
Question 4 At exit, what do i <= n and NOT(i < n) imply?
Question 5 Which assumption matters for the algebraic proof?

Further inquiry

Prove initialization and preservation algebraically, then derive the postcondition from the invariant and false guard. Prove termination with the nonnegative decreasing integer n - i. Compare this model with fixed-width arithmetic and explain the extra preconditions or checks needed to avoid overflow.

Review criteria

  • State the execution model and the domain of every input.
  • Justify each implication, update order and boundary case rather than only checking examples.
  • Distinguish correctness on termination from an argument that termination occurs.