next up previous index
Next: 3.4 Summation. Up: 3. Induction and Integers Previous: 3.2 Integers and Rationals.   Index

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

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

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
\begin{displaymath}
\cases{f(0)=1 & \cr
f(n+1)=(n+1)\cdot f(n) &for all $n\in\mbox{{\bf N}}$.\cr}
\end{displaymath} (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
$\displaystyle f(4)$ $\textstyle =$ $\displaystyle 4\cdot f(3)$  
  $\textstyle =$ $\displaystyle 4\cdot 3\cdot f(2)$  
  $\textstyle =$ $\displaystyle 4\cdot 3\cdot 2\cdot f(1)$  
  $\textstyle =$ $\displaystyle 4\cdot 3\cdot 2\cdot 1\cdot f(0)$  
  $\textstyle =$ $\displaystyle 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

\begin{displaymath}
f(4) = 4\cdot 3\cdot 2\cdot 1\cdot 1=24=4,\end{displaymath}

and

\begin{displaymath}f(5) = 5\cdot f(4)=5\cdot 4=0.\end{displaymath}

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

\begin{displaymath}f_a\colon\mbox{{\bf N}}\to F\end{displaymath}

by
$\displaystyle f_a(0)$ $\textstyle =$ $\displaystyle 1.$  
$\displaystyle f_a(n+1)$ $\textstyle =$ $\displaystyle 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}}$,

\begin{displaymath}a^{p+n}=a^p\cdot a^n.\end{displaymath}

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

\begin{displaymath}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}}.\end{displaymath}

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}}$,

\begin{displaymath}a^{p+n} \cdot a = a^{(p+n)+1}=a^{p+(n+1)},\end{displaymath}

and

\begin{displaymath}(a^p a^n)\cdot a = a^p( a^n a) = a^pa^{(n+1)}.\end{displaymath}

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.

\begin{displaymath}\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$}\end{displaymath}

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

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

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

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


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

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

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

\begin{displaymath}1^n=1 \mbox{ for all }n\in\mbox{{\bf Z}}.\end{displaymath}

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

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

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

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

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

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

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

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

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

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

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

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

Proof: By exercise 3.62

\begin{displaymath}\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}}.\end{displaymath}

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

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

i.e.

\begin{displaymath}\left({a\over b}\right)^n = {a^n \over b^n}.\end{displaymath}

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

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


next up previous index
Next: 3.4 Summation. Up: 3. Induction and Integers Previous: 3.2 Integers and Rationals.   Index