Number of binary strings with sub-string constraint

Question

How many binary strings of length $n$: $a_1a_2\dots a_n$ are there, such that for every sub-string of k consecutive numbers $a_ia_{i+1}\dots a_{i+k-1}$ and $\forall k, 1 \leq k \leq n$, the difference between number of 0's and number of 1's is not greater than 2?

This is a question from a local competiton. I supposed that we should use the recurrence relation and then induct on $n$. Any idea?

Answer 1

This series is known as A027383. I find the recurrence $$s(0) = 1,\; s (1)=2, \;s (n+2)=2s (n)+2$$

most accessible.

Consider drawing a tree of valid strings. You'll only have to draw 5 levels until subtrees start repeating.

Answer 2

Think of starting at $\langle 0,0\rangle$ and following a path determined by the binary string, taking one step for each bit: if you’re at $\langle m,n\rangle$, go to $\langle m+1,n+1\rangle$ if the next bit is $0$, and to $\langle m+1,n-1\rangle$ if it’s $1$. (In other words, a $0$ bit indicates a step up and to the right, while a $1$ bit indicates a step down and to the right.) The condition on substrings amounts to saying that if $h$ and $\ell$ are the maximum and minimum $y$-coordinates along the path, then $h-\ell\le 2$. Thus, every allowable path lies between $y=0$ and $y=2$, between $y=-1$ and $y=1$, or between $y=-2$ and $y=0$. Call $h-\ell$ the width of the path.

Suppose that an allowable path of length $n$ terminates at $\langle n,2\rangle$; the entire path must lie between $y=0$ and $y=2$, so it’s easy to see that we can extend the bit string for the path by $10$ or by $11$ and still have an allowable path.

• Show that no matter where a path of length $n$ and width $2$ terminates, there are exactly $2$ two-bit extensions of its bit string that yield allowable paths.

• Show that there are exactly two allowable paths of length $n$ and width $1$, and that each of these produces $3$ allowable paths of length $n+2$, two of which are of width $1$.

• Conclude that if $a(n)$ is the number of allowable paths of length $n$, then $$a(n+2)=2a(n)+2\;.$$

You know $a(0)$ and $a(1)$, so you can solve this as two separate recurrences, one for even $n$ and one for odd $n$. You might even want explicitly to set $b(n)=a(2n)$ and $c(n)=a(2n+1)$ for $n\in\Bbb N$, so that $b(n+1)=2b(n)+2$ and $c(n+1)=2c(n)+2$; these sequences satisfy the same recurrence, so you need only solve it once in general and then substitute in the different initial values.