سوال ۱۱۱ کنکور ارشد علوم کامپیوتر ۱۴۰۳

Let $f(n)$ be the number of ways to climb a staircase of $n$ steps using moves of $1$ or $2$ steps. Classify the climbs by the first move:

• If the first move is $1$ step, the remaining ways equal $f(n-1)$.
• If the first move is $2$ steps, the remaining ways equal $f(n-2)$.

This gives the Fibonacci recurrence

$f(n) = f(n-1) + f(n-2),$

with base cases $f(1) = 1$ (only $1$) and $f(2) = 2$ (either $1{+}1$ or $2$).

Tabulating up to $n = 11$:

Hence $f(11) = 144$, which is option 4.

Exam trick: These are Fibonacci numbers shifted by one index: $f(n) = F_{n+1}$ with $F_1 = F_2 = 1$. The distractors $34$, $55$, $89$ are exactly $f(8)$, $f(9)$, $f(10)$ — off-by-one traps from miscounting the base case or stopping early.