induction on recursive calls

A recursive procedure handles a big input by calling itself on smaller inputs and combining the results. How do you trust the answer when the function calls itself, possibly many times? You use the same trust you would extend to a colleague: assume each recursive call returns the correct answer for its (smaller) input, then check that you assemble those correct answers into a correct answer for the whole. This is induction on the recursive calls — induction over the size of the input, with the recursive calls playing the role of the induction hypothesis.

The recipe has two parts that mirror induction exactly. Base case: the non-recursive cases (the inputs small enough to answer directly, e.g. an empty or single-element list) return the right answer outright. Inductive step: assume every recursive call, made on a strictly smaller input, returns the correct result (this is the hypothesis), and prove the combine step turns those into the correct result for the current input. For merge sort: base case, a list of length <= 1 is already sorted; step, the two recursive calls sort the left and right halves (by hypothesis), and merge correctly interleaves two sorted halves into one sorted whole — so the result is sorted. Because each call is on a strictly smaller input, the chain of assumptions bottoms out at the base case; it is really strong induction on size.

Two things make this rigorous and safe. First, the recursion must strictly shrink the input on every call, so it cannot recurse forever — that decreasing measure is also what proves termination. Second, you must check the combine step on its own, treating the recursive results as black boxes that are simply correct. A subtle but common error is assuming correctness for inputs that are not actually smaller (e.g. recursing on the same size), which makes the induction circular and the procedure possibly nonterminating.