EXAMPLE-INDUCTION-SCHEME-NAT-RECURSION

induction on natural numbers
Major Section:  INTRODUCTION-TO-THE-THEOREM-PROVER

See logic-knowledge-taken-for-granted-inductive-proof for an explanation of what we mean by the induction suggested by a recursive function or a term.

Classical Induction on Natural Numbers: Induction is familiar in the arithmetic setting. To prove (p n), for all n, by classical induction on the construction of the natural numbers, prove each of the following:

Base Case:
(implies (zp n) (p n))
Induction Step:
(implies (and (not (zp n))
              (p (- n 1)))
         (p n))
The Base Case establishes that p holds for 0. In fact, because of the definition of zp , it establishes that (p n) holds when n is 0 and it holds when n is not a natural number.

The Induction Step establishes that if n is a natural number other than 0, and if p holds for n-1, then p holds for n. The hypothesis (p (- n 1)) above is called the induction hypothesis.

A function that suggests this induction is

   
(defun nat-recursion (n)
  (if (zp n)
      n
      (nat-recursion (- n 1))))
Similarly, the term (fact n) suggests this induction if fact is defined:
 (defun fact (k)
  (if (zp k)
      1
      (* k (fact (- k 1))))).
even though the formal parameter of this definition of fact is k, not n.