SOLUTION: In how many ways can you walk up a stairway that has 7 steps if you can take 1 0r 2 steps at a time?

Question 36496: In how many ways can you walk up a stairway that has 7 steps if you can take 1 0r 2 steps at a time?
Answer by kev82(151) (Show Source): You can put this solution on YOUR website!
Hi,
Are you familiar with reccurence relations? Hopefully you are because I don't know how to attempt this otherwise.
let N(x) be the number of ways to get up x stairs, where you can either take one or two steps at a time. Obviously N(1)=1 because when you have one stair left all you can do is walk up it.
With two stairs left to go, we can go up both stairs at once or we can go up one stair and be on stair 1. So N(2)=1+N(1)=1+1=2.
If there are x stairs left, then we can either go up one stair and be on stair x-1 or we can go up two stairs and be on stair x-2. So N(x)=N(x-1)+N(x-2). We want to know N(7), lets work it out.
N(1)=1
N(2)=N(1)+1=1+1=2
N(3)=N(2)+N(1)=2+1=3
N(4)=N(3)+N(2)=3+2=5
N(5)=N(4)+N(3)=5+3=8
N(6)=N(5)+N(4)=8+5=13
N(7)=N(6)+N(5)=13+8=21
So there's your answer, 21. Hopefully you should recognise this as the Fibbionacci sequence.
Hope that helps,
Kev
RELATED QUESTIONS
In how many ways can you walk up a stairway that has 7 steps if you can take 1 or 2... (answered by Theo)

A staircase has 5 steps. You can walk up the staircase by taking one or two steps at a... (answered by drk,jsmallt9)

a stairway has less than 20 steps. if tony goes up 2 steps at a time, then one step is... (answered by ankor@dixie-net.com)

Find the number of ways in which you can climb 13 steps if you can go up 1 or 2 steps... (answered by Edwin McCravy)

if a cat can climb 1 or 2 steps at a time. in how many ways can she climb a flight of 10... (answered by Theo)

There are 10 steps from ground level to the top. The 6th step is under repair and only... (answered by greenestamps)

These are my questions. I have no clue how to do these. I need to know step by step how... (answered by htmentor)

An escalator in a department store moves down at the rate of sixty-four steps per minute. (answered by ankor@dixie-net.com)

An old house has a basement stairway that has steps with 7.25 inch risers and 10 inch... (answered by josmiceli)