GATE 2023 IN GA Q.7: solution and answer

GATE 2023 · INGA Q.7 · 2 marks · MCQ

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 $N^{t h}$ 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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$F (5) = 8$ , which is option (A).

Official answer: ASource: Official answer key, GATE 2023 IN (IIT Kanpur)

Condition on the last move. Ankita can never move down, and each move goes up by 1 or 2 stairs, so every way of reaching stair $N$ ends with exactly one of two moves: a 1-stair step from stair $N - 1$ or a 2-stair step from stair $N - 2$ .
Every way ends in one of these two moves, so the two cases cover all ways. They also do not overlap, because a way ending in a 1-stair step cannot also end in a 2-stair step. The ways that end with a 1-stair step are exactly the ways of reaching stair $N - 1$ , and there are $F (N - 1)$ of them. Likewise $F (N - 2)$ ways end with a 2-stair step. The addition rule for disjoint cases gives $F (N) = F (N - 1) + F (N - 2)$ This is the Fibonacci recurrence.
Check it against the given values: $F (3) = F (2) + F (1) = 2 + 1 = 3$ . This matches the question.
$F (4) = F (3) + F (2) = 3 + 2 = 5$
$F (5) = F (4) + F (3) = 5 + 3 = 8$
Direct check by counting 2-stair steps. With $k$ two-stair steps, Ankita needs $5 - 2 k$ one-stair steps, which makes $5 - k$ moves in total. Choosing which $k$ of those moves are 2-stair steps gives $(k 5 - k)$ orderings, where $k = 0, 1, 2$ . So $(0 5) + (1 4) + (2 3) = 1 + 4 + 3 = 8$
$F (5) = 8$ , which is option (A).

KEY IDEA

Look at the last move. The final move onto stair $N$ is either a 1-stair step from $N - 1$ or a 2-stair step from $N - 2$ . Those two cases are disjoint and cover every way, so $F (N) = F (N - 1) + F (N - 2)$ , the Fibonacci recurrence. Starting from $F (1) = 1$ and $F (2) = 2$ , the values run 1, 2, 3, 5, 8.

WATCH OUT FOR

One common mistake is to count only the combinations of step sizes (all 1s; three 1s and one 2; one 1 and two 2s), which gives 3, instead of counting orderings. For example, 1+2+2, 2+1+2 and 2+2+1 are three different ways. Another is to use the standard Fibonacci sequence 1, 1, 2, 3, 5 and pick 5, option (D). The question's own values $F (1) = 1$ , $F (2) = 2$ shift the sequence by one place, so $F (5) = 8$ .

From the GATE 2023 IN paper. Every question of this paper · Download the full paper · All 58 Numerical questions, with notes

GATE 2023 IN GA Q.7: solution and answer

Answer and solution

More Numerical questions