I have to proof that in a word $w$ the number of the letter d is always even.

Let $L \subsetneq \Sigma^*$ be a language over the alphabet $\Sigma = \{a,b,c,d\}$ such that a word $w$ is in $L$ if and only if it is $a$ or $b$ or of the form $w = ducvd$ where $u$ and $v$ are word of $L$.


$dacad$, $ddacbdcad$, $dddbcbdcdbcbddcad$

I know there are three cases:

  1. $|w| = 0$ the number of the letter d is zero and even

  2. $|w| = 1$ and $w = a$ or $w = b$ same as number 1

  3. $|w| = 5$ and $w = ducvd$ the number of letter d is even

    I know how induction works, but I don't know to write the base, hypothesis and step. I think it works with the length of $w$. Does somebody have a hint?

  • $\begingroup$ The base cases are 1) and 2); the hypothesis is "the number of ds in the string is even"; the step is in 3), where you prove the hypothesis by induction over the subwords of $w$, not the length. $\endgroup$
    – siracusa
    Oct 12, 2019 at 0:49
  • $\begingroup$ ok but how can I write the induction? $\endgroup$
    – skinnyBug
    Oct 12, 2019 at 9:28

2 Answers 2


The proof is by induction on the length of $w$. If $|w| \leq 2$ then necessarily $w = a$ or $w = b$, and in both cases $w$ doesn't contain any $d$'s. If $|w| \geq 3$ then necessarily $w$ is of the form $ducvd$, where $u,v \in L$ are shorter words. By induction, each of $u,v$ contains an even number of $d$'s. It follows that $w$ also contains an even number of $d$'s: if $u,v$ contain $2s,2t$ many $d$'s (respectively), then $w$ contains $2s+2t+2=2(s+t+1)$, which is also even.


Alternatively show for every k: There is no w containing 2k+1 d’s.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.