- $010$ can be generated.
- If $s$ is a sequence which can be generated by these rules, then $01s, 10s, 0s1, 1s0, s01$, and $s10$ can all be generated.
*Prove, by induction, that in any sequence generated by these rules, there are more $0$'s than $1$'s.
PART 2 Again. consider sequences of $0$'s and $1$'s, this time generated according to the following rules: $10$ can be generated.
$01$ can be generated.
If $s$ is a sequence which can be generated by these rules, then $0s1$ and $1s0$ can be generated by these rules.
If $s$ is a sequence which can be generated by these rules, then the sequence $ss$ ($s$ followed by another copy of $s$) can be generated.
If $s$ is a sequence which can be generated by these rules, and $s$ is of the form $t00$ or $t11$ for some smaller sequence $t$, then $t$ itself can be generated.
Prove that no sequence with an odd length can be generated by these rules.
When using induction to prove a property of a generated set, there are two steps.
First, show the given property holds for the set of basis elements. In this case, part one has just one basis element ($\{010\}$) and part two has two ($\{01, 10\}$).
Then assume it holds for any element up to a given "size". Often there are multiple choices for size. Here, you could assume the property holds for any element $s$ whose length is less than some integer $k$. Or you could induct on the number $n$ of operations performed starting from the basis element.
Using this assumption, prove that the property is maintained no matter which way a new element is created using $s$.
EDIT: A simple example may help. Suppose $S$ is a set defined recursively as follows: $$\{a, b\} \subset S$$ $$\forall s \in S, asb \in S$$ Now I want to prove the following claim: for any $s \in S$, the number of $a$'s in $s$ (denoted $n_a(s)$) and the number of $b$'s in $s$ (denoted $n_b(s)$) differ by $1$ (hence $|n_a(s) - n_b(s)| = 1$) .
To proceed by induction, first we note that the base case is true. Next, assume true for $s$. Note that the new element created $asb$, $$|n_a(asb) - n_b(asb)| = |n_a(s) + 1 - (n_b(s) + 1)| = |n_a(s) - n_b(s)| = 1$$ where the last equality is from our inductive hypothesis. Thus, $\forall s \in S: |n_a(s) - n_b(s)| = 1$