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
|
|
|
