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.

Question

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.

anonymous · Answer

n0=1,n1=1,n2=2,n3=4,n4=7, do those base cases look correct?

anonymous · Answer

actually, n4=8, does the recurrence relation have anything to do with it being powers of 2?