Stepping Stones

Suppose you have a big line of individual stones going down a pond. You start at the left and move towards the right.

There are two moves you can make. You can either move from one adjacent stone to another, or you can hop over one stone and reach the stone after. Count the number of ways you can get to each stone in the diagram, assuming that the there is 1 way to get to the first stone.

• Hint
  Try counting case by case. For example, there is only one way to get to the second stone, but there are two ways to get to the third stone (you can hop from the first, or move once to the second and move once again to the third).
• Solution

  Let's think about how to get to the third stone. You can either hop from two stones before the third stone, or you can move once from the second stone. Since there is one way to get to either, there is a sum total of two ways to get to the third stone.

  Now let's think about the fourth stone. You can either hop from two stones before the fourth stone, or you can move once from the third stone. Since there is one way to get to the second stone, and two ways to get to the third, there is a sum total of 3 ways to get to the fourth stone

  Now let's think about the fifth stone. You can either hop from two stones be...wait a second! You can describe the way to get to any stone recursively!

  Suppose we have f(n) where n is the nth stone you would like to reach. By the above recursive relationship (recurrence relation) we can say that:

  f(n) = f(n - 1) + f(n - 2)

  Look familiar? This is the Fibbonacci sequence!

Home