Loop invariants are used to prove the correctness of an [[algorithm]] involving a loop. The loop invariant proof is a form of [[proof by induction]]. You must show three things: - **Initialization**: the loop invariant is true prior to the first iteration of the loop. - **Maintenance**: if the loop invariant is true before an iteration of the loop, it remains true before the next iteration. - **Termination**: the loop terminates, and when it does, the invariant is the correct output.