Stuck on where to start - this Discrete Math class is kicking my butt and I\'m t
ID: 3630875 • Letter: S
Question
Stuck on where to start - this Discrete Math class is kicking my butt and I'm taking this to teach middle school math.
Problem: Passwords for a certain computer system are strings of uppercase letters. A valid password must contain an even number of X's. Determine the recurrence relation for the valid number of passwords of length n.
Hint: To build a good code word of length n, you can either
(1) add a Non-X to the end of a good word of length n-1 -or-
(2) add an X to the end of a "not good" code word of length n-1
Explanation / Answer
Let r(n) denotes valid passwords of length n
=>r(n-1) denotes valid passwords of length n-1
Total possible passwords of length n-1 = 26n-1 as there are 26 uppercase letters
=> no. of invalid passwords of length n-1 = 26n-1 - r(n-1)
To get a valid password of length n,two cases are possible
case-1: add non-X to valid password of length n-1,which can be done in 25 ways
Hence 25r(n-1) in this case
case-2: add X to invalid password of length n-1
Hence 26n-1 - r(n-1) in this case which is computed above
Summing above two cases,we get
r(n) = 25r(n-1) + 26n-1 - r(n-1)
=> r(n) = 24r(n-1) + 26n-1
This is the required recurrence relation