What is the recurrence relation for climbing stairs with 1 or 2 steps at a time?

[r0bHadz]

Homework Statement

I'm suppose to find the # of ways to climb n stairs if a person can take 1 stair or 2 stairs at a time. The question is:

"
Find a recurrence relation for the number of ways to
climb n stairs if the person climbing the stairs can take
one stair or two stairs at a time."

Homework Equations

The Attempt at a Solution

I'm just confused as to why a_0 = 1. This makes no sense to me.

If there are 0 stairs to climb, I don't consider the action of "do nothing" to fulfill "the # of ways to climb n stairs"

Can anyone break this down for me logically?

 

[r0bHadz]

The previous question I did was:

"
Find a recurrence relation for the number of bit strings
of length n that do not contain three consecutive 0s."

a_0 = 1 makes sense to me here. There is one string of length 0 that does not contain three consecutive zeros, namely, the string of length 0. The problem in my first post though, I just can't make sense of how there can be a way to climb zero stairs.

 

[PeroK]

The previous question I did was:

"
Find a recurrence relation for the number of bit strings
of length n that do not contain three consecutive 0s."

a_0 = 1 makes sense to me here. There is one string of length 0 that does not contain three consecutive zeros, namely, the string of length 0. The problem in my first post though, I just can't make sense of how there can be a way to climb zero stairs.

This is sort of equivalent to defining $0! = 1$. You could leave $a_0$ undefined. But, if you define $a_0 = 1$, then it gives you more flexibility in your formulas.

In this case, however, I would have started with $a_1$.

There's one example, however, which shows the importance of this sort of idea. If you have two types of drink, water and juice, say, and a group of people. Each person gets to choose what drinks they want. You then separate the group according to what they chose.

You have 1 subgroup of people who chose both drinks.

You have 2 subgroups of people who chose one drink: a "water" subgroup and a "juice" subgroup.

You have 1 subgroup of people who chose neither drink.

In this case, there definitely is (precisely) one way to choose 0 drinks!

So, I suppose, if you extend this to climbing stairs. For any number of stairs, you separate people into the way they climbed them. If there are no stairs, then you can't split the group, meaning that there is, perhaps, precisely one way to climb no stairs!

 

[r0bHadz]

You see, PeroK, your example with the drinks makes sense to me. For some reason it is still not clicking in the context of stairs though. I don't really know how to explain my doubt,.. but I have a doubt.

There will be a group that chooses neither drink, but that's with the given that a drink is offered in the first place. In this stair problem, a_0 to me implies that there isn't even a context where you can create subgroups.

That was probability an awful way to express my doubt, sadly I think I'm going to have to go to my professor for this one, as I doubt I can properly express it through online.

I do get the point you're trying to make though, I just don't see it for this problem

In this case, however, I would have started with a1

This is what I feel most comfortable doing. The relation is the fibbonacci numbers, but I feel most comfortable Ignoring a_0, calculating a_1, a_2, a_3 manually, and going from there. I'm sure any reasonable prof would not deduct points for this, but the book has the answer a_0 = 1, and I just get bothered when my solution is not aligned with the books -_-

cheers mate

 

[PeroK]

You deleted your comment something like "there's no context in this case". I'd agree with that. That's why this problem is perfectly solvable without considering $a_0$. Just start at $a_1$. I wouldn't get hung up about this.

You could, however, look at it this way: a group of people first pick a random number between 0-5, say. They are then given 0-5 stairs to climb and the group is separated into the number of stairs they got and the way they climbed them.

In this case, the subgroup that picked 0 stairs is a single group. Logically, they all climbed the 0 stairs the same way.

 

[r0bHadz]

I wouldn't get hung up about this.

Yeah writing this was a waste of time -_-. I need to stop doing this. Thanks a lot though.