Category: Good Problems

1 Step, 2 Step

I’ve been working with R, a former student, this summer. A few days ago, I gave him an NRICH problem called 1 Step, 2 Step.

Liam’s house has a staircase with 12 steps. He can go down the steps one at a time or two at a time.

Our goal is to determine the number of ways Liam can walk down the stairs. I gave R no instructions or guidance; I actually stood in the yard while he worked. After around ten minutes, R told me he’d made some progress but might be stuck. I asked him to tell me what he’d come up with so far.

R told me that he’d decided to start by looking at smaller staircases. If Liam’s staircase had only two stairs, for example, he could walk down two different ways: take both steps one at a time or take the pair of steps two at a time. R listed out these possibilities for staircases with less than six steps. He used 1 to represent Liam walking one step at a time and 2 to represent Liam walking two steps at a time. Here’s the list for a staircase with four steps:

Case Approach for 4

R felt confident that he’d listed all of the possibilities for the first five staircases, but he felt like he might have missed one for the staircase with six steps. We decided that I’d say all of the different ways I could, and R would check them off his list as we went along. R’s intuition proved correct: he had missed one of the ways. The table below shows the number of ways for staircases with one to six steps. I encourage you to take a close look before you keep scrolling.

Case Approach part 1

Do you see it? R noticed that the number of ways looked a lot like the Fibonacci sequence. He couldn’t see, however, why this problem would have anything to do with the Fibonacci sequence. Frankly, neither could I. Actually, I couldn’t even begin to consider why the Fibonacci sequence appeared in the table because R’s thinking had impressed me so much. (As you’ll see below, I took a totally different approach to this problem.) R and I decided to test his hypothesis that the number of ways matched the Fibonacci sequence by looking at the staircase with seven steps. First, R added 8 and 13 to predict 21 ways. Then, R listed out all of the different ways to walk down that staircase. When R only came up with 20, he suspected he’d again missed one. We went through the ways together and found the missing one. His prediction for the seven-step staircase having proven correct, R confidently filled out the table below:

Case Approach part 2

R asked and I confirmed that the correct answer was indeed 233. But the mystery remained: What did this staircase problem have to do with the Fibonacci sequence? We managed to come up with this explanation. To walk down the twelve-step staircase, you could walk down a ten-step staircase and then go down the last two in one step. Or you could walk down an eleven-step staircase and then go down the last one in one step. Thus, you’d add the number of ways for ten- and eleven-step staircases.

As mentioned above, I solved the problem a totally different way. I viewed the problem as involving several different cases, each of which I could deal with by using combinations. The table below shows my reasoning for the twelve-step staircase:

Combinations Approach

Adding the numbers in the last column gives the 233 total ways that R calculated earlier.

Okay, now it all gets a little crazy. R and I haven’t talked about this yet, but I spent some time today thinking about it. Combinations got me thinking about Pascal’s Triangle, and it turns out there’s an interesting connection between it and the Fibonacci sequence. Take a look at the following image of a left-justified Pascal’s Triangle:

Fibonacci_in_Pascal_triangle
Image credit: Phan Yamada; Link to original file

Each diagonal adds up to a Fibonacci number. We’ll number the diagonals starting with 0. Let’s take a look at the 7th diagonal:

7th diagonal

Now, take a look at the approach I used to calculate the number of ways to walk down a seven-step staircase:

Combinations Approach 7 stairs

See the similarity? The entries in Pascal’s Triangle are binomial coefficients. If you want the second column of the fifth row, for example, you’d use the following binomial coefficient:

5C2

Comparing the “Combination Version 2” column of the table to the left-justified Pascal’s Triangle confirms that our calculation matches the diagonal. This is a pretty awesome result, one that I definitely wasn’t expecting when I gave R this problem!

Here are a few takeaways:

  1. Giving R the freedom to attack the problem without any guidance allowed him to develop a unique approach.
  2. Examining different approaches to the same problem reveals much more than focusing on a single approach.
  3. NRICH problems are awesome!

As I prepare for what promises to be a strange and challenging school year, I keep reminding myself of the power of problem solving. I haven’t quite figured out how to make this sort of exploration and discussion happen during remote learning, but I’m more committed than ever to finding a way to make it work.