next up previous contents
Next: Selection and Binomial Coefficients Up: Induction and Counting Previous: Strong Principle of Mathematical   Contents

Recursive Definitions

(Or in other words) Defining $ f(n)$, a formula or functions, for all $ n \in \mathbb{N}_0$ with $ n \ge k_0$ by defining $ f(k_0)$ and then defining for $ k > k_0$, $ f(k)$ in terms of $ f(k_0)$, $ f(k_0 + 1)$, $ \dots$, $ f(k-1)$. The obvious example is factorials, which can be defined by $ n! = n (n-1)!$ for $ n \ge 1$ and $ 0! = 1$.

Proposition 8.4.1   The number of ways to order a set of $ n$ points is $ n!$ for all $ n \in \mathbb{N}_0$.

Proof. This is true for $ n=0$. So, to order an $ n$-set, choose the $ 1^{\text{st}}$ element in $ n$ ways and then order the remaining $ n-1$-set in $ (n-1)!$ ways. $ \qedsymbol$

Another example is the Ackermann function, which appears on example sheet 2.

root 2002-06-10