I got this problem from Shelley Chang, who says it’s one of her favorites.

Simple trial and error will allow you to get the number of ways to climb one, two, three, four, and five steps. This turns out to be one, two, three, five, and eight.

That probably looks familiar as the Fibonacci sequence. Fibonacci comes into play here because there are two ways to reach the stair. You can go up a single step from the or go up two steps at once from the . So the number of ways you can reach step is the sum of the number of ways you can reach steps and . Since the first and second steps correspond to the second and third Fibonacci numbers (depending on where you think the Fibonacci numbers start), the number of ways you can reach the stair is the Fibonacci number.

I wrote up a derivation of the formula for this number here.

If you followed the post linked above, it becomes trivial to generalize this question. The maximum number of steps you can take at a time becomes the dimension of the matrix. The matrix has mostly zeroes along the diagonal with ones next to the diagonal, and nothing else until the last row. The last row then has ones in all the columns that correspond to steps you could use to get to the final step. Then by diagonalizing this matrix and exponentiating the eigenvalues, we could find, for example, how many ways there are to get up steps going or at a time. (This would require a 9X9 matrix).

### Like this:

Like Loading...

*Related*

This entry was posted on July 17, 2009 at 5:14 am and is filed under problems and solutions. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply