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.
   365   366   367   368   369   370   371   372   373   374   375