Skip to main content

Section 8.4 Excursion: Recursively-defined Structures

Many discrete objects, such as sets and graphs, can also be defined recursively. In this section, we look at a variety of examples of recursively-defined structures. While the recursively-defined sequences in Section 8.1 used only one previous term, recursions can involve any number of previous terms. In this section, we take a sneak peek at such higher order recursions, which we return to explore in more depth in Section 8.5.

Subsection 8.4.A Proper Bit Strings

We begin with a puzzle. For the sake of this puzzle, we classify each bit string as either proper or improper according to the following definition.

Definition 8.4.1 Proper bit strings.

 
  1. A bit string is proper if it can be constructed from the initial condition B by applying the recursions R1 and/or R2 a finite number of times each in any order where
    • B: The empty bit string \(\lambda\) is proper.
    • R1: If the bit string \(b\) is proper, then the bit string \(b\bs{0}\) is also proper.
    • R2: If the bit string \(b\) is proper, then the bit string \(\bs{1}b\bs{1}\) is also proper.
    For example, \(\bs{1100110}\) is proper, as we show in Example 8.4.2 (a).
  2. All other bit strings are improper. For example, \(\bs{011}\) is improper, as we show in Example 8.4.2 (b).
Let’s verify our examples from Definition 8.4.1.

Example 8.4.2 Proper bit strings.

 
  1. Prove that the bit string \(\bs{1100110}\) is proper.
    Solution.
    To see why, we start with the initial condition B that tells us \(\lambda\) is proper. We can use R1 to show that \(\lambda\bs{0} = \bs{0}\) is proper, and then apply R1 again to show that \(\bs{00}\) is proper. Next, we apply R2 to show that \(\bs{1001}\) is proper, and then apply R2 again to show that \(\bs{110011}\) is proper. Finally, we apply R1 again to show that \(\bs{1100110}\) is proper.
    We can summarize this series of steps in the diagram:
    \begin{equation*} \xrightarrow{\textbf{B}} \lambda \xrightarrow{\textbf{R1}} \bs{0} \xrightarrow{\textbf{R1}} \bs{00} \xrightarrow{\textbf{R2}} \bs{1001} \xrightarrow{\textbf{R2}} \bs{110011} \xrightarrow{\textbf{R1}} \bs{1100110} \end{equation*}
  2. Prove that the bit string \(\bs{011}\) is improper.
    Solution.
    We start with B which tells us \(\lambda\) is proper. If we first apply R1, we get that \(\bs{0}\) is proper. To get two more \(\bs{1}\) s we can apply R2 but that tells us \(\bs{101}\) is proper, which is not our bit string. On the other hand, if we first apply R2, we get that \(\bs{11}\) is proper. To get one \(\bs{0}\text{,}\) we can apply R1 but that tells us \(\bs{110}\) is proper, which is also not our bit string.
    Alternatively, we can construct a possibility tree listing all bit strings of length up to three that are proper as shown in Figure 8.4.3.
    Figure 8.4.3. All proper bit strings of length three or less
Now, it is your turn to work with proper bit strings.

Activity 8.4.A Proper Bit Strings Puzzle.

Recall that a bit string is proper if it can be constructed from these rules in a finite number of steps (and improper otherwise):
  • B: The empty bit string \(\lambda\) is proper.
  • R1: If the bit string \(b\) is proper, then the bit string \(b\bs{0}\) is also proper.
  • R2: If the bit string \(b\) is proper, then the bit string \(\bs{1}b\bs{1}\) is also proper.
  1. Explain why the bit string \(\bs{1010}\) is proper. That means, show how to use the rules to construct this bit string.
  2. Explain why the bit string \(\bs{111010}\) is proper. Again, show how to use the rules to construct this bit string.
  3. Draw a possibility tree showing all proper bit strings of length up to four. Underline the bit strings of length four in your tree.
  4. How many proper bit strings of length four are there?
  5. Use your tree to explain why the bit string \(\bs{1101}\) is improper.
  6. How many improper bit strings of length four are there? Hint: How many bit strings of length four are there (total)?
  7. Extend to your tree from (c) to show all proper bit strings of length up to five. Draw a box around each bit string of length five in your tree.
  8. How many proper bit strings of length five are there? How many improper?
Make sure that you have completed Activity 8.4.A because we are about to reveal some of the answers.

Example 8.4.5 Proper bit strings of length up to five.

 
  1. Draw a possibility tree to list all proper bit strings of length up to five.
    Solution.
    We begin with the tree in Figure 8.4.3. Since we only want bit strings of length at most five, we can apply R1 and R2 to any bit string in that tree, but once we have a bit string of length four we can only apply R1. The tree is shown in Figure 8.4.6.
    Figure 8.4.6. All proper bit strings of length five or less
  2. How many proper bit strings of length five are there? How many improper bit strings of length five are there? Explain.
    Solution.
    We see in Figure 8.4.6 that there are eight proper bit strings of length five. They are
    \begin{equation*} \bs{00000}, \bs{10001}, \bs{10010}, \bs{10100}, \bs{11011}, \bs{11000}, \bs{11101}, \bs{11110}\text{.} \end{equation*}
    Recall from Theorem 2.4.8 that there are \(2^5=32\) bit strings of length five. Therefore, there are \(32-8 = 24\) improper bit strings of length five.
  3. Explain how we can obtain a list of proper bit strings of length five from the list of proper bit strings of length three and four.
    Solution.
    There are two ways to obtain a proper bit string of length five.
    Case 1: Start with a proper bit string of length four and apply R1. The proper bit strings of length four are
    \begin{equation*} \bs{0000}, \bs{1001}, \bs{1010}, \bs{1100}, \bs{1111} \end{equation*}
    so we get
    \begin{equation*} \bs{0000\underline{0}}, \bs{1001\underline{0}}, \bs{1010\underline{0}}, \bs{1100\underline{0}}, \bs{1111\underline{0}} \end{equation*}
    Case 2: Start with a proper bit string of length three and apply R2. The proper bit strings of length three are
    \begin{equation*} \bs{000}, \bs{101}, \bs{110} \end{equation*}
    so we get
    \begin{equation*} \bs{\underline{1}000\underline{1}}, \bs{\underline{1}101\underline{1}}, \bs{\underline{1}110\underline{1}} \end{equation*}
Before we look at other recursively-defined structures, we mention how this example connects to computer science.

Definition 8.4.7 Language.

 
  1. An alphabet is a set of characters. For example, the usual English alphabet \(\{a,b,c, \ldots, z\}\) is an alphabet. The set of bits, \(\{\bs{0}, \bs{1}\}\text{,}\) is also an alphabet.
  2. A (formal) language over the alphabet \(\Sigma\) is a set of strings where each character of each string is an element of \(\Sigma\text{.}\) For example, \(\mathbb{B}\text{,}\) the set of all bit strings, is a language over \(\Sigma = \{\bs{0}, \bs{1}\}\text{.}\) Similarly,
    \begin{equation*} \mathbb{P} = \{ b \in \mathbb{B} \mid b \text{ is proper } \}\text{,} \end{equation*}
    is another language over \(\Sigma = \{\bs{0}, \bs{1}\}\text{.}\)

Subsection 8.4.B Recursively-defined Sets

In Activity 8.4.A, we define what it means for a bit string to be proper using a recursion. This example gives rise to the recursively-defined set of proper bit strings.

Example 8.4.8 Recursively-defined set of proper bit strings.

Give a recursive definition of the set \(\mathbb{P} = \{ b \in \mathbb{B} \mid b \text{ is proper } \}\text{,}\) where proper bit strings are defined in Definition 8.4.1.
Solution.
We can rewrite the initial condition and recursions using set notation to obtain:
  • B: \(\lambda \in \mathbb{P}\text{.}\)
  • R1: If \(b \in \mathbb{P}\text{,}\) then \(b\bs{0}\in \mathbb{P}\text{.}\)
  • R2: If \(b \in \mathbb{P}\text{,}\) then \(\bs{1}b\bs{1}\in \mathbb{P}\text{.}\)
Let’s practice working with proof by mathematical induction to check the unsurprising fact that any bit string consisting of all \(\bs{0}\) s is in \(\mathbb{P}\text{.}\)

Example 8.4.9 Proof by mathematical induction that involves recursively-defined set.

Use mathematical induction Theorem 8.2.2 to prove that any bit string consisting of all \(\bs{0}\) s is in \(\mathbb{P}\text{,}\) the set of all proper bit strings.
Solution.
Proof. We induct on \(n\text{,}\) the length of the bit string.
First, by B we know that \(\lambda \in \mathbb{P}\text{.}\) Next, by R1, it follows that \(\lambda \bs{0} = \bs{0} \in \mathbb{P}\text{.}\) Thus the bit string of length one consisting of all \(\bs{0}\) s is in \(\mathbb{P}\text{.}\)
Next, assume \(b = \underbrace{\bs{000}\cdots\bs{0}}_{n-1 \text{ times } } \in \mathbb{P}\) for some integer \(n > 1\text{.}\) Then by R1, it follows that
\begin{equation*} b\bs{0} = \underbrace{\bs{000}\cdots\bs{0}}_{n-1 \text{ times } }\bs{0} = \underbrace{\bs{000}\cdots\bs{0}}_{n \text{ times } } \in \mathbb{P} \end{equation*}
Here is another example of a recursively-defined set.

Example 8.4.10 Multiplicative set.

Consider the set of integers \(L\) constructed recursively as follows:
The \(L\) consists of all integers that can be formed using B1, B2, B3, and R a finite number of times.
  1. Is \(18 \in L\text{?}\) Is \(20 \in L\text{?}\) Is \(1 \in L\text{?}\) Justify your answers.
    Solution.
    First, by B2 \(2 \in L\) and by B3 \(3 \in L\text{.}\) Then, by R, it follows that \((2)(3) = 6 \in L\) and then it follows from R again that \((3)(6)=18 \in L\text{,}\) so yes.
    Next, there is no combination of 2s and 3s that multiply to give 20 because the prime factorization of \(20=2^25\text{.}\) Therefore there is no way to construct 20, so no.
    Last, \(1 \in L\) by B1.
  2. Give an explicit definition of \(L\text{.}\)
    Solution.
    Notice that \(L\) includes 1 and any integer we can build as a product of 2s and 3s. That is,
    \begin{equation*} L= \{2^a\cdot 3^b \mid a,b \in \mathbb{N}\} \end{equation*}
  3. Give an implicit definition of \(L\text{.}\)
    Solution.
    One implicit definition is
    \begin{equation*} L = \{ n \in \mathbb{N} \mid n = 2^a\cdot 3^b \text{ for some } a,b \in \mathbb{N}\} \end{equation*}
    but a more specific implicit definition is
    \begin{equation*} L = \{ n \in \mathbb{N} \mid \text{ if } p \text{ is prime and } p \mid n \text{ , then } p=2 \text{ or } p=3\} \end{equation*}
Your turn to work with a recursively-defined set.

Activity 8.4.B Additive set.

Consider the set \(M\) constructed recursively as follows:
  1. Show that \(4 \in M\text{.}\)
  2. Show that \(7 \in M\text{.}\)
  3. Show that \(11 \in M\text{.}\)
  4. Explain why every positive even integer is in \(M\text{.}\) Hint: How do we get \(2k\) for \(k \ge 1\text{?}\)
  5. Explain why any positive odd integer that’s greater than or equal to three is in \(M\text{.}\) Hint: Start with three. What do you need to add to get \(2k+1\) total for \(k \ge 1\text{?}\)
Let’s process some of what we learned in Activity 8.4.B.

Example 8.4.12 Additive set.

Consider the set \(M\) constructed recursively in Activity 8.4.B.
  1. Explain why \(M = \{n \in \mathbb{Z} \mid n \ge 2\}\text{.}\)
    Solution.
    We can show any even integer \(n \in M\) as follows. Write \(n = 2k\) for some integer \(k\text{.}\) By B1 we know \(2 \in M\text{.}\) Applying R \((k-1)\) times we get
    \begin{equation*} 2 + \underbrace{2+2+\cdots +2}_{k-1 \text{ times } } \in M\text{.} \end{equation*}
    But
    \begin{equation*} 2 + \underbrace{2+2+\cdots +2}_{k-1 \text{ times } } = 2+ 2(k-1) = 2k =n\text{.} \end{equation*}
    Thus \(n \in M\text{.}\)
    We can show any odd integer \(n \in M\) for \(n \ge 3\) as follows. Write \(n = 2k+1\) for some integer \(k\text{.}\) Since \(n \ge 3\text{,}\) it follows that \(k \ge 1\text{.}\) By B2 we know \(3 \in M\text{.}\) Applying R \((k-1)\) times we get
    \begin{equation*} 3 + \underbrace{2+2+\cdots +2}_{k-1 \text{ times } } \in M\text{.} \end{equation*}
    But
    \begin{equation*} 3 + \underbrace{2+2+\cdots +2}_{k-1 \text{ times } } = 3 + 2(k-1) = 2k + 1=n\text{.} \end{equation*}
    Thus \(n \in M\text{.}\)
  2. Use mathematical induction to verify that \(n \in M\) for any integer \(n \ge 2\text{.}\)
    Solution.
    Proof. Induct on \(n\text{.}\)
    First, when \(n = 2\text{,}\) we know \(2 \in M\) by B.
    Next, assume \(n-1 \in M\) for some \(n >1\text{.}\) We consider two cases.
    Case 1: Somewhere in the process of constructing \(n-1\) we used B1. That is, \(n-1=2+m\) for some \(m \in M\text{.}\) Adding one to each side of the equation we get \(n = 3 + m\text{,}\) and so \(n\) can be constructed from \(m\) using B2 and R.
    Case 2: Nowhere in the process of constructing \(n-1\) did we use B1. It follows that somewhere in the process of constructing \(n-1\) we used B2. That is, \(n-1 = 3+m\) for some \(m \in M\text{.}\) Adding one to each side of the equation we get \(n = 4 + m\text{,}\) and so \(n\) can be constructed from \(m\) using B1 twice and R.
In many textbooks, the example from Activity 8.4.B is described in terms of coins or stamps. In that vocabulary, we can make any value of money 2¢ or greater using 2¢ and 3¢ coins, or any postage 2¢ or greater using 2¢ and 3¢ stamps.

Subsection 8.4.C Recursively-defined Graphs

We begin with an activity.

Activity 8.4.C Lopsided trees.

We define the family of lopsided trees, \(T_n\text{,}\) as follows: \(T_1\) and \(T_2\) are each just a single root vertex. For \(n\ge3\text{,}\) the lopsided tree \(T_n\) is built from the trees \(T_{n-1}\) (drawn on the left) and \(T_{n-2}\) (drawn on the right) by adding a new root vertex, an edge between the new root vertex and the root vertex of \(T_{n-1}\text{,}\) and an edge between the new root vertex and the root vertex of \(T_{n-2}\text{,}\) as represented schematically in Figure 8.4.14.
Figure 8.4.14. Defining the lopsided tree \(T_n\) from Activity 8.4.C.
The first five lopsided trees are drawn in Figure 8.4.15.
Figure 8.4.15. From left to right: the lopsided trees \(T_1\text{,}\) \(T_2\text{,}\) \(T_3\text{,}\) \(T_4\text{,}\) an \(T_5\) from Activity 8.4.C.
  1. Copy \(T_5\) and explain how \(T_3\) and \(T_4\) were used to create \(T_5\text{.}\)
  2. Draw \(T_6\text{.}\) Pay attention to what is on the left versus the right in your drawing.
  3. Recall that leaf is a vertex of degree one. Write \(w_n=\) the number of leaves in the lopsided tree \(T_n\) for \(n \ge 3\text{.}\) Explain why \(w_3=2\) and \(w_4=3\text{.}\)
  4. Calculate \(w_5\) and \(w_6\text{.}\)
  5. Write an recursive definition of the sequence \(w_n\) and explain why the equation holds by referring to the trees (not just the numbers you found). Hint: The definition uses the two previous terms.
Let’s take a closer look at the trees from Activity 8.4.C.

Example 8.4.16 Lopsided trees.

In Activity 8.4.C, we defined the family of lopsided trees \(T_n\text{.}\) Write \(w_n=\) the number of leaves in the lopsided tree \(T_n\) for \(n \ge 3\text{.}\)
  1. Make a table showing the values of \(w_n\) for \(n=1,2,3,4,5,6\text{.}\)
    Solution.
    We can count the leaves in the graphs in Figure 8.4.15 for \(n=1,2,3,4,5\text{.}\) For \(n=6\) note that the leaves in \(T_6\) consists of the leaves from \(T_5\) (on the left) and the leaves from \(T_6\) (on the right). Thus \(w_6 = w_5 + w_4 = 5+3=8\text{.}\) We summarize our findings in Table 8.4.17.
    Table 8.4.17. The number of leaves in the lopsided trees
    \(n\) 1 2 3 4 5 6
    \(w_n\) 1 1 2 3 5 8
  2. Write a recursive definition for \(w_n\) for \(n \ge 1\text{,}\) including the initial conditions.
    Solution.
    Since the leaves in \(T_n\) are the leaves from \(T_{n-1}\) (on the left) and the leaves from \(T_{n-2}\) (on the right), we get
    \begin{equation*} w_n=w_{n-1}+w_{n-2} \end{equation*}
    for \(n \ge 3\text{.}\) The initial conditions are \(w_1=1\) and \(w_2=1\text{.}\) Since the recursion uses two previous terms, we need two initial conditions to start.
The lopsided trees in Activity 8.4.C were defined recursively. Here is another example of a recursively-defined family of graphs.

Example 8.4.18 Recursive definition of the path graphs.

Consider the path graphs \(P_n\text{.}\) We can define these graphs recursively setting \(P_1\) to be a single vertex and then \(P_n\) is formed from \(P_{n-1}\) by adding one new vertex and an edge connecting that new vertex to one of the end vertices of \(P_{n-1}\text{.}\)
  1. Use this definition to draw the first five path graphs.
    Solution.
    The first five path graphs are drawn in Figure 8.4.19.
    Figure 8.4.19. The path graphs
  2. Write a recursive definition for \(v_n=\) the number of vertices of \(P_n\) and \(e_n=\) the number of edges of \(P_n\text{.}\)
    Solution.
    First, \(P_1\) has one vertex and zero edges so \(v_1=1\) and \(e_1=0\text{.}\) Next, at each step we add one new vertex and so the number of new vertices is 1 more than the number of old vertices. That is, \(v_n=v_{n-1}+1\) for \(n \ge 2\text{.}\) Similarly, at each step we add one new edge and so the number of new edges is 1 more than the number of old edges. That is, \(e_n=e_{n-1}+1\) for \(n \ge 2\text{.}\) Notice that \(v\) and \(e\) are defined using the same recursive rule but because they have different initial conditions we get different sequences. In fact, \(v_n=n\) and \(e_n=n-1\) for \(n \ge 1\text{.}\)
  3. Determine the adjacency matrices for \(P_1\text{,}\) \(P_2\text{,}\) \(P_3\text{,}\) \(P_4\text{,}\) and \(P_5\text{.}\) Then describe how the adjacency matrix for \(P_n\) can be constructed from the adjacency matrix for \(P_{n-1}\text{.}\)
    Solution.
    Figure 8.4.20 shows labeled versions of the path graphs \(P_1\text{,}\) \(P_2\text{,}\) \(P_3\text{,}\) \(P_4\text{,}\) and \(P_5\text{.}\)
    Figure 8.4.20. Paths \(P_1\text{,}\) \(P_2\text{,}\) \(P_3\text{,}\) \(P_4\text{,}\) and \(P_5\) labeled.
    The corresponding adjacency matrices are shown in Table 8.4.21. Starting with \(P_{n-1}\) we add a new column on the far right and a new row at the bottom which are all \(\bs{0}\) s except the next to last entry in the column and row is \(\bs{1}\text{.}\)
    Table 8.4.21. The adjacency matrices for the paths \(P_1\text{,}\) \(P_2\text{,}\) \(P_3\text{,}\) \(P_4\text{,}\) and \(P_5\)
    \(\begin{array}{c} v_1 \end{array}\)
    \(\begin{array}{r} v_1 \end{array}\) \(\left[ \begin{array}{cccccc} ~\bs{0}~ \end{array} \right]\)
    \(\begin{array}{cc} v_1\amp v_2 \end{array}\)
    \(\begin{array}{r} v_1 \\ v_2 \end{array}\) \(\left[ \begin{array}{cccccc} ~\bs{0}~ \amp ~\bs{1}~ \\ \bs{1} \amp \bs{0} \end{array} \right]\)
    \(\begin{array}{ccc} v_1\amp v_2\amp v_3 \end{array}\)
    \(\begin{array}{r} v_1 \\ v_2 \\ v_3 \end{array}\) \(\left[ \begin{array}{cccccc} ~\bs{0}~ \amp ~\bs{1}~ \amp ~\bs{0}~ \\ \bs{1} \amp \bs{0} \amp \bs{1} \\ \bs{0} \amp \bs{1} \amp \bs{0} \end{array} \right]\)
    \(\begin{array}{cccc} v_1\amp v_2\amp v_3\amp v_4 \end{array}\)
    \(\begin{array}{r} v_1 \\ v_2 \\ v_3 \\v_4 \end{array}\) \(\left[ \begin{array}{cccccc} ~\bs{0}~ \amp ~\bs{1}~ \amp ~\bs{0}~ \amp ~\bs{0}~\\ \bs{1} \amp \bs{0} \amp \bs{1} \amp \bs{0} \\ \bs{0} \amp \bs{1} \amp \bs{0} \amp \bs{1} \\ \bs{0} \amp \bs{0} \amp \bs{1} \amp \bs{0} \end{array} \right]\)
    \(\begin{array}{ccccc} v_1\amp v_2\amp v_3\amp v_4\amp v_5 \end{array}\)
    \(\begin{array}{r} v_1 \\ v_2 \\ v_3 \\v_4\\v_5 \end{array}\) \(\left[ \begin{array}{cccccc} ~\bs{0}~ \amp ~\bs{1}~ \amp ~\bs{0}~ \amp ~\bs{0}~\amp ~\bs{0}~\\ \bs{1} \amp \bs{0} \amp \bs{1} \amp \bs{0} \amp \bs{0}\\ \bs{0} \amp \bs{1} \amp \bs{0} \amp \bs{1} \amp \bs{0}\\ \bs{0} \amp \bs{0} \amp \bs{1} \amp \bs{0} \amp \bs{1}\\ \bs{0} \amp \bs{0} \amp \bs{0} \amp \bs{1} \amp \bs{0} \end{array} \right]\)

Subsection 8.4.D Exercises

Subsubsection Exercises for 8.4.A Proper Bit Strings

1. Practice.

 
  1. Explain why the bit string \(\bs{101111}\) is improper.
  2. Explain why the bit string \(\bs{1011111}\) is improper. Consider the case where you start with R1 and the case where you start with R2.
Check.
  1. Hint: Look at the number of \(\bs{1}\) s.
  2. Hint: If you start with R1 you can show \(\bs{101}\) is proper, but there is no way to add \(\bs{1}\) s on only the right.

2. Understand.

In Figure 8.4.6, we drew a possibility tree showing all proper bit strings of length up to five.
  1. Use the list of proper bit strings of length four and length five from Example 8.4.5 to generate a list of all proper bit strings of length six.
  2. How many proper bit strings of length six are there?
  3. How does the number of proper bit strings of length six relate to the number of proper bit strings of length four and the number of proper bit strings of length five?
Check.
  1. Hint: Use R1 to turn proper bit strings of length five into proper bit strings of length six. Then use R2 to generate the remaining proper bit strings of length six.
  2. 13
  3. Hint: How does 13 relate to 8 and 5?

3. Understand.

Generalize your observation from Exercise 22.(c) to write a recursive definition of the sequence \(p_n=\) the number of proper bit strings of length \(n\text{,}\) including initial conditions.
Check.
Hint: Your recursion should use \(p_{n-1}\) and \(p_{n-2}\text{.}\) Also, since the recursion involves the two previous terms, you need two initial terms to start: \(p_0\) and \(p_1\text{.}\)

4. Recap.

Do you know …
  1. How to use a recursive definition of a language?
  2. How to draw a possibility tree to list strings from a recursively-defined language?
  3. How to recursively define a sequence using two previous terms and why we need two initial conditions?

5. Explore.

In this problem, we are looking for general conjectures that tell us if a bit string is proper or improper by looking at it– meaning without working through the rules, drawing a tree, considering cases, or anything complicated. Your conjectures should be in the form
“If a bit string is/has , then it is automatically proper/improper.”
Your conjectures should not be examples, they should be general rules that apply to an infinite number of bit strings.
  1. Make a conjecture about a condition that automatically shows a bit string is proper.
  2. Make another conjecture about a condition that automatically shows a bit string is proper.
  3. Make a conjecture about a condition that automatically shows a bit string is improper.
Check.
  1. Hint: One possible answer is any bit string that consists only of \(\bs{0}\) s: \(\bs{0}\text{,}\) \(\bs{00}\text{,}\) \(\bs{000}\text{,}\) etc.
  2. Hint: Find another type of bit string that is always proper. Make sure there are infinitely many bit strings of this type
  3. Hint: Count the number of \(\bs{0}\) s.

6. Explore.

 
  1. Describe in detail a simple process that determines whether a proper bit string was constructed starting with R1 or starting with R2. This process should not involve testing all possible constructions.
  2. Extend your process from Exercise 6 to describe in detail a relatively simple process that determines whether a bit string is proper or improper. This process should not involve testing all possible constructions.

Subsubsection Exercises for 8.4.B Recursively-defined Sets

7. Practice.

Consider the set \(M\) constructed recursively as follows:
  1. Show that \(8 \in M\text{,}\) \(9 \in M\text{,}\) and \(10 \in M\text{.}\)
  2. Which of \(1, 2, 3, 4, 5, 6, 7\) are in \(M\text{?}\) Briefly justify your answers.
Check.
  1. Hint: \(8 = 3+5\) so we can use B1, then B2, then R.
  2. Only 3, 5, and 6.

8. Understand.

Consider the set \(M\) constructed recursively in Exercise 7.
  1. Suppose \(n-1 \in M\) and that somewhere in the construction of \(n-1\) we used B2, meaning that \(n-1=m+5\) for some \(m \in M\text{.}\) Show that \(n \in M\text{.}\)
  2. Suppose \(n-1 \in M\) and that somewhere in the construction of \(n-1\) we used B1 three times, meaning that \(n-1 = m+3+3+3\) for some \(m \in M\text{.}\) Show that \(n \in M\text{.}\)
  3. Suppose \(n-1 \in M\) and that \(n \ge 8\text{.}\) Explain why if we did not use B2 somewhere in the construction of \(n-1\text{,}\) then we must have used B1 at least three times.
Check.
  1. Hint: Solve for \(n\) and use that \(5+1=6=3+3\text{.}\) Explain which parts of the definition you use.
  2. Hint: Now use \(3+3+3+1=10=5+5\text{.}\)
  3. Hint: If we did not use any 5s, then \(n-1\) is built out of 3s. Two threes is only \(3+3=6\text{,}\) but \(n \ge 8\) so \(n-1 \ge 7\text{.}\)

9. Recap.

Do you know …
  1. How to decide if an element is in a recursively-defined set?
  2. How to use mathematical induction to prove results about a recursively-defined set?

10. Explore.

Consider the set \(M\) constructed recursively in Exercise 7. Use mathematical induction to prove \(n \in M\) for all \(n \ge 8\text{.}\) Hint: Copy and edit the proof from Example 8.4.12 (b).
Check.
Another hint: Break the inductive step into two cases based on whether somewhere in the process of constructing \(n-1\) we used B2. In the case where we used B2, use Exercise 8 8.(a). In the case where we did not use B2, cite Exercise 8 8.(c) to show that we must have used B1 at least three times. Then apply Exercise 88.(b)

11. Explore.

Consider the set \(M_{a,b}\) constructed recursively as follows:
  • B1: \(a \in M_{a,b}\)
  • B2: \(b \in M_{a,b}\)
  • R: If \(k,m \in M_{a,b}\text{,}\) then \(k+m \in M_{a,b}\text{.}\)
We saw the set \(M_{2,3}\) in Activity 8.4.B and \(M_{3,5}\) in Exercise 7. It turns out that \(M_{2,3} = \{ n \in \mathbb{Z} \mid n \ge 2\}\) and \(M_{3,5}= \{ n \in \mathbb{Z} \mid n \ge 8\}\text{.}\) That is, \(M_{a,b}\) was the set of all integers starting at \(s\) for some integer \(s\text{.}\)
  1. Is \(M_{2,4}\) the set of all integers starting at \(s\) for some integer \(s\text{?}\) Explain your reasoning.
  2. Is \(M_{6,9}\) the set of all integers starting at \(s\) for some integer \(s\text{?}\) Explain your reasoning.
  3. Is \(M_{4,5}\) the set of all integers starting at \(s\) for some integer \(s\text{?}\) Explain your reasoning.
  4. Make a conjecture about when \(M_{a,b}\) the set of all integers starting at \(s\) for some integer \(s\text{.}\) Your answer will be a relationship between \(a\) and \(b\text{.}\)

Subsubsection Exercises for 8.4.C Recursively-defined Graphs

12. Practice.

We defined lopsided trees in Activity 8.4.C. Write \(v_n=\) the number of vertices in the lopsided tree \(T_n\) for \(n \ge 1\text{.}\)
  1. Explain why \(v_1=1\text{,}\) \(v_2=1\text{,}\) and \(v_3=3\text{.}\)
  2. Calculate \(v_4\text{,}\) \(v_5\text{,}\) and \(v_6\text{.}\)
  3. Write an equation for \(v_n\) in terms of \(v_{n-1}\) and \(v_{n-2}\) for \(n \ge 1\) and explain why the equation holds by referring to the trees (not just the numbers you found).
  4. How are \(v_n\) and \(w_n\) (the number of leaves) related for \(n \ge 3\text{?}\)
Check.
  1. Hint: \(T_3\) has three vertices.
  2. Hint: \(v_6=15\text{.}\)
  3. Hint: Make sure you count the root vertex.
  4. Hint: Make a table showing \(n\text{,}\) \(w_n\text{,}\) and \(v_n\) for \(n=3,4,5,6\text{.}\) The values of \(v_n\) are almost twice \(w_n\text{.}\)

13. Understand.

Consider the family of graphs defined as follows: \(G_1\) is a single (original) vertex and \(G_n\) is formed from \(G_{n-1}\) by adding one new vertex and an edge connecting that vertex to the original vertex. Notice that \(G_1, G_2, G_3\) are the same as \(P_1, P_2,P_3\) but after that term the sequences differ.
  1. Draw \(G_1\text{,}\) \(G_2\text{,}\) \(G_3\text{,}\) \(G_4\text{,}\) and \(G_5\text{.}\) What is the usual name for this family of graphs?
  2. Write the initial condition and a recursive rule for \(v_n\text{,}\) the number of vertices of \(G_n\text{.}\)
  3. Write an explicit rule for \(v_n\text{.}\)
  4. Write the initial condition and a recursive rule for \(e_n\text{,}\) the number of edges of \(G_n\text{.}\)
  5. Write an explicit rule for \(e_n\text{.}\)
Check.
  1. Hint: \(G_5\) has five vertices — one original vertex and four other vertices each connected by an edge to the original vertex.
  2. \(v_1=1\) and \(v_n=v_{n-1}+1\) for \(n\ge 2\)
  3. Hint: \(v_5=5\)
  4. Hint: We add one edge each time.
  5. Hint: \(e_5=5\)

14. Understand.

The graphs \(M_n\) are defined as follows: \(M_1\) is a single (original) vertex and \(M_n\) is formed from \(M_{n-1}\) by adding a copy of the path \(P_2\) each of whose vertices is connected by an edge to the original vertex.
  1. Draw \(M_1\text{,}\) \(M_2\text{,}\) \(M_3\text{,}\) and \(M_4\text{.}\)
  2. Write the initial condition and a recursive rule for \(v_n\text{,}\) the number of vertices of \(M_n\text{.}\)
  3. Write an explicit rule for \(v_n\text{.}\)
  4. Write the initial condition and a recursive rule for \(e_n\text{,}\) the number of edges of \(M_n\text{.}\)
  5. Write an explicit rule for \(e_n\text{.}\)
Check.
  1. Hint: \(M_2=C_3\) and \(M_3\) looks like a bowtie (\(\bowtie\)).
  2. Hint: How many new vertices do we add? Check that your definition gives \(v_4 = 7\text{.}\)
  3. Hint: Make a table showing \(n\) and \(v_n\) for \(n=1,2,3,4\text{.}\) Check that your definition gives \(v_4 = 7\text{.}\)
  4. Hint: How many new edges do we add? Check that your definition gives \(e_4=9\text{.}\)
  5. Hint: make a table showing \(n\) and \(e_n\) for \(n=1,2,3,4\text{.}\) Check that your definition gives \(e_4=9\text{.}\)

15. Understand.

The ladder graphs \(L_{2 \times s}\) for \(s \ge 1\text{,}\) defined in Definition 3.2.22, consist of two paths \(P_s\) with \(s\) additional edges between each pair of corresponding vertices. For example, \(L_{2 \times 5}\) is drawn in Figure 3.2.27.
  1. Write a recursive construction of the ladder graphs like we did for the lopsided graphs in Activity 8.4.C. That means, state where to start (Hint: \(P_2\)) and describe how many new vertices and which edges to add.
  2. Write the initial condition and a recursive rule for the number of vertices \(v_s\) of the ladder graph \(L_{2 \times s}\) and make a conjecture about an explicit rule.
  3. Write the initial condition and a recursive rule for the number of edges \(e_s\) of the ladder graph \(L_{2 \times s}\) and make a conjecture about an explicit rule.
Check.
  1. Hint: Assume the original \(P_2\) is drawn vertically. At each step, add vertices to the right and explain what edges are added.
  2. Hint: The recursive rule is of the form \(v_s = v_{s-1} +\) the number of new vertices. The explicit rule involves \(s\) (and no previous terms.)
  3. Hint: The recursive rule is of the form \(e_s = e_{s-1} +\) the number of new edges. For the explicit rule, count the number of edges in each path and the number of additional edges between each pair of corresponding vertices.

16. Understand.

 
  1. Draw the complete graphs \(K_s\) for \(s = 1, 2,3,4\) as defined in Definition 3.2.12.
  2. Write a recursive construction of the complete graphs \(K_s\) for \(s \ge 1\) That means, state where to start and describe how many vertices and which edges to add.
  3. Write the initial condition and a recursive rule for the number of vertices \(v_s\) of the complete graph \(K_s\text{.}\)
  4. Write the initial condition and a recursive rule for the number of edges \(e_s\) of the complete graph \(K_s\text{.}\)
Check.
  2. Hint: Start with a single vertex. At each step, explain how many new vertices to add and which new edges to add.
  3. Hint: Make sure you used \(v_{s-1}\text{.}\) Check that \(v_5=5\text{.}\)
  4. Hint: Make sure you used \(e_{s-1}\text{.}\) Check that \(e_5=10\text{.}\)

17. Understand.

 
  1. Write the adjacency matrices of \(K_s\) for \(s = 1,2,3,4\text{.}\)
  2. Describe how the adjacency matrix for \(K_s\) can be constructed from the adjacency matrix for \(K_{s-1}\text{.}\)

18. Recap.

Do you know …
  1. How to construct graphs that are defined recursively?
  2. How to write a recursive definition for the number of leaves, number of vertices, or number of edges in a recursively-defined graph?
  3. How to write a recursive definition for a family of graphs?

19. Explore.

Consider the family of graphs \(T_n\) defined in Activity 8.4.C. Figure 8.4.41 shows a labeled versions of \(T_3\text{,}\) \(T_4\text{,}\) and \(T_5\text{.}\)
Figure 8.4.41. From left-to-right, labeled lopsided trees \(T_3\text{,}\) \(T_4\text{,}\) and \(T_5\text{.}\)
  1. Determine the adjacency matrices for \(T_3\text{,}\) \(T_4\text{,}\) and \(T_5\) using the vertices in alphabetical order in each case.
  2. Describe how the adjacency matrix for \(T_5\) can be constructed from the adjacency matrices for \(T_3\) and \(T_4\text{.}\)
PrevTopNext