To start this off, please excuse the title as I couldn't think of a better way to word it. The following is a homework question I'm working on, for some background, I haven't done induction in a little bit of time and I'm running into some trouble wording and formatting my answer appropriately.
The question is the following:
The alphabet $A$ is $\{0,1\}$
$S = \{\text{all strings over $A$ formed by concatenating one or more copies of $0111$ or $1101$}\}$
$L(S)$ = length of $S$
Use mathematical induction to prove that for every positive integer $n$, if a string $s$ in $S$ has length $4n$, then the number of $1$'s in $s$ is a multiple of $3$.
The answer is somewhat obvious to me here as both $0111$ and $1101$ both have three $1$'s and any concatenation will result in the total number of $1$'s increasing by $3$ and keeping the total count a multiple of $3$, the problem I'm having is getting my inductive steps down on paper without it seeming like a 7 year old wrote it.
a) State what you are going to prove in symbolic form
$\forall n \in \mathbb N$ such that $L(S)=4n$ $\rightarrow$ # of $1$'s is $m$ such that $m=3k, k \in \mathbb N $
I'm pretty sure that this is not symbolic form, I tried searching online on how to properly represent this in symbolic form but I could not find anything that helped me
b) The symbolic form statement in the previous question should have the form $\forall n\in D, P(n)$
- What is the set $D$?
The set $D=\mathbb N$
- What is the predicate function $P(n)$?
I don't understand how to represent my predicate function in this case, any help is appreciated here.
Edit: After some looking around I was able to come up with the following for $P(n)$
$$P(n) = L(S) = 4n \land m=3k$$
c) Proof of base case
Case 1: $P(1)$: $0111$
$\text{number of $1$'s} = 3 \rightarrow m=3$ and $3=3k$ where $k=1$ and therefore a multiple of $3$
Case 2: $P(1)$: $1101$
$\text{number of $1$'s} = 3 \rightarrow m=3$ and $3=3k$ where $k=1$ and therefore a multiple of $3$
I'm pretty sure that is enough to prove my base case of $P(1)$ but I could be missing something too.
d) This is the beginning of the inductive step where you are stating the assumption in the inductive step and what you will be proving in that step. As you do so, identify the inductive hypothesis.
Edit: I was able to come up with the following
$L(S)$ = length of string $S$
$m$ = # of $1$'s in the string $S$
Assume that some positive integer $k$ such that $P(n)$ is true for all $n \le k$
i.e $\forall n \in {1,2,…,k}$ $L(S)=4n \land m=3n$
This is my inductive hypothesis, I have a feeling I did this part wrong but I am not sure.
e)Finish the inductive step of your proof here.
The above two parts are where I'm having trouble getting my thought down on paper, I can explain the whole thing using words but I am not sure how to go about setting up my inductive step and then completing it, I was thinking of representing $0111$ and $1101$ as their number of 1's and showing that any multiple of them concatenated to string $S$ will result in the total value of 1's being a multiple of $3$ but every time I try to represent this in anything other than words I can't seem to figure out how to do it gracefully.
I realize this is a long read but I would greatly appreciate anyone willing to help me out here and show me how to correctly complete this proof.
Best Answer
You are making an easy question difficult, partly by using poor notation and partly by using overly complicated arguments.
First of all, you may observe that $S$ is the regular language $\{0111, 1101\}^+$. The length of $S$ is meaningless, since $S$ is a language. You can only define the length of a string $s$, which is usually denoted by $|s|$. A convenient notation for the number of occurrences of $1$ in a string $s$ is $|s|_1$. For instance, $$ (1)\quad|0111| = |1101| = 4 \quad\text{and}\quad |0111|_1 = |1101|_1 = 3. $$ Let us now come back to your question. The hypothesis "if a string $s$ in $S$ has length $4n$" is actually useless, since, as we will see, the length of every word of $S$ is a multiple of $4$. Let us prove the following property:
By definition of $S$, there exist a positive integer $k$ and some strings $s_1, s_2, \ldots, s_k \in \{0111, 1101\}$ such that $s = s_1s_2 \dotsm s_k$. Note that, by $(1)$, $|s_1| = |s_2| = \ldots = |s_k| = 4$ and $|s_1|_1 = |s_2|_1 = \ldots = |s_k|_1 = 3$. Observing that $$ (2)\quad |s| = |s_1s_2 \dotsm s_k| = |s_1| + |s_2| + \dotsm + |s_k| \quad\text{and}\quad |s|_1 = |s_1s_2 \dotsm s_k|_1 = |s_1|_1 + |s_2|_1 + \dotsm + |s_k|_1 $$ one gets $|s| = 4k$ and $|s|_1 = 3k$, which proves $(*)$.
Note. If you really insist to use induction, you could prove $(2)$ by induction on $k$, but I don't think it would clarify the argument.