# How to find the number of possible ways to climb the staircase [closed]

You are going to climb up a staircase that has an n number of stairs, starting from bottom. In each step, you can only move up either one or two stairs.

Note that, as an example, after reaching the 3rd or 4th stairs, you can climb up to the 5th stair in 2 ways;

 I. move up 1 stair from the 4th stair, and

II. move up 2 stairs from the 3rd stair.


Develop a Python program to take an integer n as input (0 < n < 120) and display the number of ways you can climb up to the nth stair. You may handle unexpected inputs appropriately.

Input: Single integer n (0

Output: Single integer

Example:

Case 1:

Input:

5 Output:

8 Case 2:

Input:

9 Output:

55

Above is a question from one of my computer assignments. I don’t understand how to calculate the number of possible ways. To start coding I need a solution to the problem. How do I find the number of possible ways to climb the staircase.

## closed as off-topic by Henrik, Namaste, Sahiba Arora, Fabio Somenzi, DidFeb 5 '18 at 22:14

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Henrik, Sahiba Arora, Fabio Somenzi, Did
If this question can be reworded to fit the rules in the help center, please edit the question.

• This is just the sequence of Fibonacci numbers. – Saad Feb 5 '18 at 12:48
• The sequence goes $1,2,3,...$, the $n$th number is the $(n+1)$th Fibonacci number. – user_194421 Feb 5 '18 at 12:53

Say input$=1$, in this case output$=1$.

Now say input$=2$, in this case there is the answer of $($input$=1)$ and then another step and we have also the answer of taking $2$ steps(so $2$)

Now take input$=n$ in this case we have that output is: $($output$=n-1)$ with step of $1$ at the end and $($output$=n-2)$ with step of $2$ at the end

This is the same as the $n+1$ Fibonacci number

To make it clearer:

If I want to climb $10$ stairs. In this case I can climb $9$ and then climb a single stairs and I can also climb $8$ and then climb 2 stairs. So the number of ways to get to $10$ is the number of ways to get to $9$ plus the number of ways to get to $8$. And this is the same for all $n>2$.

• Can you please explain further – ulama Feb 5 '18 at 13:57
• @ulama if I have 10 stairs, I can go up $1$ stair and then I have $9$ stairs left. I can also go up $2$ stairs at the start, and then I have $8$ stairs left. So in the end I have the number of ways to go up $9$ stairs+the number of ways to go up $8$ stairs. And in general change $10$ into $n$, $9$ into $n-1$ and $8$ into $n-2$ – Holo Feb 5 '18 at 14:02
• I’m really sorry to keep bothering but I still don’t see the Fibonacci sequence – ulama Feb 5 '18 at 14:05
• @ulama there is no problem. Do you understand why the number of ways to get to $10$ is the number of ways to get to $9$+ the number of ways to get to $8$? – Holo Feb 5 '18 at 14:11
• Yeah, because the last step could be 1 step up or 2 steps up. – ulama Feb 5 '18 at 14:28