A password generator works by arbitrarily stringing together words from the following dictionary: apple, pear, orange, banana.

A password generator works by arbitrarily stringing together words from the following dictionary: apple, pear, orange, banana. More precisely, the password generator starts with the empty string, and repeats the following one or more times: it selects a random word from the dictionary and adds it to the left of the string it already has. No spaces or other separators are inserted between words. For example, bananabananapear is one of the passwords generated. Let an be the number of possible outputs of this password generator with length n.

(a) Find the values an for n = 0, 1, 2, 3 and explain. -ANSWERED

(b) Evaluate a4, a5, a6, a7 and explain. -ANSWERED

(c) Explain a8 = 1, a9 = 2, a10 = 5, a11 = 4. -ANSWERED

(d) For n ≥ 10, an satisfies the recurrence an = an−4 + an−5 + 2an−6 Explain the recurrence relation. Is there a danger of double counting?

(e) Find the characteristic equation of the recurrence relation. (f) Use a CAS like Wolfram Alpha to find the characteristic values. All real coefficients may be rounded to 5 digits. (Some solutions are real, some are imaginary.)

(g) When some of the characteristic values are complex, then the general solution of the recurrence is also complex, i.e. the coefficients are generally complex numbers. However, if the sequence is all realvalued, then the coefficients associated with the real characteristic values are also real, and the coefficients associated with the complex conjugate imaginary characteristic values are complex conjugates of each other. This rule is illustrated by Webwork Unit 15 Linear Recurrence, Problem 9. Use this information and the rounded characteristic values from the previous part to give an approximation of the general solution of the recurrence relation. Your answer must contain exactly 6 arbitrary real coefficients A, B, C, D, E, F.

Thanks!