I'm supposed to solve the following problem.
What's the number $F(n)$ of words with $n$ letters using the alphabet $x,y,z$ such that maximal sequences of $x$'s are of even length, and the same for $y$'s? (For instance, $zxxxxzyy$ is legal but not $zxxxzzyy$.)
I just tried to split into cases:
- If the first letter is $z$, then we omit the first letter and move to $F(n-1)$
- If the first letter is $x$ or $y$, omit the first two and move to $F(n-2)$.
This gives me the following recurrence relation to solve $$F(n)=F(n-1)+2F(n-2).$$
Is this correct?
Yes, the analysis is correct, as is the recurrence, but you should add the initial conditions $F(0)=F(1)=1$.
By the way, if you then calculate a few values, you can easily find a nicer recurrence:
$$\begin{array}{rcc} n:&0&1&2&3&4&5&6&7\\ F(n):&1&1&3&5&11&21&43&85 \end{array}$$
If you look at the second line, especially the righthand end of it, you’ll see that $F(n+1)$ is approximately $2F(n)$ for each $n$. In fact, it appears to alternate between $2F(n)-1$ when $n$ is even and $2F(n)+1$ when $n$ is odd. If that’s true, we have a first-order recurrence
$$F(n+1)=2F(n)-(-1)^n\tag{1}$$
with $F(0)=1$ for the initial condition. This doesn’t seem to have a nice, straightforward combinatorial explanation, but the second-order recurrence that you found implies that
$$F(n+1)-2F(n)=2F(n-1)-F(n)=-\big(F(n)-2F(n-1)\big)$$
for each $n\ge 0$, and $F(1)-2F(0)=-1=-(-1)^0$, from which $(1)$ follows at once by induction on $n$.