Derive a recurrence relation for the numbers

Reference no: EM13975427

Problem:

Let Wn be the number of strings of length n formed from letters A, B, C, and D that do notncontain a substring AA, BA or CA.

For example, for n = 2, all the strings with this property are AB, AC, AD, BB, BC, BD, CB, CC, CD, DA, DB, DC, DD and thus W₂ = 13. (Note that W₀ = 1, because the empty string satisfies the condition.)

(a) Derive a recurrence relation for the numbers Wn. Justify it.

(b) Find the formula for the numbers Wn by solving this recurrence. Show your work.

Reference no: EM13975427

Questions Cloud

What is the nash equilibrium : What is the Nash equilibrium if 0 , What is the Nash equilibrium if 0 a + c1?

What is the cost to contractors based on cost : Front range cabinet distributors in colorado springs, colorado, sells to its contractors with a 42% markup on cost. if the selling price for cabinets is $9,655, what is the cost to contractors based on cost?

Prepare the relative frequency column : Containers of yogurt were inspected with regard to the number of days until they expire. 0 represents a yogurt container with today's date. The following table gives the frequency distribution of the number of day's expiry date. Prepare the relati..

Too many dollars chasing too few goods : Which of the following is not an accurate description of what can cause inflation? a. too many dollars chasing too few goods. b. an increase in labor costs when productivity is not increasing.

Derive a recurrence relation for the numbers : Derive a recurrence relation for the numbers Wn. Justify it and find the formula for the numbers Wn by solving this recurrence.

Sending arrays of unsorted numbers to the server : The clients should send requests to the server only in the form of Remote Procedure Calls. Sockets cannot be used for this assignment.

Find the net torque on the wheel : Find the net torque on the wheel in the figure below about the axle through O, taking a = 11.0 cm and b = 27.0 cm. (Assume that the positive direction is counterclockwise.)

Differentiating the equation with respect to pa : How would I go about differentiating the following equation with respect to PA?

Find the percentage of the total work lost to friction : Find the percentage of the total work lost to friction if 26.9 J of work is put into pushing a block up a ramp resulting in 16.5 J of stored potential energy at the top.

User Account

All Pages