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$
base:


*

*$|w| = 0$ and $w = \epsilon$ the number of the letter d is zero and even

*$|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?
 A: 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)$.

A: 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.
