$1\mathrm{.}2$ Problem $2[10$pts$]$

Problem $2.$ Suppose we have an m$-$letter alphabet $\backslash$Sigma $=\{0,1,$dots,m$-1\}.$ Let W$\_($n$)$ be the set of strings $\backslash$omega in$\backslash$Sigma $^($n$)$

such that $\backslash$omega does not have $00$ as a substring. Let f$\_($n$)$:$=|$W$\_($n$)|.$ Write down an explicit recurrence for f$\_($n$),$ including

the base cases. Clearly justify each recursive term.

Answer.