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?

  • 1
    $\begingroup$ What you say is correct, absolutely correct for $n>10$. $\endgroup$ – астон вілла олоф мэллбэрг Apr 4 '16 at 3:38
  • $\begingroup$ So would I need to include an expression for $3 < n < 10$ since $3$ is the least number of miles I can travel other than the trivial solution $0$? $\endgroup$ – Jodo1992 Apr 4 '16 at 3:43
  • 1
    $\begingroup$ I suppose. Remember, every recurrence relation has an initial value, right? So yo have to specify the initial conditions, starting from $n=0$ onwards. I can help you. Just think about these conditions, they are obvious to derive: $a_0=a_1=a_2=0,a_3=1,a_4=0,a_5=1,a_6=1,a_7=0,a_8=2,a_9=1$, and from $a_{10}$ on wards you can help yourself $\endgroup$ – астон вілла олоф мэллбэрг Apr 4 '16 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.