07.3 Induction and Recursion
7.3 Induction and Recursion Induction is the standard proof technique for objects built in stages. Recursion is the matching construction technique. Together they describe how to define, compute, and prove statements about natural numbers, lists, trees, syntax, algorithms, and other generated structures. The simplest form is mathematical induction on natural numbers. To prove a statement $P(n)$ for every natural number $n$, prove two things. First, prove the base case: $$...