Find a generating function for the $0-1$ strings not containing the string $010.$ Show the number $c_n$ of such strings obeys the recurrence relation

$c_0=1$

$c_1=2$

$c_2=4$

$c_n=2c_{n-1}-c_{n-2}+c_{n-3},n>=3$

Provided is just a hint for solution.

If $S$ is a set of strings then

$S^{**}=lon+S{S}^{**}=lon+S^{**}S$

Thus

The forbidden substring $010$ occurs exactly whenever one of the underlined copies of ${00}^{**}{11}^{**}$ contributes ${00}^{**}1.($The other copy of ${00}^{**}{11}^{**}$ is not followed by a $1,$ and cannot contain the beginning of a string $010.)$ Our desired decomposition thus replaces these copies of ${00}^{**}{11}^{**}$ by

$({00}^{**}{11}^{**}-{00}^{**}1)={00}^{**}{111}^{**}.$