0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – user851954
    Commented Nov 24, 2020 at 18:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .