1. **Problem Statement:** Explain what a loop invariant is and provide an example with a proof. 2. **Definition:** A loop invariant is a condition that holds true before and after each iteration of a loop. It helps prove the correctness of algorithms. 3. **Example:** Consider the problem of finding the sum of the first $n$ natural numbers using a loop. 4. **Algorithm:** Initialize $sum = 0$ and $i = 1$. While $i \leq n$, do: - $sum = sum + i$ - $i = i + 1$ 5. **Loop Invariant:** At the start of each iteration, $sum = \frac{(i-1) \cdot i}{2}$. 6. **Proof:** - **Initialization:** Before the first iteration, $i=1$, so $sum=0$. The formula gives $\frac{(1-1) \cdot 1}{2} = 0$, which holds. - **Maintenance:** Assume the invariant holds at the start of iteration $k$, i.e., $sum = \frac{(k-1)k}{2}$. During iteration $k$, we add $i=k$ to $sum$, so new $sum = \frac{(k-1)k}{2} + k = \frac{k(k+1)}{2}$. Then increment $i$ to $k+1$. - **Termination:** When $i = n+1$, the loop ends, and $sum = \frac{n(n+1)}{2}$, which is the sum of the first $n$ natural numbers. 7. **Conclusion:** The loop invariant holds at initialization, is maintained through each iteration, and upon termination, it proves the correctness of the algorithm. **Final answer:** The loop invariant $sum = \frac{(i-1) \cdot i}{2}$ proves the correctness of the sum calculation loop.