How many distinct ways to climb stairs in 1 or 2 steps at a time?

Question

I came across an interesting puzzle:

You are climbing a stair case. It takes $n$ steps to reach to the top. Each time you can either climb $1$ or $2$ steps. In how many distinct ways can you climb to the top?

Is there a closed-form solution to the problem? One can compute it by creating a 'tree' of possibilities of each step. That is, I can either take 1 or 2 steps at each stage and terminate a branch once it sums to $n$. But this is would get really unwieldy very quickly since the maximum number of nodes in a binary tree is $2^{n+1}-1$, i.e., exponential. Is there an easier way to solving this puzzle?

Answer 1

Let $F_n$ be the number of ways to climb $n$ stairs taking only $1$ or $2$ steps. We know that $F_1 = 1$ and $F_2 = 2$. Now, consider $F_n$ for $n\ge 3$. The final step will be of size $1$ or $2$, so $F_n$ = $F_{n-1} + F_{n-2}$. This is the Fibonacci recurrence.

Answer 2

This is the Fibonacci numbers - One interpretation of the n-th Fibonacci number is the number of ways to compose $n$ with parts in $\{1,2\}$ (that is, the n-th fibonacci number counts the number of sequences whose values are in $\{1,2\}$ whose sums are $n$). This is often called "Golfs and Cadillacs" or something similar.

Answer 3

The solution to this problem indeed corresponds to the Fibonacci numbers, as mentioned by @fahrbach.

Here is an illustration of what you are trying to solve for the case of $n=4$ steps (taken from this website, which also gives a combinatorial solution)

Any staircase with $n$ steps allowing paths with increments of 1 or 2 steps at a time will end up in one of two states before the last path is taken: either we've climbed $(n-1)$ steps already and have $\color{red}{one}$ more step to take, or we've climbed $(n-2)$ steps already and we have $\color{blue}{two}$ more steps to take (if we took only one step here then we'd end up in an arrangement from the first state).

Thus, to get the total number of possible ways to climb $n$ steps, we just add the number of possible ways we can climb $(n-1)$ steps and the number of possible ways we can climb $(n-2)$ steps, giving the familiar recurrence relation:

\begin{equation*} F_n = \left\{ \begin{array}{l@{}l@{}l} 1 & n = 0,1\\ \color{red}{F_{n-1}} + \color{blue}{F_{n-2}} & n \ge 2 \end{array} \right. \end{equation*}