Passwords for a certain computer system are strings of uppercaseletters. A valid

Passwords for a certain computer system are strings of uppercaseletters. A valid password must contain an even number of Xs.Determine a recurrence relation for the number of valid passwordsof length n. Note: 0 is an even number so ABBC is a validpassword. This counting problem is pretty tricky. Heres a good wayto think about it: to make a good password of length n you caneither (a) add any non-X to the end of a good password of length n- 1 or (b) add an X to the end of a bad password of length n 1.For (b) you can use the Good = Total-Bad trick to count the numberof bad passwords of length n 1. Please present answer with clearexplanation or will not get a good rating.