A lot of programmers have used Fibonacci sequence to solve this problem, i have tested the solutions and they work very well, howver i am interested to know "why Fibonaci is the solution" what is the theory behind?
Why Fibonacci sequence is the solution of this problem ?

I don't have any insight on to how to arrive at the Fibonacci sequence by just looking at the problem statement. However, I only figured out it was the Fibonacci sequence because I wrote all the combinations out for n = 1, 2, 3, 4, 5. I basically used pattern matching to arrive at the solution.


Imagine we are standing on step N.
Now, either we just took one step up (from N1); or we took two steps up (from N2). Those are the only possibilities! Every distinct path to step N corresponds to either a distinct path that ended at N1; or a distinct path that ended at N2.
So we have:
PathsToStep(N) = PathsToStep(N1) + PathsToStep(N2)
Where the degenerate cases are
PathsToStep(0) = 1
because there is only one way to climb zero stairs, and
PathsToStep(1) = 1
because there is only one way to climb one stair. :)

