# Proof with induction even number of letter

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$$.

Examples:

$$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?

• 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. Commented Oct 12, 2019 at 0:49
• ok but how can I write the induction? Commented Oct 12, 2019 at 9:28

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.