How to reach $n$th place from starting point using a 6 faced dice.

Question

I just completed some coding competition, and I was asked to solves this:

Imagine you are playing a board game. You roll a $6$-faced dice and move forward the same number of spaces that you rolled. If the finishing point is $n$ spaces away from the starting point, please implement a program that calculates how many possible ways there are to arrive exactly at the finishing point.

Can anyone explain how to solve this with a mathematical algorithm?

Answer 1

Denote by $H(m)$ the number of histories $$(x_1,x_2,\ldots, x_r),\qquad x_i\in[6]\quad (1\leq i\leq r)$$ of arbitrary length $r\geq1$ that sum up to $m$, i.e., $\sum_{i=1}^r x_i=m$. Then $$H(m)=0\quad(m<0),\quad H(0)=1$$ and $$H(m)=\sum_{k=1}^6 H(m-k)\qquad(m\geq1)\ .$$