UNO High School Problem of the Week Competition
Problem 1
In how many ways can you walk up a stairway with six steps if you can take one o
r two steps at a time?
Example: For a stairway with 3 steps there are three possible ways:
1) Take three single steps
2) Take one step then two steps
3) Take two steps and then one step
Solution
Since we could only take one or two steps while walking up the stairway, we must have either stepped on step number 4 or step number 5 to reach the sixth step. If the stairway had n steps, we would have had to step on either step (n-1) or (n-2) to reach the nth step. Let a(n) be the number of ways that we could walk up a stairway with n steps if we could take one or two steps at a time. Observe that since we must either step on the n-1 step or n-2 step to reach the nth step, we can write a(n) = a(n-1) + a(n-2).
We can now find the number of ways to walk up a stairway with six steps using this recursive formula.
We know that a(1) = 1, a(2) = 2.
a(3) = a(2) + a(1) = 3
a(4) = a(3) + a(2) = 5
a(5) = a(4) + a(3) = 8
a(6) = a(5) + a(4) = 13
This recursive formula actually defines the Fibonacci numbers!