Today I was drilling exercises on LeetCode and stumbled on this problem:
You are climbing a staircase. It takes \(n\) steps to reach the top.
Each time you can either climb \(1\) or \(2\) steps. In how many distinct ways can you climb to the top?
If you’ve taken a probability class before, you might recognize that this is a combinatorics problem. I immediately started thinking of how you could count the number of distinct ways to climb this \(n\)-step staircase. It is not just a simple combination \( {n \choose k}\) because the total number of “climbs” varies on how many times you skip a step (i.e., climb \(2\) steps).
After recognizing this, I started to make some trees to illustrate all the different ways you could climb the staircase.
Of course, if the staircase has only a single step, there’s just one way to climb up: take one step, which I could represent with \(S_1 = \{1\}\).
A \(2\)-step staircase is also pretty straight forward. I can either take two single steps or one double step. I could represent this by writing \(S_2 = \{ (1, 1), (2) \}\).
For \(n = 3\), we get \(S_3 = \{(1, 1, 1), (2, 1), (1, 2)\}\), and for \(n = 4\) we have \(S_4 = \{(1, 1, 1, 1), (2, 1, 1), (1, 2, 1), (1, 1, 2), (2, 2)\}\). And of course, writing out every possible combination of steps starts to get a little obnoxious beyond this point. But I wrote everything out through \(n = 6\) and started to notice a familiar pattern emerging.
“It’s just Fibonacci?”
We often denote the cardinality of a set with \( \vert \cdot \vert \), which is the number of elements in the set. The cardinalities of the sets I described above are \( \vert S_1 \vert = 1, \vert S_2 \vert = 2, \vert S_3 \vert = 3, \) and \( \vert S_4 \vert = 5\). I found that \( S_5 = 8 \) and \( S_6 = 13 \). Maybe you’re starting to pick up on what’s going on here!
In general, \(\vert S_n \vert\) is the \( (n + 1) \)-th term of the Fibonacci sequence, denoted \(F_{n + 1}\). The \(n\)th term of the famous Fibonacci sequence is given by
\[ F_n = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F_{n - 1} + F_{n - 2} & n > 1 \end{cases}.\]
When I coded up a three line solution to return \(F_{n + 1}\), submitted it, and saw that I had the right answer, I was gobsmacked! To no one (but my cats), I bellowed “it’s just Fibonacci?”
The Fibonacci sequence frequently turns up throughout nature, disciplines, and industry, but it was still pretty shocking (and really, really fun) to just run into it like this. Naturally, my next question was why?
An Alternative Formulation for \(\mathbf{F_n}\)
In mathematics, there are often many distinct ways to express the same idea. For the Fibonacci sequence, the definition above is probably the easiest to understand, but as you might imagine, there are other creative and interesting ways to formulate the sequence.
I think the formulation that best explains what’s going on in this particular instance with the staircase is one that uses sums of combinations \({n \choose k}\).
First, what number represents the most double steps you could take to climb an \(n\)-step staircase? Well, when \(n\) is even, it’s just \(n / 2\) double steps. But when it’s odd, it’s \((n - 1) / 2\) steps. We can use the floor function, \( \lfloor \cdot \rfloor\), to make this easier to write down: the maximum number of double steps you can take on an \(n\)-step staircase is \(\lfloor n/2 \rfloor\) steps. The floor function takes a real number and returns only the integer part. For example, \(\lfloor 5.9 \rfloor = 5\).
Now, remember how I mentioned at the beginning that this is a combinatorics problem? And that it’s not a straight forward one because the number of distinct climbs varies based on how many double steps you take? Let’s think about that a little more.
Since the maximum number of double steps we can take is \(\lfloor n / 2 \rfloor\), then it might seem like a reasonable approach to try counting how many distinct climbs there are for each \(i \in \{0, 1, 2, \ldots, \lfloor n/2 \rfloor \}\) double steps and then add all of those together to get the total number of distinct climbs.
Brief Review of Combinations
A combination, denoted by \({n \choose k}\) and where we say “\(n \text{ choose } k\)”, is a way to compute how many ways there are to choose \(k\) objects out of a set of \(n\) objects. Combinations are defined by
\[ {n \choose k} = \frac{n!}{(n - k)! k!}.\]
As a quick example,
\[{5 \choose 3} = \frac{5!}{2! 3!} = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(2 \cdot 1) (3 \cdot 2 \cdot 1)} = \frac{5 \cdot 4}{2} = 10.\] This means there are \(10\) ways to choose \(3\) objects out of a set of \(5\).
A Little Example
Let’s start with something small: \(n = 4\). Earlier, I mentioned that \( \vert S_4 \vert = 5\). Let’s see if we can get this same result using combinatorics.
In a \(4\)-step staircase, the maximum number of double steps we can take to get to the top is \(\lfloor 4 / 2 \rfloor = 2\). So we need to count how many ways there are to climb the staircase using \(0, 1 \text{ and } 2\) double steps. Then, we’ll add those up and with some luck, we’ll get \(5\).
Zero Double Steps
This one’s pretty straight forward. If we use no double steps, then we’re using only single steps. There’s only one way to do this, and that’s one step at a time: \(S_{4, 0} = \{(1, 1, 1, 1)\}\).
I’m using slightly different notation here. \(S_{i, j}\) is the set of distinct ways to climb \(i\) steps using \(j\) double steps.
One Double Step
Now, we’re going to use one double step. When you sit and think about it for a moment, you’ll see that there are just three ways to do this: \(S_{4, 1} = \{(2, 1, 1), (1, 2, 1), (1, 1, 2)\}\).
Two Double Steps
This one is also pretty straight forward. We’re using all double steps, and there’s only one way to do that: \(S_{4, 2} = \{(2, 2)\}\)
Results
You may have already noticed that we have now shown that \(\vert S_4 \vert = 5\) in a new way since
\[ \vert S_4 \vert = \sum_{j = 0}^{2} \vert S_{4, j} \vert = \vert S_{4, 0} \vert + \vert S_{4, 1} \vert + \vert S_{4, 2} \vert = 1 + 3 + 1 = 5.\]
Let’s look at these results a little more closely. This was a good exercise, but imagine trying to do all this work for \(n = 100\)! It would be nearly impossible and endlessly maddening to write all of that down. Luckily, we can express each term of the sum above as a combination instead of as the cardinality of a set. Notice that
\[\begin{align*} \vert S_4 \vert & = \sum_{j = 0}^{2} {4 - j \choose j} = {4 \choose 0} + {3 \choose 1} + {2 \choose 2} \\\\ & = \frac{4!}{4! 0!} + \frac{3!}{1!2!} + \frac{2!}{0!2!} = 1 + 3 + 1 = 5. \end{align*}\]Remarkably, this sort of pattern turns out to work for all \(n > 0\). In general,
\[\vert S_n \vert = \sum_{j = 0}^{\lfloor n / 2 \rfloor} {n - j \choose j}.\]
And indeed, this is directly a consequence of the combinatoric formulation for the Fibonacci sequence, which is given by
\[ F_n = \sum_{j = 0}^{\lfloor \frac{n - 1}{2}\rfloor} {n - j - 1 \choose j}, \hspace{0.5cm} n > 0.\]
Neat! Comparing these two side by side let’s us see clearly that \( \vert S_n \vert = F_{n + 1}\).
Interpretation
We’ve established the relationship between the staircase problem and the Fibonacci sequence, which is pretty cool, but why does this relationship exist?
Look back at the combinatoric sum for \(\vert S_4 \vert \) and compare it to the corresponding terms in the sum that uses cardinality.
In the sum using cardinality, each term represents the number of distinct ways to climb when using a fixed number of double steps. We are doing exactly the same thing in the combinatoric sum, but we’re just going about it a little differently.
For each term of the combinatoric sum \({n \choose k}\), the \(k\) represents the number of double steps and the \(n\) represents the total number of steps you’ll take given that you’re taking \(k\) double steps. For example, if you’re only taking \(1\) double step up \(4\) stairs, then you have to take \(2\) single steps as well to get to the top, so \(3\) steps combined–hence, \({3 \choose 1}\). Out of the \(3\) steps, we’re choosing which \(1\) will be the double step.
Now, as for why this just happens to produce the Fibonacci sequence, I really don’t have a good explanation. A brief look at the history of this formulation shows that it’s been around since the 19th century, so it’s nothing new. When the Fibonacci sequence shows up like this in strange and unexpected places, perhaps it’s best to just bask in the serendipity of it all.
To Conclude, A Much Larger (but Shorter) Example
So now that we finally understand the relationship between the staircase problem and the Fibonacci sequence, we can (sort of) easily obtain the number of distinct climbs for large staircases.
The Fibonacci sequence blows up deceptively quickly; for the stairs leading to the crown of the Statue of Liberty, a set of \(354\) stairs, there are roughly \(\mathbf{6.93 \times 10^{73}}\) distinct ways to climb them, an inconceivably large number that absolutely exceeds the number of atoms in the solar system and probably the entire galaxy.
