Every time I come home I have to climb a flight of stairs. When I'm feeling energetic I sometimes take two steps at a time. This gives me a number of ways to climb the stairs. For example, if there are ten steps, I could climb them taking five leaps of two, giving the pattern
2, 2, 2, 2, 2.
Or I could only use a leap of two at the beginning and the end, giving the pattern
2, 1, 1, 1, 1, 1, 1, 2.
How many ways are there all together of climbing the ten steps?
Being a mathematician, I don't have ten steps of course, but I have $n$ steps. Can you find a formula to express the number of ways there are of climbing $n$ steps using leaps of one and two?Hint: Think recurrently! I could start my climb with a leap of one or two...
Solution link
I've got a recursive formula
S(1)=1
S(n)=1+S(n-1)+S(n-2)+S(n-3)+...+S(1)
Fibonacci !
To reach n, i should first reach n-2 or n-1; and to reach n-2, i should reach n-3 or n-2.
Considering this, i will get:
F(n) = F(n-1)+F(n-2)
F(n-1) = F(n-2)+F(n-3)
...
F(2)=2
F(1)=1
This means to reach the n-th step, the number of ways is a Fibonacci number F(n).
Fibonacci !
To reach n, i should first reach n-2 or n-1; and to reach n-2, i should reach n-3 or n-2.
Considering this, i will get:
F(n) = F(n-1)+F(n-2)
F(n-1) = F(n-2)+F(n-3)
...
F(2)=2
F(1)=1
This means to reach the n-th step, the number of ways is a Fibonacci number F(n).
By the way, F(10) = 89.
BINARY
When I first attempted this puzzle I tried finding a pattern in the possible ways of going up a smaller no. of steps. I used the binary system to find all the possible ways . Finally I got the formula: 2 to the power of n! Then I did 2 to the power of 10 (the no. of steps) and got 1024 (no. of ways to go up 10 steps). Then I checked the solution and found mine was wrong!! I don't understand what I did wrong!? Can somebody please explain??
Fibonnaci Redux
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.
Math
[(n-0)! /(n-2×0)!]÷0! + [(n-1)!/(n-2×1)!]÷1! +[(n-2)!/(n-2×2)!]÷2! + ....................+ [(n-(n÷2))!/(n-n)!]÷(n÷2)!
Does this count?
I got a sigma notation expression:
5
Σ nCr(10-n, n)
n=0
In this case, n denotes the number of leaps of 2 steps, which leaves the number of single step to be (10-2n), and the total number of steps to be (10-2n)+n=10-n, among which there are n two-step leaps, and the number of different arrangements of such steps being nCr(10-n, n). Adding together the different number of ways this can be done (ranging from no two-step leaps to a max of 5 two-step leaps for a 10-step staircase) should give the answer.