# Inferring a recurrence relation, stairway climbing

Problem. Suppose a dog can jump one or two steps of a stairway of $$k$$ steps. How many different ways can this dog climb up? Answer it with a recurrence relation.

Solution. I calculated the number of ways for the first step $$n_1 = 1$$, and also for second $$n_2 = 2$$ and third step $$n_3 = 3$$. From the pattern, I'm inferring that $$n_k = n_{k-1} + n_{k-2}$$ and so it seems to be a Fibonacci sequence with the first element chopped off --- 1, 1, 2, 3, ... But I don't consider this a solution because I'm sort of guessing. What is the reasoning that I could apply here to naturally build this recurrence relation? How should I think of this to be able to infer it myself? Must I always guess and prove things by induction?

How did dog get to step $$k$$? From either step $$k-1$$ or step $$k-2$$.
Can it get to stair number $$k - 1$$ the same way as to $$k-2$$? No, as it can't get to different steps the same way:)
So, number of ways to get to the step $$k$$ is sum of number of ways to get to steps $$k - 1$$ and $$k - 2$$. Or, in formula, $$n_k = n_{k - 1} + n_{k - 2}$$.
• That was great! Very intuitive. From which steps can it get to step $k$? That was the important question to ask. We end up with addition because we have two different ways to get to step $k$. Marvelous. Thanks! Commented Nov 24, 2020 at 18:51