Permutations & Combinations
Permutation and Combination
star_batch_jee_advanced_2025
Grade 11
Question:
A staircase has 10 steps. A person can go up the steps one at a time, two at a time, or any combination of 1's and 2's. If the number of ways in which the person can go up the stairs is $p$, then find $\frac{p}{89}$
Step-by-Step Solution
Key Concept: The number of ways to reach step $n$ follows the Fibonacci recurrence relation since each position can be reached from exactly two previous positions.
Let $f(n)$ be the number of ways to climb $n$ steps. At step $n$, we can arrive either from step $n-1$ (taking 1 step) or from step $n-2$ (taking 2 steps), giving us the recurrence $f(n) = f(n-1) + f(n-2)$. With base cases $f(1) = 1$ and $f(2) = 2$, this is the Fibonacci sequence. Computing: $f(3)=3, f(4)=5, f(5)=8, f(6)=13, f(7)=21, f(8)=34, f(9)=55, f(10)=89$. Therefore $p = 89$, and $\frac{p}{89} = \frac{89}{89} = 1$.
Correct Answer: 1