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?


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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.