Page 370 - Discrete Mathematics and Its Applications
P. 370
5.3 Recursive Definitions and Structural Induction 349
a> b is less than or equal to 5(log b + 1). Because 5(log b + 1) is O(log b), we see that
10
10
O(log b) divisions are used by the Euclidean algorithm to find gcd(a, b) whenever a> b.
Recursively Defined Sets and Structures
We have explored how functions can be defined recursively.We now turn our attention to how sets
can be defined recursively. Just as in the recursive definition of functions, recursive definitions
of sets have two parts, a basis step and a recursive step. In the basis step, an initial collection
of elements is specified. In the recursive step, rules for forming new elements in the set from
those already known to be in the set are provided. Recursive definitions may also include an
exclusion rule, which specifies that a recursively defined set contains nothing other than those
elements specified in the basis step or generated by applications of the recursive step. In our
discussions, we will always tacitly assume that the exclusion rule holds and no element belongs
to a recursively defined set unless it is in the initial collection specified in the basis step or can
be generated using the recursive step one or more times. Later we will see how we can use a
technique known as structural induction to prove results about recursively defined sets.
Examples 5, 6, 8, and 9 illustrate the recursive definition of sets. In each example, we show
those elements generated by the first few applications of the recursive step.
EXAMPLE 5 Consider the subset S of the set of integers recursively defined by
BASIS STEP: 3 ∈ S.
RECURSIVE STEP: If x ∈ S and y ∈ S, then x + y ∈ S.
The new elements found to be in S are 3 by the basis step, 3 + 3 = 6 at the first application of
the recursive step, 3 + 6 = 6 + 3 = 9 and 6 + 6 = 12 at the second application of the recursive
step, and so on. We will show in Example 10 that S is the set of all positive multiples of 3. ▲
Recursive definitions play an important role in the study of strings. (See Chapter 13 for
an introduction to the theory of formal languages, for example.) Recall from Section 2.4 that a
∗
string over an alphabet is a finite sequence of symbols from . We can define , the set of
strings over , recursively, as Definition 1 shows.
∗
DEFINITION 1 The set of strings over the alphabet is defined recursively by
BASIS STEP: λ ∈ (where λ is the empty string containing no symbols).
∗
∗
∗
RECURSIVE STEP: If w ∈ and x ∈ , then wx ∈ .
GABRIEL LAMÉ (1795–1870) Gabriel Lamé entered the École Polytechnique in 1813, graduating in 1817.
He continued his education at the École des Mines, graduating in 1820.
In 1820 Lamé went to Russia, where he was appointed director of the Schools of Highways and Trans-
portation in St. Petersburg. Not only did he teach, but he also planned roads and bridges while in Russia. He
returned to Paris in 1832, where he helped found an engineering firm. However, he soon left the firm, accepting
the chair of physics at the École Polytechnique, which he held until 1844. While holding this position, he was
active outside academia as an engineering consultant, serving as chief engineer of mines and participating in
the building of railways.
Lamé contributed original work to number theory, applied mathematics, and thermodynamics. His best-
known work involves the introduction of curvilinear coordinates. His work on number theory includes proving Fermat’s last theorem
for n = 7, as well as providing the upper bound for the number of divisions used by the Euclidean algorithm given in this text.
In the opinion of Gauss, one of the most important mathematicians of all time, Lamé was the foremost French mathematician of
his time. However, French mathematicians considered him too practical, whereas French scientists considered him too theoretical.