Find a system of recurrence relations

Question

Find a system of recurrence relations for the number of $n$-digit binary sequences with $k$ adjacent pairs of $1$s and no adjacent pairs of $0$s.

Any help on how to go about doing this would be appreciated. I'm new to the topic of recursive relations.

Answer 1

Let $S(n,k)$ be the set of $n$-bit binary sequences with $k$ pairs of adjacent ones, and let $$a_{n,k}=|S(n,k)|\;;$$ we want recurrences for $a_{n,k}$.

Suppose that $\sigma\in S(n,k)$. If $\sigma$ ends in $1$, we can append $0$ to get the sequence $\sigma^{\frown}0\in S(n+1,k)$, or we can append a $1$ to get the sequence $\sigma^{\frown}1\in S(n+1,k+1)$. If $\sigma$ ends in $0$, we can only append a $1$ to get $\sigma^{\frown}1\in S(n+1,k)$. This suggests that we may want to keep track separately of sequences ending in $1$ and sequences ending in $0$, so for $i\in\{0,1\}$ let $S_i(n,k)$ be the set of $\sigma\in S(n,k)$ that end in $i$, and let

$$a_{n,k}^{(i)}=\left|S_i(n,k)\right|\;;$$

clearly $a_{n,k}=a_{n,k}^{(0)}+a_{n,k}^{(1)}$.

Now work backwards.

• If $\sigma\in S_0(n,k)$, then $\sigma=\tau^{\frown}0$ for some $\tau\in S_1(n-1,k)$, so $$a_{n,k}^{(0)}=a_{n-1,k}^{(1)}\tag{A}\;.$$
• If $\sigma\in S_1(n,k)$, then either $\sigma=\tau^{\frown}1$ for some $\tau\in S_1(n-1,k-1)$, or $\sigma=\tau^{\frown}1$ for some $\tau\in S_0(n-1,k)$, and $$a_{n,k}^{(1)}=a_{n-1,k-1}^{(1)}+a_{n-1,k}^{(0)}\;.\tag{B}$$

It follows that

$$\begin{align*} a_{n,k}&=a_{n,k}^{(0)}+a_{n,k}^{(1)}\\ &\overset{(1)}=a_{n-1,k}^{(1)}+a_{n-1,k-1}^{(1)}+a_{n-1,k}^{(0)}\\ &\overset{(2)}=a_{n-1,k}^{(1)}+a_{n-1,k-1}^{(1)}+a_{n-2,k}^{(1)}\\ &\overset{(3)}=a_{n-2,k-1}^{(1)}+a_{n-2,k}^{(0)}+a_{n-1,k-1}^{(1)}+a_{n-2,k}^{(1)}\\ &\overset{(4)}=a_{n-2,k-1}^{(1)}+a_{n-1,k-1}^{(1)}+a_{n-2,k}\\ &\overset{(5)}=a_{n-1,k-1}^{(0)}+a_{n-1,k-1}^{(1)}+a_{n-2,k}\\ &\overset{(6)}=a_{n-1,k-1}+a_{n-2,k}\;; \end{align*}$$

step $(1)$ uses both recurrences (A) and (B), step $(2)$ applies (A) to the last term, step $(3)$ applies (B) to the first term, step $(4)$ combines the second and fourth terms to get rid of the superscripts, step $(5)$ applies (A) to the first term, and step $(6)$ combines the two superscripted terms.

An easier way to discover this recurrence, though not to derive it, is to calculate $a_{n,k}$ for $1\le n\le 5$ and $0\le k\le n-1$:

$$\begin{array}{c|cc} n\backslash k&0&1&2&3&4\\ \hline 1&2\\ 2&2&1\\ 3&2&2&1\\ 4&2&3&2&1\\ 5&2&4&4&2&1 \end{array}$$

You can now enter enter the table by rows into The On-Line Encyclopedia of Integer Sequences (OEIS) as

$$2,2,1,2,2,1,2,3,2,1,2,4,4,2,1$$

and get a single return: this matches OEIS A073044. Better yet, the description of this entry reads:

Triangle read by rows: T(n,k) (n>=1, k>=0) = number of n-sequences of 0's and 1's with no pair of adjacent 0's and exactly k pairs of adjacent 1's.

Plainly this is exactly what we want, and the only formulas given are the recurrence above and a generating function

$$G(z,t)=\frac{z(2+2z-tz)}{1-tz-z^2}=\sum_{n\ge 1}\sum_{k=0}^{n-1}a_{n,k}z^nt^k\;.$$