Proving Recursive Algorithm Correctness by Induction

Hello. In the last lesson, you used loop invariants to justify iterative code: initialize a precise claim, preserve it at each iteration, and combine it with the stopping condition. Recursive correctness has the same logic, but the “next iteration” is replaced by a call on a strictly smaller instance.

For competitive programming, the key shift is this: do not merely say “the recursive calls solve smaller cases.” State exactly what they solve, why their inputs remain valid, and why their answers combine into the answer for the current case. By the end of this lesson, you should be able to write a compact induction proof for a recursive algorithm or a recurrence-based solution, including termination.

---

The theorem hidden inside recursive code

A recursive function is usually meant to satisfy a contract:

• Precondition: what inputs are valid?
• Postcondition: what does the function return or modify?
• Termination claim: why will every valid call finish?

For example, a sorting function on a half-open array segment might have this contract:

For every valid segment a[l..r), mergeSort(a, l, r) terminates and rearranges exactly the elements initially in that segment into nondecreasing order.

Notice the details:

• “sorted” alone is not enough; an algorithm could overwrite every value with zero.
• “same elements” alone is not enough; it could preserve all values in arbitrary order.
• termination belongs in the claim if you want total correctness, rather than merely “the output would be correct if it returned.”

Induction proves such a claim across all instance sizes.

Let $P(n)$ mean:

$$P(n):\text{Every valid instance of size }n\text{ terminates and satisfies the postcondition.}$$

The word every matters. The recursive call generally receives a different input from the original one, not merely “the same problem but smaller.” Your induction hypothesis must cover all valid smaller inputs that the algorithm might generate.

For a recursive algorithm, a reliable proof has five parts:

1. Choose a decreasing measure.
   Usually this is segment length, remaining elements, tree size, or number of unset decisions.

2. State the full claim.
   Include the function’s exact output guarantee and, normally, termination.

3. Prove base cases.
   These are branches with no recursive calls.

4. Use the induction hypothesis in each recursive branch.
   Before invoking it, establish:

   • the recursive input satisfies the precondition;
   • its measure is strictly smaller.

5. Show how correct subanswers produce a correct current answer.
   This is the actual algorithm-specific reasoning. It should not be replaced by “therefore it works.”

For divide-and-conquer, strong induction is usually the natural form:

Assume $P(k)$ holds for every $k$ with $0\le k<n$. Prove $P(n)$.

Ordinary induction assumes only $P(n-1)$, which is often awkward when an algorithm recursively calls sizes such as $\lfloor n/2\rfloor$, $n-2$, or several unequal subproblems. Strong induction does not make a proof less rigorous; it simply matches the recursive structure.

---

Worked proof: Merge Sort

Merge Sort is a particularly important example because its recursive structure is clean, but its correctness statement has two components:

1. the output is sorted;
2. the output is a permutation of the original segment.

Here is a standard half-open-interval version:

void mergeSort(vector<int>& a, int l, int r) {
    if (r - l <= 1) return;

    int m = l + (r - l) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m, r);
    merge(a, l, m, r);  // merges sorted a[l..m) and a[m..r)
}

The red upper portion of the Merge Sort recursion tree represents the recursive decomposition. The green lower portion represents the reconstruction. The proof must justify both halves: recursive calls correctly sort their segments, and merge correctly combines those sorted segments.

State the claim precisely

For every integer $n\ge 0$, define $P(n)$ as follows:

$$P(n):\begin{array}{rl}& \text{For every valid array segment }a[l\dots r)\text{ with }r-l=n,\\ & \text{mergeSort(a, l, r)}\text{ terminates and leaves }a[l\dots r)\\ & \text{sorted in nondecreasing order with exactly its original multiset of values.}\end{array}$$

Using half-open intervals makes the size measure explicit:

$$n=r-l.$$

Base case

Suppose $n\le 1$. The function returns immediately.

A segment of length zero or one is already sorted, and returning without modifying it clearly preserves its multiset. The call terminates.

Therefore, $P(0)$ and $P(1)$ hold.

Inductive step

Now let $n>1$, and assume $P(k)$ is true for all $k$ such that

$$0\le k<n.$$

Consider any valid call mergeSort(a, l, r) with $r-l=n$. The code chooses

$$m=l+\lfloor \frac{r-l}{2}\rfloor .$$

The two recursive segments are a[l..m) and a[m..r). Their lengths are both strictly less than $n$:

$$m-l<n$$

and

$$r-m<n.$$

They are also valid subsegments of the original array. Thus the induction hypothesis applies to both calls:

• after mergeSort(a, l, m), the left segment is sorted and contains exactly its original values;
• after mergeSort(a, m, r), the right segment is sorted and contains exactly its original values.

At this point, merge(a, l, m, r) receives two adjacent sorted segments.

The required merge lemma is:

Given two sorted adjacent segments, merge terminates and replaces them with one sorted segment containing exactly the union of their values.

You already have the machinery to prove this lemma from the prior lesson: a merge-loop invariant can state that the output prefix contains the smallest available elements, in sorted order, while the remaining suffixes of both input halves are still unprocessed. When one half is exhausted, copying the other is safe because it is already sorted and all its remaining values are at least as large as the output prefix.

Applying the merge lemma gives:

• a[l..r) is sorted;
• its values are exactly the values originally present in the two halves;
• since the halves partition the original segment, this is exactly the multiset originally in a[l..r).

Thus the postcondition holds for size $n$.

For termination, both recursive calls terminate by the induction hypothesis. The merge loop advances a bounded number of positions, at most $n$, so it terminates as well. Therefore mergeSort terminates.

By strong induction, Merge Sort is correct for every valid segment length.

What the proof did not prove

This proof establishes correctness, not running time.

To prove Merge Sort runs in $O(n\log n)$, you would separately analyze a time recurrence such as

$$T(n)=2T(\lceil n/2\rceil )+O(n).$$

Do not blur these claims under contest pressure:

• a correctness proof explains why the result satisfies the statement;
• a complexity argument explains why the solution fits the constraints.

Both belong in a polished solution sketch, but they answer different questions.

---

A recurrence proof: maximum-weight independent set on a path

Induction also proves that a recurrence captures the correct optimum. This is central to dynamic programming, even when the final implementation is iterative.

Consider a path of $n$ positions with weights $w_1,w_2,\dots ,w_n$. Select positions with no two adjacent, maximizing total selected weight. Allow selecting nothing, which handles negative weights naturally.

Define:

$$D[0]=0$$ $$D[1]=\max (0,w_1)$$

and, for $i\ge 2$,

$$D[i]=\max (D[i-1],D[i-2]+w_i).$$

The recurrence suggests two possibilities at position $i$:

• do not select $i$, leaving an optimal solution among the first $i-1$ positions;
• select $i$, which forbids $i-1$, leaving an optimal solution among the first $i-2$ positions.

That intuition is not yet a proof. In particular, you must establish that these are not merely possible answers, but that every optimal solution falls into one of the cases.

The claim

Let $P(i)$ be:

$$P(i):D[i]\text{ equals the maximum total weight of a nonadjacent subset of }\{1,\dots ,i\}.$$

We prove $P(i)$ for every $i$ from $0$ through $n$.

Base cases

For $i=0$, the only subset is empty, so its maximum weight is $0=D[0]$.

For $i=1$, the best valid choice is either empty, with weight $0$, or select position $1$, with weight $w_1$. Hence the optimum is

$$\max (0,w_1)=D[1].$$

Inductive step

Fix $i\ge 2$, and assume $P(i-1)$ and $P(i-2)$.

Take an optimal valid subset $S$ of positions $1$ through $i$. Exactly one of two cases holds.

Case 1: $i\notin S$.
Then $S$ is a valid nonadjacent subset of the first $i-1$ positions. Therefore its weight is at most $D[i-1]$.

Case 2: $i\in S$.
Because adjacent selections are forbidden, $i-1\notin S$. Removing $i$ leaves a valid subset of the first $i-2$ positions, whose weight is at most $D[i-2]$. Therefore:

$$\mathrm{weight}(S)\le D[i-2]+w_i.$$

Every optimum belongs to one of these cases, so:

$$\mathrm{OPT}(i)\le \max (D[i-1],D[i-2]+w_i).$$

That gives an upper bound. To finish, we need the reverse direction.

By the induction hypothesis, there exists a valid subset of the first $i-1$ positions with weight $D[i-1]$. It remains valid for the first $i$ positions when we do not select $i$.

Likewise, there exists a valid subset of the first $i-2$ positions with weight $D[i-2]$. Adding position $i$ preserves validity, because position $i-1$ is not in that subset. This gives a solution of weight:

$$D[i-2]+w_i.$$

So both recurrence candidates are achievable valid solutions. Consequently:

$$\mathrm{OPT}(i)\ge \max (D[i-1],D[i-2]+w_i).$$

Combining the upper and lower bounds:

$$\mathrm{OPT}(i)=\max (D[i-1],D[i-2]+w_i)=D[i].$$

Thus $P(i)$ holds.

The most reusable pattern here is:

To prove an optimization recurrence, classify every optimal solution into exhaustive cases for an upper bound, then show each recurrence candidate corresponds to a feasible construction for a lower bound.

Without the lower-bound argument, you may only have shown that the recurrence does not underestimate the optimum, or does not overestimate it. You need equality.

---

Turning the recurrence into recursive code

The recurrence can be implemented directly:

long long solve(int i) {
    if (i == 0) return 0;
    if (i == 1) return max(0LL, w[1]);

    return max(solve(i - 1),
               solve(i - 2) + w[i]);
}

The recurrence proof already establishes what value this function returns. The remaining termination argument is short:

• for every call with $i\ge 2$, recursive calls use $i-1$ and $i-2$;
• both are strictly smaller nonnegative indices;
• eventually, execution reaches $i=0$ or $i=1$.

Memoization changes the running time dramatically, but it does not change the correctness proof. A memoized version returns the same value as solve(i); it merely stores a previously established subanswer instead of recomputing it.

---

A compact proof template for contests

When a recursive solution looks promising, write this in your notes before coding:

Claim. For every valid instance of size $n$, F(instance) terminates and returns [exact required result].

Measure. The instance size is [segment length / number of nodes / remaining decisions].

Base case. For [smallest cases], the code returns [why this meets the specification].

Inductive step. Assume the claim for all valid smaller instances. Each recursive call:

• receives a valid input;
• has strictly smaller measure;
• therefore returns its specified correct result.

Using those returned results, [explain why the current branch satisfies the postcondition].

Termination. Every recursive call decreases a nonnegative measure; nonrecursive work terminates.

Several proof failures recur in competitive programming:

Incomplete argument	What is missing
“The recursive call handles the rest.”	Its exact postcondition and why its input is valid.
“The problem gets smaller.”	A defined measure and a strict decrease.
“The halves are sorted, so the whole array is sorted.”	A merge lemma showing order and preservation of elements.
“The recurrence considers two choices.”	Proof that every optimal solution belongs to one of them, plus feasibility of both candidates.
“We proved the answer is right.”	A termination argument, if total correctness is required.

A proof does not need to be long. But every recursive branch needs a justified bridge from correct subanswers to the current answer.

---

Takeaways

Induction is the natural proof method for recursive and recurrence-based algorithms because recursive calls reduce a well-founded measure.

For a rigorous proof:

• state a contract that includes the exact postcondition;
• choose a size measure that decreases in every recursive call;
• use strong induction when calls may have several different smaller sizes;
• verify recursive-call preconditions before invoking the induction hypothesis;
• prove that correct subanswers combine into the required current answer;
• separately account for termination.

For optimization recurrences, prove both directions: every optimum is covered by a recurrence case, and every candidate value comes from a feasible solution.

Next, you will shift from proving an idea on paper to checking an implementation mechanically: building a brute-force oracle for small inputs.