We are playing a board game imagine Monopoly or Life or anyt

We are playing a board game (imagine Monopoly or Life or anything similar). Every time you flip a coin, you move forward by 2 if it was heads, and move forward by 1 if it was tails. Set a_n = number of different ways to move forwards by n. Find the recurrence relation for a_n.

Solution

a_n = number of different ways to move forwards by n.

The n^th step can be reached either from (n-1)^th step or from (n-2)^th step.

Thus: number of different ways to move forwards by n = (number of different ways to move forwards by n-1) + (number of different ways to move forwards by n-2)

a_n = a_n-1 + a_n-2