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

In summary, Homework Statement: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 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."

## 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:
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.

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!

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

PeroK said:
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

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.

PeroK said:

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

PeroK

## 1. What is a recurrence relation?

A recurrence relation is a mathematical equation that describes a sequence of numbers or objects by relating each term to one or more previous terms. It is often used to find the value of a term in a sequence without having to explicitly list all the terms.

## 2. Why is finding a recurrence relation important?

Finding a recurrence relation is important because it allows us to understand and predict the behavior of a sequence or pattern. It also helps us to solve problems more efficiently by avoiding the need to explicitly list out all the terms in a sequence.

## 3. How do you find a recurrence relation?

To find a recurrence relation, you need to first identify the pattern or relationship between the terms in a sequence. This can be done by looking at the differences between terms, the ratio between terms, or any other patterns that may exist. Once the pattern is identified, it can be expressed as a mathematical equation.

## 4. What are some common methods for finding recurrence relations?

Some common methods for finding recurrence relations include the method of differences, the method of generating functions, and the method of substitution. These methods involve identifying patterns and using algebraic techniques to derive a recurrence relation.

## 5. How can recurrence relations be applied in real-world situations?

Recurrence relations have many applications in various fields such as computer science, engineering, and finance. They can be used to model and predict the growth of populations, the behavior of algorithms, and the value of financial investments over time. They also have applications in physics, chemistry, and other scientific fields to describe natural phenomena and processes.

• Precalculus Mathematics Homework Help
Replies
2
Views
2K
• Calculus and Beyond Homework Help
Replies
3
Views
1K
• Introductory Physics Homework Help
Replies
9
Views
7K
• Precalculus Mathematics Homework Help
Replies
2
Views
2K
• Introductory Physics Homework Help
Replies
2
Views
8K
• Precalculus Mathematics Homework Help
Replies
3
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
1K
• Calculus and Beyond Homework Help
Replies
11
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
18
Views
2K
• Precalculus Mathematics Homework Help
Replies
5
Views
2K