Recursion question I think?

[blamocur]

Someone on discord found the recursive formula a(n) = 3a(n-1)-2a(n-2)+2a(n-3)
Their explaination was:

take all the valid strings of length n-1 and append an A,B or C at the end in 3a(n-1) ways.the ones ending in A,B are valid, but some of the ones ending in C aren't, namely when the (n-1)-st digit is A or B. there are 2a(n-2) of these, since to construct them, you start with a valid string of length n-2 and append AC or BC at the end. moreover, there are those valid strings ending in ACC or BCC which are not obtained in the preceding way (the first n-1 digits of these strings are not themselves valid), and there are 2a(n-3) of these (edited)

wondering if the reasoning is right

I like this one better than mine. It looks correct, and it does produce the same numbers as mine.
Since there is a better solution posted now I'll post mine for completeness:
[math]F_n = 2F_{n-1}+1 + \sum_{k=3}^{n} F_{n-k}[/math]For both recursions [imath]F_0 = 1, F_1 = 2, F_3=5[/imath]

 

[Cubist]

Yes I included those

Here is the list I tested
AAAA
AAAB
AABA"
AABB
AACC
ABAA
ABAB
ABBA
ABBB
ABCC
ACCA
ACCB
ACCC
BAAA
BAAB
BABA
BABB
BACC
BBAA
BBAB
BBBA
BBBB
BBCC
BCCA
BCCB
BCCC
CCAA
CCAB
CCBA
CCBB
CCCA
CCCB
CCCC

I get the same list.
And for 5 letters I get 83. For 6 I get 209

 

[blamocur]

And for 5 letters I get 83. For 6 I get 209

Ditto.

 

[Dr.Peterson]

I get 21 ... but about to check it.

No, that's clearly wrong. I'll go back to my calculations.

What I had missed is that if the C's are not all adjacent to another C, they are not necessarily all isolated. So the method I was trying won't work.

 

[blamocur]

What I had missed is that if the C's are not all adjacent to another C, they are not necessarily all isolated. So the method I was trying won't work.

I made the same mistakes initially in my scripts.