let wn be the number of strings of length n using................................

Let W\" be the number of strings of length 11 using A and B which do not contain consecutive B's. (a) Explain why wn satises the recurrence relation wn = wn_1 +wn_2, with we = l,w1 = 2. (b) In what follows, we will obtain the generating function W[x] for WW in a afferent way than our textbook (i.e. rather than attacking the recurnmce relation directly.) Notice that a string of our type can be made by stringing together substrings of the form A and BA, followed by either a B or nothing at the end. 1 l[x+x2))'[1+x) Explain how this observation allows us to conclude that W(x) = ( (c) Noticing that [x + x2)\" can be rewritten using an application of the Binomial Theorem, rewrite the above representation of W(x} in a way that allows us to derive an explicit formula for w\" (i.e. a formula just in terms of n, and in particular, not involving wn_1,wn_2, etc). ((1) Relate our closed-form representation of W(x) in part (b) to relate W[x) to the generating function F[x] for the sequence tn of Fibonnaci numbers (i.e. the sequence of numbers satisfying f\" = fn_1 + fn_2, with to = 1 = . Use this (simple) relationship between W and F to write a closed-form for F[x}