Recurrence Relations · Recursive Definitions

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Problem. Let \(S(n)\) be the number of ways to climb \(n\) steps, where each move is either a step to the next step or a jump skipping one step. For example, \(S(4) = 5\):

  1. Step, step, step, step
  2. Jump, jump
  3. Jump, step, step
  4. Step, jump, step
  5. Step, step, jump
Find \(S(10)\).

5 points