Find a recurrence relation for the number of ways to go n miles by fast walking at 2 miles per hour or

Question

A) 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. B) How many ways are there to go 12 miles?

I tried to start the problem with $a_n=a_{n-2}+a_{n-4}+a_{n-8}$ But I don't know if I am on the correct track.

Answer 1

Yup, your recurrence relation is correct but you have to be little cautious here. Since you can go even number of miles at each hour, what should be the answer if i ask you this question: "How many ways are there to go n miles? where n is odd,e.g-n=3". Certainly you can go 2 miles, 4 miles but there is no way you can make exactly 3 miles.You can say, that there is no way to go exactly 3 miles, in that case you an define your recurrence in this way:

$a_0 = 1.$
$a_i =0$, when i is odd or negative integer.
$a_i = a_{i-2} + a_{i-4} + a_{i-8}$ otherwise.

Answer 2

The recurrence relation (seems to me) is correct, but you have to add initial conditions (you can not start recurrence/program from empty air); using notation a(n) instead of your an (easier in HTML) add a(1) = 0.5; a(2) = a(3) = 1; a(4) = 2; // walk or jog etc - you certainly can finish yourself