More $1$s than $0$s in recursively defined set? Let $S$ be the set of strings defined recursively by:
Basis Step: $1 \in S$
Recursive Step: If $s \in S$, then $01s \in S$, $10s \in S$, $0s1 \in S$, $1s0 \in S$, $s10 \in S$, $s01 \in S$, $s1 \in S$ and $1s \in S$.  


*

*Prove that if $s \in S$ then "$1$" occurs in $s$ more times than "$0$".

*Is $10011 \in S$ ?  If so, show how to construct $10011$ from the definition?  If not, why not?
I simply have no clue where to start with this.  Please explain step by step how you do it.  Thanks!
 A: Hint: You can prove there are more 1's than 0's by induction on the number of recursive steps, starting with the string $1$ which has no recursive steps. All you need is that each recursive step weakly increases the difference between the number of 1 minus the number of 0.
A: It seems like you are not fully confident applying induction yet, so I have included more details than normally required for this kind of problem.
1.
Induction hypothesis: Assume that for some number of recursive steps, $n$, any string $s$ produced from applying $n$ rules to $1 \in S$ contains more 1's than 0's.
Inductive step: We wish to show that any string produced from applying $n+1$ rules to $1 \in S$ contains more 1's than 0's. By the induction hypothesis, we know that after $n$ of those steps, the result $s$ has more 1's than 0's. Applying another rule to $s$ will make $n+1$ steps and create one of $\{01s, 10s, 0s1, 1s0, s10, s01, s1, 1s\}$. We see that in all cases, the number of 1's increase by 1, while the number of 0's increase by at most 1, so since $s$ had more 1's than 0's, after applying another rule that is still the case, which is what we wished to show.
Base case: Any string produced after applying $0$ rules to $1 \in S$ is simply $1$ which has more 1's than 0's.
Conclusion: When $n=0$, the induction hypothesis is true. We have shown that if the induction hypothesis is true for $n$, then it is true for $n+1$ as well. So it is true for $0, 1, 2, \dots$. But the strings produced after $0, 1, 2, \dots$ applications of rules are exactly the elements of $S$, so for any $s \in S$ we can find a value of $n$ for which the induction hypothesis is true and thus $s$ has more 1's than 0's.
2. Yes. $1 \in S \implies 01(1) \in S \implies 10(011) \in S$.
