Given $3$ different speeds, find a recurrence relation for the number of ways to travel $n$ miles

86 Views Asked by At

You can walk $3$ miles per hour, jog $5$ miles per hour, or run $10$ miles per hour. You go a full hour before you can change pace. At the end of each hour, you make a choice as to whether to walk, jog, or run for the next hour. Find a recurrence relation for the number of ways to travel $n$ miles.

For the sake of notation convenience: $Walk = W$; $Jog = J$; $Run = R$

My thought process is that to travel $n$ miles, either:
$1$: Travel $n-3$ miles and add a $W$, which can be done $1\cdot (n-3)$ ways
$2$: Travel $n-5$ miles and add a $J$, which can be done $1\cdot (n-5)$ ways
$3$: Travel $n-10$ miles and add an $R$, which can be done $1\cdot (n-10)$ ways

So, adding these values I get: $$a_n=a_{n-3}+a_{n-5}+a_{n-10}$$

Is this line of thinking correct, or am I making any logical errors about jogging and running since running is a multiple of jogging?