1
$\begingroup$

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$.

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

It looks good to me.

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}$).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks for clarifying $\endgroup$ – user123 Mar 4 '18 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.