A loop invariant makes correctness easier to check

A loop invariant is a statement that should hold before and after every iteration. Check three things: it holds before the first iteration, each step preserves it, and when the loop ends it implies the desired result.