1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Recurrence relations

  1. Apr 24, 2009 #1

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

  2. jcsd
  3. Apr 24, 2009 #2


    User Avatar
    Homework Helper

    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
    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...
  4. Apr 24, 2009 #3

    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
    C, etc.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook