Proof with induction even number of letter

Question

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$

base:

1. $|w| = 0$ and $w = \epsilon$ the number of the letter d is zero and even
2. $|w| = 1$ and $w = a$ or $w = b$ same as number 1

Hypothesis:

$w$ has even number of d

Step:

I don't know how to make an induction with $w = ducvd$. Does somebody have a hint?

Answer 1

The induction step has to use the rule for buiding new words from old ones.

Indcution hypotheses : $u$ and $v$ are words with an even number of $d$ : $d_u$ and $d_v$ respectively.

The new word $w=ducvd$ will have $d_w=d_u+d_v+2$ number of $d$.

From the assumption that $d_u=2k$ and $d_v=2l$ we get that :

$d_w=d_u+d_v+2=2k+2l+2=2(k+l+1)$.

Answer 2

Induction step:

If $u$ and $v$ are words with $2n$ and $2k$ occurences of letter $d$ (here $n,k$ are nonnegative integers) then word $ducvd$ evidently has $2n+2k+2=2(n+k+1)$ occurences of letter $d$ (so an even number again).

---

Edit (showing an alternative route):

For any word $w$ in $L$ let $\overline{w}$ denote the number of occurrences of letter $d$ in $w$.

Assume that the statement is not true and let $w$ be a word in $L$ having minimal length and with $\overline{w}$ odd.

Evidently $w$ is not $a$ and $w$ is not $b$, so must have the shape $ducvd$ where $u$ and $v$ are words.

Then $\overline{u}+\overline{v}+2=\overline{w}$ must be odd, implying that $\overline u$ is odd or $\overline v$ is odd.

This however contradicts that $w$ has minimal length.

The contradiction allows us to conclude that the assumption is wrong so to conclude that the statement is true.