Question

There are ten steps in a staircase and a person has to take those steps. At every step, the person has got a choice of taking one step or two steps or three steps. The number of ways in which a person can take those steps is

• A. $3^{10}$
• B. $3^9$
• C. $3^8$
• D. None of these

Answer 1

The correct option is D None of these

We have,

Let $N_k$ denote the number of ways to climb k stairs in the manner described. (So we’re looking for N₁₀.) Notice that for k ≥ 4 there are $3$ “moves” one can do for your first step: you can climb $1,2$ or $3$ stairs. If you climb $1$ stair then there are Nk−1 ways to finish; if you climb $2$ stairs there are N_k−2 ways to finish; and if you climb 3 stairs there are Nk−3 ways to finish. Thus: N_k = N_k−1 + N_k−2 + N_k−3 Well, it’s pretty easy to see that for the k < 4 we have N₁ = 1, N₂ = 2 and N₃ = 4, so using the above we can calculate N₁₀ using brute force.

$N_4=N_3+N_2+N_1=4+2+1=7$

$N_5=N_4+N_3+N_2=7+4+2=13$

$N_6=N_5+N_4+N_3=13+7+4=24$

$N_7=N_6+N_5+N_4=24+13+7=44$

$N_8=N_7+N_6+N_5=44+24+13=81$

$N_9=N_8+N_7+N_6=81+44+24=149$

$N_{10}=N_9+N_8+N_7=149+81+44=274$

There are 274 ways to climb the stairs.

Hence, this is the answer.