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