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