Find a recurrence relation for the number of ways to go n mi

Find a recurrence relation for the number of ways to go n miles by fast 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.

How many ways are there to go 12 miles?

Solution

Find a recurrence relation for the number of ways to go n miles by fast 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.

How many ways are there to go 12 miles?

Solution :

Walk fast for \'a\' hours
Jog for b hours
Run for c hours

2a + 4b + 8c = 12

Divide by 2 :

a + 2b + 4c = 6

Total number of variables, n = 3
Total sum, S = 6
a,b,c can be 0

So, number of solutions is :

(n + S - 1) Combination (n - 1)

8 C 2

28

So, we have 28 possible ways to go the 12 miles