# Why Fibonacci sequence is the solution of this problem ?

• 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?

• 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 N-1); or we took two steps up (from N-2). Those are the only possibilities! Every distinct path to step N corresponds to either a distinct path that ended at N-1; or a distinct path that ended at N-2.

So we have:

``````PathsToStep(N) = PathsToStep(N-1) + PathsToStep(N-2)
``````

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. :)

• @subfallen Ok get it Thank you very much

• @subfallen This helps a lot! thank you!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.