(Or in other words) Defining , a formula or functions, for all
with by defining and then defining
for , in terms of ,
, , .
The obvious example is factorials, which can be defined by
for and .

Proposition 8.4.1
The number of ways to order a set of points is for all
.

Proof.
This is true for . So, to order an -set, choose the
element in ways and then order the remaining -set in ways.

Another example is the Ackermann function, which appears on example sheet 2.
root
2002-06-10