Find a recursive definition of this sequence

Question

I always have some difficulty with problems of this type, and I was wondering if there was a typical trick that makes it reasonable.

Let $W_n$ be the number of words of length $n$ formed with the letters $A$ and $B$ such that

• There are no words that contain sequences of $A$s with length exactly 2

• There are no words that contain sequences of $B$s with length exactly 2 or 3.

Examples of words: $AAAB, ABABABA, ABBBBAAABA$, and of non-words: $AAB, ABBBA$, etc.

These "recursion with constraints" type problems always cause me difficulty. I want to write $W_n = f(W_{n-1}, W_{n-2}, \ldots, W_{n-k})$ for some fixed $k$. I tried to break it into cases based on what the last letter is, so $W_n = A_n + B_n$ where $A_n$ is the number of words of length $n$ that end in $A$ and $B_n$ defined similarly. Then getting recursive definitions for $A_n$ in terms of some $B_{n-k_i}$ and $W_{n-k_j}$ and likewise recursive definitions for $B_n$ produces a whole mess of terms that don't cancel even when you get these $W_{n-11}$ terms showing up. Surely I'm missing the trick?

Answer 1

We can write down an infinite recursion and then simplify.

Let $A_n$ be the number of such sequences ending in A, and $B_n$ be the number of such sequences ending in B. We count the empty string in both.

Then, for $n \ge 1$, we have $$ A_n = B_{n-1} + B_{n-3} + B_{n-4} + B_{n-5} + \dotsb $$ because we can add A or AAA or AAAA or AAAAA to the end of a string ending in B, but not both. So for $n \ge 2$, we have \begin{align} A_n - A_{n-1} &= (B_{n-1} + B_{n-3} + B_{n-4} + B_{n-5} + \dotsb) - (B_{n-2} + B_{n-4} + B_{n-5} + B_{n-6} + \dotsb) \\ &= B_{n-1} - B_{n-2} + B_{n-3}. \\ A_n &= A_{n-1} + B_{n-1} - B_{n-2} + B_{n-3}. \end{align} We can do the same thing for $B_n$, except that $B_n$ won't have an $A_{n-3}$ term in the recurrence. For $n\ge 2$, we get \begin{align} B_n - B_{n-1} &= (A_{n-1} + A_{n-4} + A_{n-5} + \dotsb) - (A_{n-2} + A_{n-5} + A_{n-6} + \dotsb) \\ &= A_{n-1} - A_{n-2} + A_{n-4}. \\ B_n &= A_{n-1} + B_{n-1} - A_{n-2} + B_{n-4}. \end{align} This is already enough to make the problem a finite linear recurrence, but we can still try to simplify it further.

---

For $n \ge 1$, we have $W_n = A_n + B_n$, so we have $$ W_n = 2W_{n-1} - W_{n-2} +B_{n-3} + A_{n-4} $$ by adding the two equations. Unfortunately, we still have a mismatched $A$ and $B$ to deal with here.

Expanding $B_{n-3}$ and $A_{n-4}$ out using their recurrences, we get \begin{align} W_{n} &= 2W_{n-1} - W_{n-2} + (W_{n-4} - A_{n-5} + A_{n-7}) + (W_{n-5} - B_{n-6} + B_{n-7}) \\ &= 2W_{n-1} - W_{n-2} + W_{n-4} + W_{n-5} - A_{n-5} - B_{n-6} + W_{n-7} \end{align} which again has a mismatched $A$ and $B$, but now in the reverse order. So if we subtract $W_{n-2}$ from both sides, we get \begin{align} W_n - W_{n-2} &= (2W_{n-1} - W_{n-2} + W_{n-4} + W_{n-5} - A_{n-5} - B_{n-6} + W_{n-7}) \\&\quad - (2W_{n-3} - W_{n-4} + B_{n-5} + A_{n-6}) \\ &= 2W_{n-1} - W_{n-2} - 2W_{n-3} + 2W_{n-4} - W_{n-6} + W_{n-7} \end{align}

and the final recursion is $W_n = 2W_{n-1} - 2W_{n-3} + 2 W_{n-4} - W_{n-6} + W_{n-7}$. (This may not fly for small $n$ - in particular, $W_0 \ne A_0 + B_0$ - but for $n> 7$ all the manipulations above are valid.)

Answer 2

Let $w(n)$ be the number of qualifying words of length $n$.

Then $w$ satisfies the recursion $$w(n)=2w(n-1)-2w(n-3)+2w(n-4)-w(n-6)+w(n-7)$$ for $n\ge 8$, with initial values \begin{align*} w(0)&=1\\ w(1)&=2\\ w(2)&=2\\ w(3)&=3\\ w(4)&=6\\ w(5)&=11\\ w(6)&=18\\ w(7)&=30\\ \end{align*} The above recursion can be derived as follows . . .

Define functions $a_1,a_3,b_1,b_4$ by

• $a_1(n)$ is the number of qualifying words of length n for which the last constant block is exactly "A".
• $a_3(n)$ is the number of qualifying words of length n for which the last constant block ends with "AAA" (i.e., at least $3$ consecutive occurrences of "A").$\\[6pt]$
• $b_1(n)$ is the number of qualifying words of length n for which the last constant block is exactly "B".
• $b_4(n)$ is the number of qualifying words of length n for which the last constant block ends with "BBBB" (i.e., at least $4$ consecutive occurrences of "B").

Then we get the following linked recursion: \begin{align*} w(n)&= \begin{cases} 1\;\text{if}\;n=0\\ a_1(n)+a_3(n)+b_1(n)+b_4(n)\;\text{if}\;n > 0\tag{eq1}\\ \end{cases} \\[4pt] a_1(n)&= \begin{cases} 0\;\text{if}\;n<1\\ 1\;\text{if}\;n=1\\ b_1(n-1)+b_4(n-1)\;\text{if}\;n > 1\tag{eq2}\\ \end{cases} \\[4pt] a_3(n)&= \begin{cases} 0\;\text{if}\;n<3\\ 1\;\text{if}\;n=3\\ b_1(n - 3) + b_4(n - 3)+a_3(n-1)\;\text{if}\;n > 3\tag{eq3}\\ \end{cases} \\[4pt] b_1(n)&= \begin{cases} 0\;\text{if}\;n<1\\ 1\;\text{if}\;n=1\\ a_1(n-1)+a_3(n-1)\;\text{if}\;n > 1\tag{eq4}\\ \end{cases} \\[4pt] b_4(n)&= \begin{cases} 0\;\text{if}\;n<4\\ 1\;\text{if}\;n=4\\ a_1(n - 4) + a_3(n - 4)+b_4(n-1)\;\text{if}\;n > 4\tag{eq5}\\ \end{cases} \\[4pt] \end{align*} Applying the linked recursion, we get \begin{align*} w(0)&=1\\ w(1)&=2\\ w(2)&=2\\ w(3)&=3\\ w(4)&=6\\ w(5)&=11\\ w(6)&=18\\ w(7)&=30\\ \end{align*} Next, we unlink the linked recursion . . .

Using $(\text{eq}2)$, we can eliminate $a_1$.

Then, using $(\text{eq}4)$, we can eliminate $b_1$.

Then, using $(\text{eq}5)$, we can eliminate $a_3$.

Based on the eliminations, from $(\text{eq}1)$ we get $$ w(n)=2b_4(n+3)-4b_4(n+1)+3b_4(n)+2b_4(n-1)-3b_4(n-2)+b(n-3)+b(n-4)-b_4(n-5) $$ for $n\ge 6$, and from $(\text{eq}3)$ we get $$ b_4(n)=2b_4(n-1)-2b_4(n-3)+2b_4(n-4)-b_4(n-6)+b_4(n-7) $$ for $n\ge 8$.

Since shifts of $b$ satisfy the same recursion as $b$, and since $w$ is a linear combination of $b$ and shifts of $b$, it follows that $w$ also satisfies the same recursion as $b$, hence we get $$w(n)=2w(n-1)-2w(n-3)+2w(n-4)-w(n-6)+w(n-7)\tag{eq6}$$ for $n\ge 13$.

We already have the values of $w(n)$ for $0\le n\le 7$.

Applying the linked recursion, we can get the values of $w(n)$ for $8\le n\le 12$, and it can then be verified that $(\text{eq}6)$ fails for $n=7$, but holds for $8\le n\le 12$, hence holds for all $n\ge 8$.

Answer 3

Maybe this graph will be of assistance:

You want to count the walks of length $n$ starting from the left-most state and ending up in any of the blue states.

Answer 4

Here is a rewriting of above work using automaton and generating functions. The associated grammars need to be unambiguous; if not, because of the copies, the numbers obtained will be higher than the right ones.

By the second diagram, one may write

$A = x + xC + xD$ where :

$A = a_1x + a_2x^2 + a_3x^3 + ... $is the generating function (or the string index) for words that ends exactly in $0$. We have similar expressions for B, C and D.

Similarly, the other three equations are:

$B = x^3 + xB + x^3C + x^3D $

$C = x + xA + xB$

$D = x^4 + x^4A + x^4B + xD$

Here $x$ stands for $0$ or $1$, $x^3$ covers the bit string $000$; $x^4$ covers the bit string $1111$;

The above (second) system easily solves to the same solution as the first diagram :

here (for example), $x + {x^3 \over 1-x } $ encodes the set { 0, 000, 0000, 00000, ....}

the two equations are

$ A+B = {x-x^2+x^3 \over 1-x } ( C + D + 1 ) $ and

$ C+D = {x-x^2+x^4 \over 1-x } ( A + B + 1 ) $

that easily solves to $ W=A+B+C+D= {2x - 2x^2 - x^3 + 4x^4 -x^5 -2x^6 + 2x^7 \over 1 - 2x + 2x^3 - 2x^4 + x^6 - x^7} $

$= 2+2x +3x^2 +6x^3 +11x^4 +18x^5+30x^6 +50x^7 +85x^8 +143x^9+ 241x^{10} + ...$

The denominator encodes the required recurrence.