Results 1 to 2 of 2

Math Help - Recurrence Relation

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    23

    Recurrence Relation

    Passwords for a certain computer system are strings of uppercase letters. A valid password must contain an even number of X's. Determine a recurrence relation for the number of valid passwords of length n.

    Hint: Either add a non-X to the end of a good word of length n-1
    or
    Add an X to the end of a "not-good" code word of length n-1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Let g_n be the number of good passwords of length n, and let b_n be the number of bad passwords. The hint allows finding g_{n+1} through g_n and b_n. Also, g_n+b_n is the number of all words of length n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 16th 2011, 12:27 AM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2010, 03:15 AM
  3. Recurrence Relation HELP
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2009, 02:18 PM
  4. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 07:20 PM
  5. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2008, 09:02 AM

Search Tags


/mathhelpforum @mathhelpforum