6
$\begingroup$

There is a very interesting puzzle for Fibonacci sequence:

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb $1$ or $2$ steps. In how many distinct ways can you climb to the top?

The answer is Fibonacci sequence: $F(n) = F(n - 1) + F(n - 2)$. The explanation is that you could reach the $n$th step either from the $(n - 1)$th step or $(n - 2)$th step.

What I fail to understand is why isn't the answer $F(n) = (F(n - 1) + 1) + (F(n - 2) + 2)$. Since, after reaching $(n - 1)$th step I have to take $1$ step to reach the $n$th step and after reaching $(n - 2)$th step I have to take another $2$ steps to reach the $n$th step.

I know I might be ignoring some very stupid detail but it's better to ask and be called a fool once than to remain a fool forever.

$\endgroup$
8
$\begingroup$

You're not counting the number of steps involved, just the number of paths. For each path that gets to $n-1$ steps, there is exactly one way to finish the stairs (namely, take the last step). With getting to $n-2$, there is only one way to finish at that point if you insist on taking two steps at once. (If you take one step, you're instead back to the first scenario.) In both scenarios, we don't need to add anything else on: just add the number of paths that get you to $n-1$ and the number that get you to $n-2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.