Finding recurrence relation

  • Thread starter r0bHadz
  • Start date
  • #1
r0bHadz
194
17

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?
 
Last edited:

Answers and Replies

  • #2
r0bHadz
194
17
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.
 
  • #3
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
24,041
15,743
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!
 
  • #4
r0bHadz
194
17
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
 
  • #5
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
24,041
15,743

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.
 
  • #6
r0bHadz
194
17
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.
 

Suggested for: Finding recurrence relation

Replies
8
Views
376
  • Last Post
Replies
2
Views
1K
Replies
20
Views
692
Replies
2
Views
1K
Replies
10
Views
178
Replies
2
Views
138
Replies
6
Views
385
Replies
19
Views
625
  • Last Post
Replies
10
Views
511
Top