Introduction

When you write pseudocode for recursive or iterative algorithms, you also need a proof that the algorithm is correct for all valid input sizes. Mathematical induction is the standard method for that job. A good induction proof is not just formal math; it also exposes hidden assumptions in the algorithm design.

What an Induction Proof Must Show

For pseudocode, correctness usually means two claims:

• partial correctness: if the algorithm returns, the result is correct.
• termination: the algorithm eventually stops.

Induction is often used for partial correctness. You choose a parameter such as input size n, then prove:

1. Base case: the claim is true for the smallest valid n.
2. Inductive step: assuming the claim is true for size k, show it is true for size k + 1.

If both parts hold, the claim is true for all n in the domain.

Example: Prefix Sum Algorithm

Consider this pseudocode that returns the sum of the first n elements in an array.

1function PrefixSum(A, n):
2    if n == 1:
3        return A[1]
4    return PrefixSum(A, n - 1) + A[n]

Specification

Input is an array A indexed from 1 to n, with n >= 1. Output is A[1] + A[2] + ... + A[n].

Base Case

When n = 1, the function returns A[1]. That matches the specification directly.

Inductive Hypothesis

Assume for some k >= 1 that PrefixSum(A, k) returns A[1] + ... + A[k].

Inductive Step

For input size k + 1, the algorithm computes:

• PrefixSum(A, k) by recursive call.
• then adds A[k + 1].

By the inductive hypothesis, the recursive call equals A[1] + ... + A[k]. After adding A[k + 1], the result becomes A[1] + ... + A[k + 1], which is exactly the required output.

So partial correctness holds for all n >= 1.

Termination Argument

Correctness alone is not enough. We must show the recursion stops.

Define a measure m = n. Each recursive call reduces m by one because it calls PrefixSum(A, n - 1). The measure is a positive integer and cannot decrease forever. Eventually n reaches 1, which triggers the base case and returns. Therefore termination is proven.

Example with Loop Invariant and Induction

Many iterative algorithms are proved with loop invariants. The proof style is still induction, just indexed by iteration count.

1def prefix_sum_iter(a):
2    total = 0
3    for i in range(len(a)):
4        total += a[i]
5    return total

Invariant at loop index i: before processing element i, total equals the sum of elements from index 0 to i - 1.

• Initialization: before first iteration, i = 0 and total = 0, which matches an empty prefix.
• Maintenance: if invariant holds at start of iteration i, adding a[i] makes total equal sum from 0 to i.
• Termination: after the loop ends, i = len(a), so total is the full sum.

This is induction over loop iterations, not over recursive depth, but the logic is identical.

Writing Better Proofs for Pseudocode

The biggest quality gap in student and production documentation is vague statements. Use this checklist:

• State exact preconditions such as index bounds and non-empty input.
• State exact postcondition in mathematical form or precise plain language.
• Identify the induction variable explicitly.
• Separate partial correctness from termination.
• Mention edge cases such as empty arrays, single element arrays, or invalid parameters.

If the pseudocode has helper functions, specify which assumptions are delegated to each helper. That avoids circular proofs where one unproven helper silently supports another.

Common Pitfalls

• Proving only the base case and claiming the rest is obvious.
• Using an inductive hypothesis that does not match the recursive call.
• Mixing one-based and zero-based indexing in the same proof.
• Showing output correctness but forgetting to prove termination.
• Omitting preconditions and later discovering counterexamples outside the intended domain.

Summary

• Induction proofs for pseudocode require a base case and an inductive step.
• Correctness claims should be tied to explicit input and output specifications.
• Termination must be proved separately, usually with a decreasing measure.
• Loop invariants are induction in iterative form.
• Clear assumptions and indexing conventions prevent invalid proofs.