3.3 Recursive Definitions.

Our definition of function $f\colon A\to B$ involved the undefined word ``rule". If I define $f\colon\mbox{{\bf N}}\to\mbox{{\bf N}}$ by

$$f(n)=2\cdot n+1 \mbox{ for all } n\in\mbox{{\bf N}}$$

the rule is perfectly clear. I will often want to define functions by ``rules" of the following sort: $f\colon\mbox{{\bf N}}\to\mbox{{\bf N}}$ is given by

$$\cases{f(0)=1 & \cr f(n+1)=(n+1)\cdot f(n) &for all $n\in\mbox{{\bf N}}$.\cr}$$ (3.50)

It is not quite so clear that this is a rule, since the right side of (3.50) involves the function I am trying to define. However, if I try to use this rule to calculate $f(4)$, I get

$$f(4) = 4\cdot f(3)$$

$$= 4\cdot 3\cdot f(2)$$

$$= 4\cdot 3\cdot 2\cdot f(1)$$

$$= 4\cdot 3\cdot 2\cdot 1\cdot f(0)$$

$$= 4\cdot 3\cdot 2\cdot 1\cdot 1$$ (3.51)

and by this example, you recognize that (3.50) defines the familiar factorial function. In fact, I make this my definition of the factorial function.

3.52   Definition (Factorial function.) We define $f\colon\mbox{{\bf N}}\to\mbox{{\bf N}}$ by the rules.

$$\begin{eqnarray*} \cases{f(0)=1 & \cr f(n+1)=(n+1)\cdot f(n) &for all $n\in\mbox{{\bf N}}$.\cr} \end{eqnarray*}$$

We call $f$ the factorial function, and denote $f(n)$ by $n!$. By definition,

$$\begin{eqnarray*} \cases{ 0!=1 & \cr (n+1)!=(n+1)\cdot n!. & \cr} \end{eqnarray*}$$

I could use the same rule (3.50) to define a factorial function $\mbox{{\bf Z}}_5\to\mbox{{\bf Z}}_5$. The calculation (3.51) shows that then

$$f(4) = 4\cdot 3\cdot 2\cdot 1\cdot 1=24=4,$$

and

$$f(5) = 5\cdot f(4)=5\cdot 4=0.$$

but in $\mbox{{\bf Z}}_5$, $5=0$ so I have $f(0)=0$, contradicting $f(0)=1$. So I see that (3.50) is not a ``rule". How do I know that (3.50) is a ``rule" when considered as a function from $\mbox{{\bf N}}\to\mbox{{\bf N}}$?; i.e., how do I know that no contradiction arises when I use (3.50) to calculate values for $n\in\mbox{{\bf N}}$? I have decided not to worry about this question, and to treat definitions analogous to (3.50) where functions on $\mbox{{\bf N}}$ are defined by giving $f(0)$ explicitly, and expressing $f(n+1)$ in terms of $n$ and $f(k)$ for values of $k \leq n$, as valid ``rules". Such defintions are called definitions by recursion. A discussion of, and justification for definitions by recursion can be found in [27].

3.53   Definition (Powers.) Let $F$ be a field, and let $a\in F$. Define a function

$$f_a\colon\mbox{{\bf N}}\to F$$

by

$$f_a(0) = 1.$$

$$f_a(n+1) = f_a(n)\cdot a\mbox{ for all }n\in\mbox{{\bf N}}.$$ (3.54)

Thus,

$$\begin{eqnarray*} f_a(4)&=&f_a(3)\cdot a \\ &=&f_a(2)\cdot a\cdot a \\ &=& f_a... ...&=&1\cdot a\cdot a\cdot a\cdot a \\ &=& a\cdot a\cdot a\cdot a. \end{eqnarray*}$$

We denote the value of $f_a(n)$ by $a^n$. Then we can rewrite (3.54) as

$$\begin{eqnarray*} \cases{a^0=1 & \cr a^{n+1}=a^n\cdot a &for all $n\in\mbox{{\bf N}}$.\cr} \end{eqnarray*}$$

Note that $0^0=1$ and $a^1=a$.

3.55   Theorem. Let $F$ be a field and let $a\in F$. Then for all $p,n\in\mbox{{\bf N}}$,

$$a^{p+n}=a^p\cdot a^n.$$

Proof: Define a proposition form $P$ on $\mbox{{\bf N}}$ by

$$P(n)=``\mbox{for all }p\in\mbox{{\bf N}}( a^{p+n}=a^p\cdot a^n)'' \mbox{ for all }n\in\mbox{{\bf N}}.$$

Then $P(0) \mbox{``}\mbox{for all }p\in\mbox{{\bf N}}( a^{p+0}=a^p\cdot a^0)''$ which is true, since both sides of the equation are equal to $a^p$. For all $n\in\mbox{{\bf N}}$,

$$a^{p+n} \cdot a = a^{(p+n)+1}=a^{p+(n+1)},$$

and

$$(a^p a^n)\cdot a = a^p( a^n a) = a^pa^{(n+1)}.$$

Hence for all $n\in\mbox{{\bf N}}$,

$$\begin{eqnarray*} P(n)&\mbox{$\Longrightarrow$}& \mbox{for all }p\in\mbox{{\bf N... ... a^{p+(n+1)} =a^p a^{n+1})\\ &\mbox{$\Longrightarrow$}& P(n+1). \end{eqnarray*}$$

By induction, $P(n)$ is true for all $n\in\mbox{{\bf N}}$, i.e.

$$\mbox{ for all }n\in\mbox{{\bf N}}\Big( \mbox{for all }p\in\mbox{{\bf N}}(a^{p+n} = a^pa^n)\Big).\mbox{ $\mid\!\mid\!\mid$}$$

3.56   Exercise. Let $F$ be a field, and let $a,b$ be elements of $F$. Show that

$$(ab)^n=a^nb^n \mbox{ for all } n\in\mbox{{\bf N}}.$$

3.57   Exercise. A Let $F$ be a field and let $a\in F$. Show that

$$(a^n)^m=a^{(nm)} \mbox{ for all } m,n\in\mbox{{\bf N}}.$$

The following results are easy to show and we will assume them.

$$\begin{eqnarray*} &&0^{n+1}=0\mbox{ for all } n\in\mbox{{\bf N}}, (\mbox{ but } ... ...row\hspace{1ex}$}(a^n\neq 0\mbox{ for all } n\in\mbox{{\bf N}}). \end{eqnarray*}$$

3.58   Remark. Let $F$ be a field, let $a\in F\backslash\{0\}$ and let $n\in\mbox{{\bf Z}}$. We know that $n=p-q$ where $p,q\in\mbox{{\bf N}}$. Suppose we also have $n=P-Q$ where $P,Q\in\mbox{{\bf N}}$.

$$\begin{eqnarray*} n=n&\mbox{$\Longrightarrow$}&p-q=P-Q\mbox{$\hspace{1ex}\Longri... ...&\mbox{$\Longrightarrow$}&{{a^p}\over {a^q}}={{a^P}\over {a^Q}}. \end{eqnarray*}$$

I need this remark for the following definition to make sense.

3.59   Definition (Integer powers.) Let $F$ be a field. If $a\in F\backslash\{0\}$ and $n\in\mbox{{\bf Z}}$, we define

$$a^n={{a^p}\over {a^q}} \mbox{ where } n=p-q,\;\; p,q\in\mbox{{\bf N}}.$$

Note that this definition of $a^{-1}$ is consistent with our use of $a^{-1}$ for multiplicative inverse. Also, this definition implies that

$$1^n=1 \mbox{ for all }n\in\mbox{{\bf Z}}.$$

3.60   Theorem. Let $F$ be a field and let $a\in F\backslash\{0\}$. Then

$$\mbox{ for all } m,n\in\mbox{{\bf Z}}\;\; (a^{m+n}=a^m\cdot a^n).$$

Proof: Let $m,n\in\mbox{{\bf Z}}$, and write

$$m=p-q,\quad n=r-s \mbox{ where } p,q,r,s\in\mbox{{\bf N}}$$

then $p+r\in\mbox{{\bf N}}$ and $q+s\in\mbox{{\bf N}}$ and

$$\begin{eqnarray*} a^{m+n}&=&a^{(p-q)+(r-s)}=a^{(p+r)-(q+s)} \\ &=&{{a^{p+r}}\ov... ...\cdot {{a^r}\over {a^s}}=a^m\cdot a^n.\mbox{ $\mid\!\mid\!\mid$} \end{eqnarray*}$$

3.61   Remark. If $F$ is a field, and $a \in F \setminus \{0\}$, then by definition 3.59 we know that

$$a^{p-q} = {a^p \over a^q} \mbox{ for all }p,q \in \mbox{{\bf N}}.$$

It follows from theorem 3.60 that $a^qa^{p-q} = a^p$ for all $p,q \in \mbox{{\bf Z}}$, and hence

$$a^{p-q} = {a^p \over a^q} \mbox{ for all }p,q \in \mbox{{\bf Z}}.$$

3.62   Exercise. Let $F$ be a field, and let $a,b\in F\backslash\{0\}$. Show that

$$(ab)^n=a^nb^n\mbox{ for all } n\in\mbox{{\bf Z}}.$$

3.63   Corollary (to Exercise 3.62)Let $F$ be a field, and let $a,b \in F \setminus \{0\}$. Then

$$\left( {a \over b}\right)^n = {a^n \over b^n} \mbox{ for all }n \in \mbox{{\bf Z}}.$$

Proof: By exercise 3.62

$$\left( {a\over b}\right)^n b^n = \left( {a\over b}\cdot b\right)^n = a^n \mbox{ for all }n \in\mbox{{\bf Z}}.$$

If we multiply both sides of this equation by $(b^n)^{-1}$, we get

$$\left({a\over b}\right)^n b^n (b^n)^{-1} = a^n(b^n)^{-1},$$

i.e.

$$\left({a\over b}\right)^n = {a^n \over b^n}.$$

3.64   Exercise. Let $F$ be a field, and let $a\in F\backslash\{0\}$. Show that

$$(a^m)^n=a^{(mn)} \mbox{ for all } m,n\in\mbox{{\bf Z}}.$$