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

Problem $3.$ Suppose we have the alphabet $\backslash$Sigma $=\{$x$,$y$\}.$ For n$>=0,$ let W$\_($n$)$ be the set of strings $\backslash$omega in$\{$x$,$y$\}^($n$)$ where

$\backslash$omega contains yyy 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.