Question

When climbing a staircase, you can take either one or three stairs in a single step.

(a) Write “Let S_n be the number of ways to climb a staircase with n stairs.” Prove the recurrence relation S_n = S_n-1 + S_n-3.

(b) Write down what S₀, S₁, S₂ are (or alternatively, what S₁, S₂, S₃ are). No justification needed.

(c) Use (a) and (b) to answer the following question. How many ways are there to climb a staircase with 12 stairs?

Answer 1