Induction and Contradiction: Proving Algorithm Correctness

Why Prove Correctness?

Testing shows an algorithm works on specific inputs; proof shows it works on all valid inputs. Two fundamental proof techniques in VCE Algorithmics are mathematical induction and proof by contradiction.

1. Proof by Mathematical Induction

Induction proves a statement $P(n)$ is true for all $n \geq$ some base case.

Structure

1. Base case: Prove $P(0)$ (or $P(1)$, or the initial state) is true
2. Inductive hypothesis: Assume $P(k)$ is true for some arbitrary $k$
3. Inductive step: Using the hypothesis, prove $P(k+1)$ is true
4. Conclusion: By induction, $P(n)$ is true for all $n$

Loop Invariants

For iterative algorithms, induction is applied through a loop invariant — a property that is:
- True before the loop (base case)
- Maintained by each iteration (inductive step)
- Implies correctness when the loop terminates

Example: Proving FindMax Correct

ALGORITHM FindMax(A)
    max ← A[0]
    for i ← 1 to length(A) - 1 do
        if A[i] > max then max ← A[i] end if
    end for
    return max

Loop invariant: After iteration $i$, max = the largest element in $A[0..i]$.

• Base case ($i=0$): Before the loop, max = A[0] = largest in $A[0..0]$. ✓
• Inductive step: Assume after iteration $k$, max = largest in $A[0..k]$. In iteration $k+1$: if $A[k+1] >$ max, update max ← A[k+1]; otherwise max unchanged. Either way, max = largest in $A[0..k+1]$. ✓
• Termination: Loop ends after iteration $n-1$. max = largest in $A[0..n-1]$ = largest element. ✓

Induction for Recursive Algorithms

For recursive algorithms, use strong induction:
1. Prove the base case(s) are correct
2. Assume recursive calls on smaller inputs are correct (inductive hypothesis)
3. Prove the overall algorithm is correct using the hypothesis

Example sketch for recursive Fibonacci:
- Base: $F(0) = 0$, $F(1) = 1$ — correct by definition ✓
- Inductive step: Assume $F(k-1)$ and $F(k-2)$ are correct. Then $F(k) = F(k-1) + F(k-2)$ — correct by induction ✓

2. Proof by Contradiction

To prove a statement $P$ by contradiction:
1. Assume $P$ is false (i.e., assume NOT $P$)
2. Derive a logical contradiction (something both true and false, or a violation of known facts)
3. Conclude that $P$ must be true

Example: Proving Prim’s Algorithm Correct

Claim: Prim’s algorithm produces a minimum spanning tree.

Proof sketch by contradiction:
- Suppose Prim’s produces a spanning tree $T$ that is NOT the MST.
- Let $T^$ be an MST. Since $T \neq T^$, there exists a first edge $e$ added by Prim’s that is NOT in $T^$.
- When $e$ was added, it was the minimum-weight edge crossing the cut {visited, unvisited}.
- Adding $e$ to $T^$ creates a cycle. There must be another edge $e’$ in this cycle that also crosses the cut.
- Since Prim’s chose $e$ (not $e’$), $w(e) \leq w(e’)$.
- Swapping $e’$ for $e$ in $T^$ gives a spanning tree with weight $\leq$ weight of $T^$.
- Contradiction with $T^$ being the MST (unless $T = T^$). ✓

Comparison

EXAM TIP: VCAA exams may ask you to “demonstrate the correctness” of a simple algorithm. For iterative algorithms, identify and prove a loop invariant. For recursive algorithms, use induction on the input size. State your base case and inductive step clearly.

VCAA FOCUS: You are not expected to produce full mathematical proofs — structured arguments explaining the loop invariant or contradiction are sufficient. Use precise language.