## Answer: Flight Of Stairs

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 $20^{th}$ stair. You can go up a single step from the $19^{th}$ or go up two steps at once from the $18^{th}$. So the number of ways you can reach step $20$ is the sum of the number of ways you can reach steps $18$ and $19$. 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 $n^{th}$ stair is the $(n-1)^{th}$ 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 $932$ steps going $4,7,$ or $9$ at a time. (This would require a 9X9 matrix).