Here is the problem:

You have n-steps to climb. You can only climb 1 or 2 steps at a time. find the number of ways to reach Nth step.

the solution is described as t(n) = t(n-1) t(n-2).

I keep thinking why not add a constant 2, to represent the final one or two step from t(n-1) and t(n-2)? I having trouble intuitively, why it's not added at each stage?

the problem is the sum of t(n-1) and t(n-2) but I feel like where does it account for taking the one or two step backwards?

since there are two option and you have yet to take the two steps at t(n-1) or t(n-2) shouldn't there be a constant added at each step? How can I conceptualize this?

CodePudding user response：

and you have yet to take the two steps

But you're not counting steps though, you're counting ways. Your final step/jump can be a one or a two. So you add the number of ways that led you to n-1 with the number of ways that led you to n-2. That's your answer.

CodePudding user response：

If you play the video backward, from the step n you move either to step n-1 or to step n-2.

Hence, the number of ways to reach the step n equals the number of ways to reach the step n-1 plus the number of ways to reach to step n-2, as these are distinct ways to reach n. There is no reason to add anything.

If you are still not convinced, let us try a few cases.

With n=1, there is a single way (1).

With n=2, there are 2 ways (1 1, 2)

With n=3, there are 3 ways (1 1 1, 2 1, 1 2)

With n=4, there are 5 ways (1 1 1 1, 1 2 1, 2 1 1, 1 1 2, 2 2)

With n=5, there are 8 ways (1 1 1 1 1, 1 1 2 1, 1 2 1 1, 2 1 1 1, 1 1 1 2, 1 2 2, 2 1 2, 2 2 1)

You should recognize the Fibonacci numbers.