PLEASE SHOW WORK. I AM TRYING TO LEARN. STEP-BY-STEP FOR MAX POINTS. Passwords f

Question

PLEASE SHOW WORK.  I AM TRYING TO LEARN.  STEP-BY-STEP FOR MAX POINTS.

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.

Note: 0 is an even number, so ABBC is a valid password.

This counting problem is pretty tricky.

Here's a good way to think about it: to make a good password of length n you can either

(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 number of bad passwords of length n - 1.

Explanation / Answer

As you might guess, the hint is key to the answer.

There are 26^n "words" of length n.

Let there be xn valid words of length n. Then, there are 26^n - xn invalid word of length n.

Then, 25 non-xs in position n+1 combine with the invalid 2^n - xn words of length n, and an x in position combines with the xn valid words of length n.

Thus, xn+1 = 25 * (26^n - xn) + 1*xn = 25*26^n - 25xn + xn = 25*26^n - 24xn

Then, the recurrence is defined as

x1 = 25

xn+1 = 25*26^n - 24xn

As x0 is tricky, we might want to verify that we could start with x0 = 0

Then, x1 = 25*26^0 - 24 * 0 = 25*1 - 0 = 25

We can show, from this recurrence relationship, that xn=1/2*26^n -1/2*(-24)^n

To prove this,

x1 = 1/2*26^1 - 1/2*(-24)^-1 = 13 + 12 = 25

Assume for xn, xn=1/2*26^n -1/2*(-24)^n

For n+1, xn+1 = 25*26^n - 24xn = substituting from the assumption,

25*26^n - 24*(1/2*26^n -1/2*(-24)^n) =

25*26^n - 12*26^n + 12*(-24)^n =

13*26^n + 12*(-24)^n =

13*26/26*26^n + 12 *-24/-24*(-24)^n =

13/26*26^(n+1) -12/24*-24^(n+1) =

1/2*26^(n+1) - 1/2*(-24)^(n+1)

This is what we were trying to show for n+1, so the proof is complete.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.