Q.7 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 ๐น(๐) denote the number of possible ways in which Ankita can reach the ๐๐กโ
stair. For example, ๐น(1) = 1, ๐น(2) = 2, ๐น(3) = 3.
The value of ๐น(5) is _______.
(A) 8
(B) 7
(C) 6
(D) 5
F(5) equals 8, making option (A) correct. This classic stairs climbing problem follows a Fibonacci-like recurrence where ways to reach stair N come from reaching N-1 (then +1 step) or N-2 (then +2 steps).
Problem Breakdown
Ankita starts at ground level (stair 0) and climbs to stair 5 using 1 or 2 steps at a time, never descending. Given F(1)=1 (just {1}), F(2)=2 ({1+1}, {2}), and F(3)=3 ({1+1+1}, {1+2}, {2+1}). The recurrence is F(N) = F(N-1) + F(N-2) for N > 2.
Compute step-by-step:
- F(4) = F(3) + F(2) = 3 + 2 = 5
- F(5) = F(4) + F(3) = 5 + 3 = 8
All 8 Ways Listed
The distinct sequences summing to 5 steps are:
Option Analysis
| Option | Value | Correct? | Reason |
|---|---|---|---|
| (A) | 8 | Yes | Matches F(5)=8 from recurrence and enumeration |
| (B) | 7 | No | Underestimates; misses one sequence like 2+2+1 |
| (C) | 6 | No | Common error confusing with other step sizes (e.g., 1/3 steps) |
| (D) | 5 | No | Equals F(4); forgets paths via stair 4 |
Ankitaโs challenge to climb 5 stairs using 1 or 2 steps at a time reveals F(5)=8 ways, a cornerstone of dynamic programming for CSIR NET aspirants mastering stairs climbing problems. This Fibonacci-based puzzle tests recurrence relations: F(N)=F(N-1)+F(N-2), with base cases F(1)=1, F(2)=2.
Why 8 Ways?
From stair 5, last move is either 1 step (from F(4)=5 ways) or 2 steps (from F(3)=3 ways), totaling 8. Explicit paths confirm: five 1โs, or mixes like three 1โs + one 2 (4 permutations), or one 1 + two 2โs (3 permutations).
Exam Tips
Practice builds F(4)=5 first, avoiding traps like counting combinations over permutations. Code it via DP array for verification.
ย
