Discrete Math Lesson
(1) A set S of integers is defined recursively by the rules:
(1) 1 ∈ S, and (2) If n ∈ S, then 2n + 1 ∈ S.
(a) Is 20 ∈ S?
(b) Is 175 ∈ S?
Explain your answers.
(2) A set, S, of strings over the alphabet Σ = {a,b,c} is defined recursively by (1) a ∈ S and
(2) if x ∈ S then xbc ∈ S. List all the strings in S of length seven or less.
8
(3) A set, S, of positive integers is defined recursively by the rule:
(1) 3 ∈ S, and (2) If n ∈ S, then 2n − 3 ∈ S. List all the elements in the set S.
(4) Give a recursive definition of the set of positive integers that end with the digit 7.
(5) Describe the strings in the set S of strings over the alphabet Σ = {a,b,c} defined recursively
by (1) c ∈ S and (2) if x ∈ S then xa ∈ S and xb ∈ S and cx ∈ S.
Hint: Your description should be a sentence that provides an easy test to check if a given
string is in the set or not. An example of such a description is: S consists of all strings of
a’s, b’s, and c’s, with more a’s than b’s. That isn’t a correct description since cab is in S
and doesn’t have more a’s than b’s, and also baac isn’t in S, but does have more a’s than
b’s. So that attempted description is really terrible. The best way to do this problem is
to use the rules to build a bunch of strings in S until a suitable description becomes obvious.
(6) (bonus) A set S of ordered pairs of integers is defined recursively by (1) (1,2) ∈ S and
(2,1) ∈ S, and (2) if (m,n) ∈ S, then (m+2,n) ∈ S, and (m,n+2) ∈ S, and (m+1,n+1) ∈
S. There is a simple description of the ordered pairs in S. What is it? Your description
should be good enough so that you can instantly decide if (12236,912242) is in S.
Needs help with similar assignment?
We are available 24x7 to deliver the best services and assignment ready within 3-4 hours? Order a custom-written, plagiarism-free paper
![](https://powerpointpresentationhelp.com/wp-content/uploads/2022/03/WhatsApp_icon.png)
![](https://powerpointpresentationhelp.com/wp-content/uploads/2022/03/205-2057855_essay-icon.png)