Question

Find a recurrence relation for the number of ways to go n miles by foot walking at 2 miles per hour or jogging at 4 miles per hour or running at 8 miles per hour; at the end of each hour a choice is made of how to go the next hour. (b) How many ways are there to go 12 miles?

Answer 1

Answer:

(a) $x_{n} = x_{n - 2} + x_{n - 4} + x_{n - 8}$

(b) 18 ways

Solution:

As per the question:

We need to find the no.of ways to go 'n' miles by foot:

From the question it is clear that, at each hours even miles can be traveled by a person, If the distance to be covered is odd, then there in no way 3 miles can be covered.

Thus defining recurrence as:

$x_{o} = 1$

$x_{n} = 0$

where

n: negative or odd

Then

$x_{n} = x_{n - 2} + x_{n - 4} + x_{n - 8}$

(b) No. of ways to travel 12 miles:

$x_{o} = 1$

$x_{2} = 1 + 0 = 1$

$x_{4} = x_{2} + x_{o} + 0 = 1 + 1 = 2$

$x_{6} = x_{4} + x_{2} + 0 = 2 + 1 + 0 = 3$

$x_{8} = x_{6} + x_{4} + 0 = 3 + 2 = 6$

$x_{10} = x_{8} + x_{6} + x_{2} = 6 + 3 + 1 = 10$

$x_{12} = x_{10} + x_{8} + x_{4} = 10 + 6 + 2 = 18$

Thus clearly there are 18 ways to travel 12 miles