You are climbing a stair case. it takes n steps to reach to the top. each time you can either climb 1 or 2 steps. in how many distinct ways can you climb to the top?
Answers
Answered by
0
The solution to this problem indeed corresponds to the Fibonacci numbers, as mentioned by @fahrbach.
Here is an illustration of what you are trying to solve for the case of n=4n=4steps (taken from this website, which also gives a combinatorial solution)

Any staircase with nn steps allowing paths with increments of 1 or 2 steps at a time will end up in one of two states before the last path is taken: either we've climbed (n−1)(n−1) steps already and have oneonemore step to take, or we've climbed (n−2)(n−2) steps already and we have twotwomore steps to take (if we took only one step here then we'd end up in an arrangement from the first state).

Thus, to get the total number of possible ways to climb nn steps, we just add the number of possible ways we can climb (n−1)(n−1) steps and the number of possible ways we can climb (n−2)(n−2)steps, giving the familiar recurrence relation:
Fn={1Fn−1+Fn−2n=0,1n≥2
Here is an illustration of what you are trying to solve for the case of n=4n=4steps (taken from this website, which also gives a combinatorial solution)

Any staircase with nn steps allowing paths with increments of 1 or 2 steps at a time will end up in one of two states before the last path is taken: either we've climbed (n−1)(n−1) steps already and have oneonemore step to take, or we've climbed (n−2)(n−2) steps already and we have twotwomore steps to take (if we took only one step here then we'd end up in an arrangement from the first state).

Thus, to get the total number of possible ways to climb nn steps, we just add the number of possible ways we can climb (n−1)(n−1) steps and the number of possible ways we can climb (n−2)(n−2)steps, giving the familiar recurrence relation:
Fn={1Fn−1+Fn−2n=0,1n≥2
Similar questions