Question 255273: A staircase has 5 steps. You can walk up the staircase by taking one or two steps at a time. How many different ways can you walk up the staircase?
Found 2 solutions by drk, jsmallt9:
Answer by drk(1908)   (Show Source):
You can put this solution on YOUR website! we have
1,1,1,1,1
1,1,1,2
1,1,2,1
1,2,1,1
2,1,1,1
1,2,2
2,1,2
2,2,1
so, it appears we have 8 ways
Answer by jsmallt9(3758) (Show Source):
You can put this solution on YOUR website! I don't think there is a clever way to do this problem. We just have to count the ways to scale the staircase. We can use a tree diagram to make this a bit easier. As we build the tree we must make sure that the total number of steps on a path never goes above 5. (This is why there are not always two possibilities at each point and why some branches are longer than others.)
Start
/ \
/ \
/ \
/ \
/ \
1 2
/ \ / \
/ \ / \
/ \ / \
1 2 1 2
/ \ |\ |\ \
/ \ | \ | \ \
/ \ | \ | \ \
1 2 1 2 1 2 1
/ \ | | |
/ \ | | |
/ \ | | |
1 2 1 1 1
/
/
/
1
Each of these paths represent one way to scale the staircase. The numbers on each path are the number of steps taken at each point. So we can count the ways of scaling the staircase by counting the ends of the paths. There are 8 ways to scale the staircase:
1-1-1-1-1
1-1-1-2
1-1-2-1
1-2-1-1
1-2-2
2-1-1-1
2-1-2
2-2-1
|
|
|
