Skip to main content
Logo image

Applied Combinatorics

Section 3.7 Inductive Definitions

Although it is primarily a matter of taste, recursive definitions can also be recast in an inductive setting. As a first example, set \(1!=1\) and whenever \(k!\) has been defined, set \((k+1)!=(k+1)k!\text{.}\)
As a second example, set
\begin{equation*} \sum_{i=1}^1 f(i) = f(1)\quad\text{and} \quad \sum_{i=1}^{k+1} f(i)= \sum_{i=1}^{k} f(i)+ f(k+1) \end{equation*}
In this second example, we are already using an abbreviated form, as we have omitted some English phrases. But the meaning should be clear.
Now let’s back up and give an example which would really be part of the development of number systems. Suppose you knew everything there was to know about the addition of positive integers but had never heard anything about multiplication. Here’s how this operation can be defined.
Let \(m\) be a positive integer. Then set
\begin{equation*} m\cdot1 = m\quad\text{and} \quad m\cdot(k+1)=m\cdot k+ m \end{equation*}
You should see that this defines multiplication but doesn’t do anything in terms of establishing such familiar properties as the commutative and associative properties. Check out some of the details in Appendix B.