Suppose S is a recursively defined set, defined by - the number 1 is in S - if n

Question

Suppose S is a recursively defined set, defined by
- the number 1 is in S
- if n is in S, then so is 3n + 2
- if n is in S, then so is 5n - 1
- if n is in S, then so is n + 7.

Suppose you want to prove using structural induction that all members of S have a certain property.

1. What do you have to prove in the base step?
     A. That the numbers 5, 4, and 8 have the property
     B. That the number 1 has the property, and the numbers 5, 4, and 8
   C. That the number 1 has the property
   D.  That the numbers 5, 4, and 8 are in the set S

2. What do you have to prove in the inductive step?
   A. That if 3n+2, 5n-1 and n+7 have the property, so must n.
   B. That the numbers 5, 4 and 8 must also have the property.
   C. That if n has the property, so do 3n+2, 5n-1 and n+7.
   D. That if n is in the set, 3n+2, 5n-1 and n+7 must also be in the set.

Explanation / Answer

1 D.  That the numbers 5, 4, and 8 are in the set S

2 D. That if n is in the set, 3n+2, 5n-1 and n+7 must also be in the set.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.