, 2007

The balanced strings consists of $X$'s and $O$'s arranged alternately, or with as many as two consecutive letters of the same kind. Such occurrences of double letters must happen alternately with an even number (possibly zero) of single letters between any two double occurrence. If $b_n$ is the number of balanced strings of length $n$, we show that
$$b_{n+2} = 2b_n + 2.$$
For $n=1$, we have the strings $X$ and $O$, so that $b_1 = 2$. For $n=2$, the balanced strings are $XX$, $XO$, $OX$, $OO$ so that $b_2 = 4$. Similarly, we have for $n=3$ the balanced strings $XXO$, $XOX$, $XOO$, $OXX$, $OXO$, $OOX$, giving $b_3 = 6$. However, for $n=4$, we see that the strings are $XXOX$, $XXOO$, $XOXX$, $XOXO$, $XOOX$, $OXXO$, $OXOX$, $OXOO$, $OOXX$, $OOXO$ and hence $b_4 = 10$.
Let $x_n, y_n, z_n$ respectively denote the number of balanced strings of length $n$ that end with $XX$; that end with $XO$ and whose last occurrence of a double letter was $XX$; and that end with $XO$, but whose last occurrence of a double letter was $OO$. Note that $X$ and $O$ can be interchanged

in any balanced string. Hence $x_n, y_n, z_n$ also denote the number of balanced strings of length $n$ that end with $OO$; that end with $OX$ and whose last occurrence of a double letter was $OO$; and that end with $OX$, but whose last occurrence of a double letter was $XX$. This shows that $b_n = 2x_n + 2y_n + 2z_n - 2$ (we count purely alternating strings $XOXO... XO$ and $OXOX... OX$ twice; once among $y_n$ and once among $z_n$). Thus $b_n + 2 = 2(x_n + y_n + z_n)$. We can form the strings of length $n+2$ from such string of length $n$ in exactly the following ways;
(i) if already ending with $XX$, we may add either $OO$ or $OX$, but nothing else;
(ii) if ending with $XO$, with last double occurrence $XX$, we can add $OX$ or $XO$, but nothing else;
(iii) if ending with $OX$, with last double occurrence $OO$, we can add $XO$ or $OX$, but nothing else.
This gives $2(x_n + y_n + z_n)$ strings. Similarly, by interchanging $X$ and $O$, we get $2(x_n + y_n + z_n)$ more strings. Thus
$$b_{n+2} + 2 = 4(x_n + y_n + z_n) = 2(b_n + 2).$$
Using the initial conditions, we get
$$b_{2n} = 2 \cdot 2^n - 2, \quad b_{2n-1} = 2^{n+1} - 2.$$