How can I get the following recursive relation that explained?

Question

if $b(n)$ is the number of words created by the alphabet ${a,b,c}$ with $n$ length that each word has at least one $a$ character and after each $a$ there is no $c$ character write a recursive relation for $b(n)$.

I have tried calculating the words by mind and getting the sequence of $b(n)$ numbers and then guessing the relation but calculating the words with more alphabet is difficult.

Answer 1

This is how I derived the recurrence.

Imagine the count $b(n)$ of good words to be split into two disjoint counts:

1. $\color{blue}{x(n)}$: count of good words which end with $a$.
2. $\color{green}{y(n)}$: count of good words which end with $b$ or $c$.

where a good word is defined as a word that meets our requirement - that is, it is generated from the alphabet $\{a, b, c\}$ such that it contains at least one $a$ and no $a$ is followed by $c$. If a word does not satisfy both the properties, we call it bad.

We have $b(n) = \color{blue}{x(n)} + \color{green}{y(n)}\tag{1}$

Next, we see how good words of length $n+1$ are created from words of length $n$. (You may want to spend some time thinking about this).

$$\begin{array}{rc} \text{length} & 1 & 2 & 3 & \cdots & n & n+1\\\hline\\ \color{blue}{x(n)}: & - & - & - & \cdots & \color{blue}{a}& \begin{cases}\color{blue}{a} \\\color{green}{b}\end{cases}\\\hline\\ \color{green}{y(n)}: & - & - & - & \cdots & \color{green}{b|c} & \begin{cases}\color{blue}{a}\\\color{green}{b}\\\color{green}{c}\end{cases}\\\hline\\ \color{red}{z(n)}: & \color{red}{b|c} & \color{red}{b|c} & \color{red}{b|c} & \cdots & \color{red}{b|c} & \begin{cases}\color{blue}{a}\end{cases}\end{array}$$

where $\color{red}{z(n)}$ is the count of bad words that do not contain $a$ (it is equal to $\underbrace{\color{red}{2\cdot2\cdots2}}_{n \text{ times}} = \color{red}{2^n}$).

This gives us the recurrences

$\begin{align}\color{blue}{x(n+1)} &= \color{blue}{x(n)} + \color{green}{y(n)} + \color{red}{z(n)} = \color{blue}{x(n)} + \color{green}{y(n)} + \color{red}{2^n} \\\color{green}{y(n+1)} &= \color{blue}{x(n)} + \color{green}{y(n)} + \color{green}{y(n)} = \color{blue}{x(n)} + \color{green}{2y(n)} \end{align}\tag{2}$

From $(1)$ and $(2)$ we get

$\begin{align}b(n+1) &= \color{blue}{2x(n)} + \color{green}{3y(n)} + \color{red}{2^n}\\b(n+2) &= \color{blue}{5x(n)} + \color{green}{8y(n)} + \color{red}{4\cdot2^n}\end{align}\tag{3}$

If we write $\color{blue}{x(n)}$ and $\color{green}{y(n)}$ in terms of $b(n+1)$ and $b(n+2)$ above and substitute in $(1)$, we get the needed recurrence

$b(n+2) = 3b(n+1) - b(n) + 2^n \text{ for } n \ge 0\tag{4}$

where $b(0) = 0$ and $b(1) = 1$ are the initial terms.

You can also play with this Perl program. It spits out the first few terms using both the recurrence relation and brute force.

---

EDIT: The OP told me that the second property of a good word is actually this:

• $c$ is not allowed in the substring that follows any $a$.

Below is an answer for this version.

---

Every good word is of the form $$\begin{array}{rc} \text{length} & 1 & 2 & \cdots &k-1&k &k+1&\cdots & n\\\hline\\ b(n): & b|c & b|c & \cdots &b|c &a &a|b& \cdots & a|b\end{array}$$

1. It contains at least one $a$ (so $1 \le k \le n$).
2. There is no $c$ after the first $a$ (so no substring after any $a$ contains $c$).

Good words of length $n+1$ are created from words of length $n$ in the following two ways.

$$\begin{array}{rc} \text{length} & 1 & 2 & \cdots &k-1&k &k+1&\cdots & n &n+1\\\hline\\ b(n): & b|c & b|c & \cdots &b|c &a &a|b& \cdots & a|b & \begin{cases}a\\b\end{cases}\\\hline\\ \color{red}{z(n)}: & \color{red}{b|c} & \color{red}{b|c} & \color{red}{\cdots} & \color{red}{b|c} & \color{red}{b|c} &\color{red}{b|c} & \cdots & \color{red}{b|c} & \begin{cases}a\end{cases}\end{array}$$

where $\color{red}{z(n) = 2^n}$ is the count of bad words that do not contain $a$.

This gives the recurrence

$$b(n+1) = 2 \cdot b(n) +\color{red}{z(n)} = 2 \cdot b(n) + 2^n \text{ where } n \ge 0$$

and $b(0) = 0$ is the initial term.

Answer 2

There are $n$ places to choose for the first occurrence of $a$. To the left of this first $a$ we may write any word containing only the letters $b$ and $c$, and to the right of this first $a$ we may write any word containing only the letters $a$ and $b$. It follows that $$b(n)=n\>2^{n-1}\ .\tag{1}$$ In order to obtain a linear recurrence for the $b(n)$ we require $$b(n+2)+A\> b(n+1)+B\>b(n)=0\ ,$$ and determine $A$ and $B$ such that $(1)$ is fulfilled identically in $n$. The result is $$b(1)=1, \quad b(2)=4,\quad b(n+2)-4b(n+1)+4b(n)=0\quad(n\geq1)\ .$$