Question

Ankita has to climb 5 stairs starting at the ground, while respecting the following rules: 1. At any stage, Ankita can move either one or two stairs up. 2. At any stage, Ankita cannot move to a lower step. Let F(N) denote the number of possible ways in which Ankita can reach the Nth stair. For example, F(1) = 1, F(2) = 2, F(3) = 3. The value of F(5) is ..................

• A. 8
• B. 7
• C. 6
• D. 5

Hint:

Problems asking for the "number of ways" to reach a certain state, where each move is a choice from a small set of options (like moving 1 or 2 steps), can often be solved with a recurrence relation. Start by calculating the first few terms manually to find the pattern.

Answer 1

The Correct Option is A

Step 1: Understanding the Concept:
This is a classic dynamic programming or recurrence relation problem. The number of ways to reach a particular stair depends on the number of ways to reach the previous stairs from which it is accessible.
Step 2: Key Formula or Approach:
To reach the Nth stair, Ankita must have come from either the (N-1)th stair (by taking a single step) or the (N-2)th stair (by taking a two-step jump). Therefore, the total number of ways to reach the Nth stair is the sum of the ways to reach the (N-1)th and (N-2)th stairs.
The recurrence relation is: \( F(N) = F(N-1) + F(N-2) \).
This is a Fibonacci-like sequence.
Step 3: Detailed Calculation:
We are given the base cases (or initial values) from the example:
F(1) = 1. (The only way is a single 1-step move: 1)
F(2) = 2. (Two ways: 1+1 or 2)
F(3) = 3. (Three ways: 1+1+1, 1+2, or 2+1)
Let's verify our recurrence relation with the given F(3):
F(3) = F(2) + F(1) = 2 + 1 = 3. This matches the example, so the recurrence relation is correct.
Now, we can calculate F(4) and F(5):
F(4):
\( F(4) = F(3) + F(2) \)
\( F(4) = 3 + 2 = 5 \)
(The 5 ways are: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)
F(5):
\( F(5) = F(4) + F(3) \)
\( F(5) = 5 + 3 = 8 \)
Let's list the 8 ways to reach the 5th stair to be sure:
1. 1+1+1+1+1
2. 1+1+1+2
3. 1+1+2+1
4. 1+2+1+1
5. 2+1+1+1
6. 1+2+2
7. 2+1+2
8. 2+2+1
Step 4: Final Answer:
The value of F(5) is 8.
Step 5: Why This is Correct:
The calculation correctly uses the identified recurrence relation \(F(N) = F(N-1) + F(N-2)\) with the given initial conditions to compute the value for N=5.