Add new comment
-
Want facts and want them fast? Our Maths in a minute series explores key mathematical concepts in just a few words.
A basic introduction to the most powerful tools in science and enginnering.
As COP28, the 2023 United Nations Climate Change Conference, kicks off we look at how maths can help understand the climate crisis.
How do you create dramatic film out of mathematics? We find out with writer and director Timothy Lanzone.
Mathematics plays a central role in understanding how infectious diseases spread. This collection of articles looks at some basic concepts in epidemiology to help you understand this fascinating and important field, and set you up for further study.
Find out why the formula we use to work out conditional probabilities is true!
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.