A typical recursive definition of a set S is of the following form:
Basis 
are all members of S.
Constructors:
If 
are all members of S then
, 
, 
,
.
Extremal Clause Nothing else is in S but what follows from the basis and
constructors.
Suppose that want to prove
that a predicate P(x) holds for all 
. The standard form of the
induction proof of this is as follows:
That is, one first shows that P is true for the basis elements, and then shows that each constructor preserves the truth of P.
To illustrate a recursive proof, consider the set S defined as follows:
Basis: 
, 
Constructors:
If and 
then 
.
If and then 
.
Extremal Clause Nothing else is in S but what follows from the basis and
constructors.
Suppose we want to show all of the elements of S are divisible by 2.
Note that what we've actually proved taking the inductive hypothesis
and the inductive step together is that
