0
  1. $010$ can be generated.
  2. 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.

Arron
  • 13
  • 2
  • What did you do or think about this problem? – Tryss Jul 21 '15 at 18:40
  • Without using the principle of induction my best guess was that rule 1 is the base case hence there will always be one 0 more than 1. The order in which the sequences are displayed do not matter because they just add one 0 and one 1 to the sequence s. BUT the question demands induction.. I can't see any other way to explain it rather than the way I just did. – Arron Jul 21 '15 at 18:48

1 Answers1

0

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$

A.E
  • 2,473