GATE IN 2023 | GA Question: 7

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 $N^{\text {th}}$ 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$

Answer 1

Let's denote $F(N)$ as the number of ways to reach the $N^{\text{th}}$ stair.

• For $N = 1,$ there is only one way$: F(1) = 1.$
• For $N = 2,$ there are two ways$: F(2) = 2. \;($She can either take two $1-$ step moves or one $2-$ step move$.)$
• For $N = 3,$ there are three ways$: F(3) = 3.\; ($She can either take three $1-$ step moves, one $2-$ step move followed by one $1-$ step move, or one $1-$ step move followed by one $2-$ step move$.)$
• For $N = 4,$ there are five ways$: F(4) = 5. \;($She can either take four $1-$ step moves, one $2-$ step move followed by two $1-$ step moves, two $1-$ step moves followed by one $2-$ step move, one $1-$ step moves followed by one $2-$ step move followed by one 1-step or one $2-$ step move followed by one $2-$ step move$.)$

Now, let's calculate $F(5)$ using the previous values:

• $F(5) = F(4) + F(3)$
• $F(5) = 5 + 3$
• $F(5) = 8$

So, the value of $F(5)$ is $8.$ 

Correct Answer: A

$\textbf{PS:}$  Here are the $8$ ways for Ankita to reach the $5^{\text{th}}$ stair:

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 + 1 + 2 + 2$
7. $1 + 2 + 2$
8. $2 + 1 + 2$

These are the $8$ distinct ways Ankita can reach the $5^{\text{th}}$ stair.

$\textbf{Short Method:}$ We can calculate $F(5)$ using the Fibonacci sequence:

1. $F(1) = 1 (1$ way to reach the $1$st stair$).$
2. $F(2) = 2 (2$ ways to reach the $2$nd stair$: 1+1 \;\text{or}\; 2).$
3. $F(3) = 3 (3$ ways to reach the $3$rd stair$: 1+1+1, 1+2, \text{or}\; 2+1).$

Now, for each subsequent step, $F(N) = F(N-1) + F(N-2).$

Calculate $F(4)$ and $F(5)$ using recurrence relation:

• $F(4) = F(3) + F(2) = 3 + 2 = 5$
• $F(5) = F(4) + F(3) = 5 + 3 = 8$