Suppose you must climb a flight of n stairs. How many different ways can you climb the stairs if you climb one or two steps at a time? For example, if you are climbing n=4 stairs then you could go 1,1,1,1 or 1,1,2 or 1,2,1 or 2,1,1 or 2,2; so there are five ways to climb the stairs.

  Getting Started

1. Make a table of the number of ways to climb n=1,2,3,... stairs. Continue your table until you start to see patterns.
2. How is the number of ways to climb n stairs related to the number of ways to climb n+1 stairs?

  Going Deeper

Suppose you can climb the stairs either 1, 2 or 3 steps at a time? What if you can only climb 1 or 3 steps but not 2 steps at a time? Consider other combinations.

Communicated by Watertown High School.