A certain diner has parallel parking along the street. Being so popular with mot

Question

A certain diner has parallel parking along the street. Being so popular with motorcyclists, the parking spots are marked to accommodate the length of a motorcycle. A car can also park there, and fits just right in two consecutive spots. Let tn denote the number of ways that such a parking strip with n motorcycle spaces can be filled with cars and motorcycles. For example, t3 = 3: (m|m|m), (CCC|m), (m|CCC). Find a recurrence relation (base case(s) and recurrence) for {tn}. (Hint: consider the last vehicle parked in the strip.)

Explanation / Answer

This is a classic example of the fibonacci principle.

Hence the recurrence would would come out to be f(n) = f(n-1) + f(n-2).

And the base cases are f(1) = 1 and f(0) = 1.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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