Solving Recurrence Relation for Letter Sequences with A, B, C

[bodensee9]

Hello:

I am asked to find a recurrence relation for the number of n letter sequences composed of A, B, C where every A that is not in the last position is followed by a B.

So, would this be:

A| (we have A(n-2) sequences) + 0 if A is in the last position
B| we have A(n-1)
C| we have A(n-1)

So does this mean that A(n) = A(n-1) + 2*A(n-1)? But this seems simplistic ...

Thanks.

 

[lanedance]

hi bodensee9

I'm not too sure what you mean by A(n), if we let N(n) be number of terms given n letters, i would start by looking at n=1, and would take it to mean you can have:
A or
B or
C
so N(1) = 3, with 1 term ending in A

then for n=2
AB only (1)
BA, BB, BC (3)
CA, CB, CC (3)
so N(2) = 7, with 2 terms ending in A...

 

[bodensee9]

Hello:

Thanks, I solved it I think.

A(n-1) means "a sub n-1" because I don't know how to type subscript on here.

I took your approach, and broke things down into
A
B
C, etc.