• Support PF! Buy your school textbooks, materials and every day products Here!

Recurrence relations

  • Thread starter bodensee9
  • Start date
  • #1
178
0
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.
 

Answers and Replies

  • #2
lanedance
Homework Helper
3,304
2
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...
 
  • #3
178
0
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.
 

Related Threads for: Recurrence relations

  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
0
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
7
Views
3K
Top