Recursive Definitions

Question

I have two recursive definitions that I need to determine if they are correct. The first one is:

The set S of all positive integer multipliers of 5 can be described by the following recursive definition:

$5 \in S; x \in S \rightarrow x + 5 \in S.$ True or false.

The second one is:

Choose all of the correct recursive definitions of the set of strings formed by an odd number of 1's:

{$1, 111, 11111, 1111111, ...$}

And the choices are:

A) $1 \in S$

$X \in S \rightarrow X11 \in S$

B) $11 \in S$

$X \in S \rightarrow X11 \in S$

C) $1 \in S$

$X \in S \rightarrow X1 \in S$

D) $11 \in S$

$X \in S \rightarrow X1 \in S$

I am pretty sure that the first question is true because any positive integer + 5 should still be in $S$. For the second one, I am totally lost. Thanks in advance!

Answer 1

Hint: Just work through the first few terms in the recursion until you get a sense of the pattern.

For example, let's see why option D is wrong. We know that $11 \in S$, so $(11)1 \in S$. Applying the recursive rule again, we know that $(111)1 \in S$. Likewise, $(1111)1 \in S$. So: $$ S = \{11, 111, 1111, 11111, \ldots\} $$ which doesn't match what we want.