# Find a recurrence relation in combinatorics

This is the first time working through a word problem with recurrence relations and I am looking to see if my workings are correct, or if there is another way to complete this problem

Find a recurrence relation for the number of $$n$$-letter sequences using the letters $$A, B, C$$ such that any $$A$$ not in the last position of the sequence is always followed by a $$B$$.

Say there are $$a_n$$ such sequences.

Case 1

(Starts with C): The remaining $$n-1$$ letters must follow the original rule, so $$a_{n-1}$$ ways.

Case 2

(Starts with B): The remaining $$n-1$$ letters must follow the original rule, so $$a_{n-1}$$ ways.

Case 3

(Starts with A): The second letter must be B, and the remaining $$n-2$$ letters must follow the original rule, so $$a_{n-2}$$ ways.

So $$a_n = 2a_{n-1} + a_{n-2}$$, with initial conditions $$a_0 = 1$$, $$a_1 = 3$$.

• Looks OK to me (quick read). – Ethan Bolker Mar 4 '18 at 16:00
• it seems to be ok. – OmG Mar 4 '18 at 16:00
• Seems fine to me. – Jaideep Khare Mar 4 '18 at 16:01
• awesome thanks foreveryones input! – user123 Mar 4 '18 at 16:01
• could someone explain why $a_0 = 1,a_1 = 3$ – user123 Mar 4 '18 at 17:08

To answer OP's question in the comments: "could someone explain why $a_0=1,a_1=3$":
When $n=0$, there is one $0$-letter sequence, the empty sequence $( )$. So we have $a_0=1$.
When $n=1$, there are $3$ one-letter sequences that satisfy the criteria: $(A)$, $(B)$, and $(C)$, so we have $a_1=3$.
Two initial conditions, $n=1$ and $n=0$, are needed because our recurrence relation involves two previous terms. If we were to just use $n=0$ as an initial condition, $a_{n-2}$ would not always be well-defined (for example, if we wished to find $a_1$ by evaluating $a_1=2a_0+a_{-1}$).