Find recursion for number of strings length of n above {$A,B,C$} without AA and BB

38 Views Asked by At

Okay, I tried something, got close, but no idea why my answer is wrong.
I pick C >> $n-1$ options.
I Pick A (Here is problem):
A = n-1 options -(subtracting) (AB = n-2 options - ABB = n-3 options))
Which gets me:
$a_n = 2a_{n-1} - a_{n-2} + a_{n-3}$
Why is my answer wrong? I used the two mistakes.
Why is it: $a_n = 2a_{n-1} + a_{n-2}$