Add new comment
-
Want facts and want them fast? Our Maths in a minute series explores key mathematical concepts in just a few words.
Weird and wonderful things can happen when you set a ball in motion on a billiard table — and the theory of mathematical billiards has recently seen a breakthrough.
Was vaccinating vulnerable people first a good choice? Hindsight allows us to assess this question.
A game you're almost certain to lose...
What are the challenges of communicating from the frontiers of mathematical research, and why should we be doing it?
Celebrate Pi Day with the stars of our podcast, Maths on the move!
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.