Add new comment

I too started with your approach Ayaan. Afterall, for n steps, there are n-1 points at which point I might take 2 steps at once. Since I can either take or not take 2 steps at each of the n-1 points, there are 2^n-1 such total possibilities.

Note though that this approach does not give the correct answer because you cannot take 2 steps at two consecutive points.

If we model the points as a binary number, the problem becomes this: in the binary representation of all numbers 0 to 2^(n-1), how many such numbers are formed without adjacent bits set?

For n=2, the binary representations to consider are: 0 1
For n=3, the binary representations to consider are: 00 01 10 11
And for each successive n, we just tack a zero to the left of the previous representations and then a one to the left.
Thus for n= 4, zero-tacking gives 000 001 010 011 and one-tacking gives 100 101 110 111.

Finally zero-tacking means that any representation that did not previously contain two consecutive bits set will again be OK.
But one-tacking means that any previous representation with the high bit set will now contain two consecutive bits.

So

n(I) = n(I-1) + n(I-1) with the high bit zero
but
n(I) with the high bit zero = n(I-1)
so
n(I) = n(I-1) + n(I-2)

This is the Fibonacci solution derived by other posters.