<s>[INST] Find recurrence relation in a counting problem In the book Galois Theory of Ian Stewart, problem 1.11 states: "Let $P(n)$ be the number of ways to arrange $n$ zeroes and ones in a row, given that ones occur in groups of three or more. Show that $P(n)=2P(n-1)-P(n-2)+P(n-4)$". 
From the recurrence relation, I guess we have to divide the problem. Here's what I did


*

*If the first position is $0$, we have $P(n-1)$ ways.

*If the first position is $1$, we have $P(n-1)$ ways subtracting some situations


And this is where I'm stuck. Any help would be appreciated. Thank you
 [/INST] $$
\begin{align}
P(n)
&=\overbrace{P(n-1)}^{\substack{\text{# of arrangements}\\\text{of $n-1$ digits}\\\text{prepending a $0$}}}
+\overbrace{P(n-1)}^{\substack{\text{# of arrangements}\\\text{of $n-1$ digits}\\\text{prepending a $1$}}}
-\overbrace{P(n-2)}^{\substack{\text{# of arrangements}\\\text{of $n-2$ digits}\\\text{prepending a $10$}}}
+\overbrace{P(n-4)}^{\substack{\text{# of arrangements}\\\text{of $n-4$ digits}\\\text{prepending a $1110$}}}\\
\end{align}
$$
The "# of arrangements of $n-1$ terms prepending a $1$" counts the arrangements starting with $4$ or more ones as well as those starting with "$10$", so we need to subtract the latter. We then need to add those arrangements starting with only $3$ ones.

Using Generating Functions
$$
\begin{align}
&\sum_{k=0}^\infty\overbrace{\vphantom{\left(\frac{x^3}{1-x}\right)^k}\left(1+\frac x{1-x}\right)}^{\text{$0$ or more zeros}}\overbrace{\left(\frac{x^3}{1-x}\frac x{1-x}\right)^k}^{\substack{\text{$3$ or more ones and}\\\text{$1$ or more zeros}}}\overbrace{\vphantom{\left(\frac{x^3}{1-x}\right)^k}\left(1+\frac{x^3}{1-x}\right)}^{\substack{\text{$0$ or $3$ or more ones}}}\\
&=\frac{1-x+x^3}{(1-x)^2}\sum_{k=0}^\infty\left(\frac{x^3}{1-x}\frac x{1-x}\right)^k\\
&=\frac{1-x+x^3}{(1-x)^2}\frac1{1-\frac{x^4}{(1-x)^2}}\\
&=\frac{1-x+x^3}{1-2x+x^2-x^4}
\end{align}
$$
The denominator of the generating function requires the recursion
$$
P(n)=2P(n-1)-P(n-2)+P(n-4)
$$
as mentioned in the text.
</s>