## Stepping Stones Puzzle

**Questions:** Given that you can take 1 or 2 steps forward from a given step, what is the total number of ways of reaching the Nth step?

**Solution:** Firstly, let us consider an arbitrary step, *i*. This step can be reached by:

- being on the (
*i*-1)-th step and advancing forward 1 step, OR - being on the (
*i*-2)-th step and advancing forward 2 steps.

If we let ** f** be a function which defines the total number of ways of reaching a given step, we can mathematically express the scenario described above as follows:

In other words, the total number of ways of reaching step *i* is a function of the total number of ways you can reach each of the 2 previous steps. This is, of course, a recurrence relationship describing the **Fibonacci-like sequence**. By their nature, recurrence relationships are amenable to recursive solutions - although it is often more efficient to find a closed-form solution! To solve the above equation recursively one only needs to know the seed values f(1) and f(2). In this case, f(0) is not required, f(1)=1 and f(2) = 2 and for n>2 the above formula can be used. QED

*27 Apr 2008*
*Damien Wintour*
0 comments