No ABs in this string

There is $1$ string which contains $0$ characters (an empty string), and it does not contain $\text{AB}$ . Therefore, $G_0=1$ .

There are $3$ strings which contain $1$ character: $\begin{array}{ccc} \text{A}, & \text{B}, & \text{C} \end{array}$ . None of these contain $\text{AB}$ . Therefore, $G_1=3$ .

To obtain the number of strings for $n=2$ , append an $\text{A}$ , $\text{B}$ , or $\text{C}$ to each of the previous strings.

$\begin{array}{ccc} \text{AA}, & \color{#D61F06}{\text{AB}}, & \text{AC}, \\ \text{BA}, & \text{BB}, & \text{BC}, \\ \text{CA}, & \text{CB}, & \text{CC} \\ \end{array}$

The number of strings is $3$ times as much as the previous number of strings. However, note that $1$ of those strings contains $\text{AB}$ . It occurred by appending a $B$ to one of the previous strings which ended in an $\text{A}$ . Thus, $G_2=8$ .

To obtain the number of strings for $n=3$ , append an $\text{A}$ , $\text{B}$ , or $\text{C}$ to each of the previous strings.

$\begin{array}{ccc} \text{AAA}, & \color{#D61F06}{\text{AAB}}, & \text{AAC}, \\ \text{ACA}, & \text{ACB}, & \text{ACC}, \\ \text{BAA}, & \color{#D61F06}{\text{BAB}}, & \text{BAC}, \\ \text{BBA}, & \text{BBB}, & \text{BBC}, \\ \text{BCA}, & \text{BCB}, & \text{BCC}, \\ \text{CAA}, & \color{#D61F06}{\text{CAB}}, & \text{CAC}, \\ \text{CBA}, & \text{CBB}, & \text{CBC}, \\ \text{CCA}, & \text{CCB}, & \text{CCC} \\ \end{array}$

The number of strings is $3$ times as much as the previous number of strings. However, note that $3$ of those strings contain $\text{AB}$ . Those occurred by appending a $B$ to one of the previous strings which ended in an $\text{A}$ . Thus, $G_3=21$ .

Without writing out the next case, predict how many there will be. There will be $3$ times as many strings as $G_3$ , but some number will be subtracted that contain $\text{AB}$ . The number that is subtracted will be the number of strings that previously ended in $A$ . The number of strings that previously ended in $A$ is $8$ . This the same as $G_2$ .

$G_4=3G_3-G_2$

In terms of $n$ , this is:

$G_n=3G_{n-1}-G_{n-2}$

Proceeding completely logically, Suppose I make this String by writing letters on a large sheet from left to right and that I have already written $n$ characters. For the $n+1^{th}$ character, there are essentially three possibilities ( A,B or C ). So $3G_{n}$ . But wait, what if the $n^{th}$ character was A ? Well, we simply subtract that case. So suppose we have written down $n-1$ characters and the $n^{th}$ character is fixed at A . Now, the unfavourable case was that the $n+1^{th}$ character in this case be B . Hence, $G_{n-1}$ .

Therefore, the relation - $G_{n+1}=3G_{n} - G_{n-1}$