Question 61
Given a finite string $S$ of symbols $X$ and $O$, we write $\Delta(S)$ for the number $X$'s in $S$ minus the number of $O$'s. (For example, $\Delta(XOOXOOX) = -1$.) We call a string $S$ balanced if every sub-string $T$ of (consecutive symbols) $S$ has the property $-2 \le \Delta(T) \le 2$. (Thus $XOOXOOX$ is not balanced, since it contains the sub-string $OOXOO$ whose $\Delta$-value is $-3$.) Find, with proof, the number of balanced strings of length $n$.