Question

Find an appropriate recurrence relation with initial conditions, and solve the recurrence relation.

Find a recurrence relation for the number of ways to arrange cars in a row with n spaces if we can use Cadillacs or Hummers or Fords. A Hummer requires two spaces, whereas a Cadillac or a Ford requires just one space.

Answer 1

SOL)

The recurrence relation will be 2а,-1 + аn-2 an When we have filled the (n-1) spaces, then the last nth space can be filled in 2 ways i.e. by putting a cadillac or a ford, hence the coefficient of 2 exists for a(n-1) When we have filled the (n-2) space, then the last 2 spaces can be filled by a hummer, hence the coefficient is 1 Now, using the initial conditions to solve the equation, F represents Ford, C represents Cadillac and H represents Hummer а — 2, оptions 3 {F,C} а — 5, оptions 3 {FF,CC,СF, FC, H} The characteristic equation will be 22 10 D 2 4ac (-2)2 - 4(1)(-1) = 4+4 = 8 _ 2 2/2 1 2 2 2 2 2 Т2 1 - 2 2 аn — с1 (1 + V2)" + с2(1 — V2)"

using the initial condition now a1 2cc2 + V2(c1 - c2) a2 5 c(3 2/2) c2(3 - 2/2) Hence the value of cl and c2 will be 1 1