This morning, I climbed my thirteen steps in this pattern: 1, 2, 1, 2, 1, 1, 2, 1, 2.

Yesterday the pattern was 1, 1, 1, 1, 1, 1, 2, 2, 1, 2.

**How many days do you think I can go before I have to repeat a pattern?**

**I wonder if there's a different way to climb the stairs for each day of the year...**

*There are lots of possibilities. It's going to be really hard to count them all without missing any, and without accidentally counting any twice.*

*Sometimes mathematicians like to tackle a big task by starting with a more manageable one, to get some insight into the bigger problem...*

**Can you think of a way to make this problem more manageable?**

*Perhaps you could investigate some smaller staircases first...*

**Is there a quick way to work out the number of different ways to go up any size staircase, one or two steps at a time?**

**How do you know your method will always work?**

*I wonder how big a staircase I would need in order to have more than a million different ways of climbing the stairs...*

Once you've explored this, you might like to take a look at Giant Steps.

## Comments

### 13 steps

What I did was to try this problem in a more manageable way, so I tried to do it up to five steps and see what the answers were.

I quickly found out the term to term rule was multiplying by 2. So it must be 2 to the power of n, but I worked out the numbers were double the real answer. So I just converted it into 2 to the power of n-1.

Lovely problem.

- Log in to post comments

### the rule definitely is not

the rule definitely is not multiplying by two:

1 step = 1 way: 1

2 steps = 2 ways: 1 1, 2

3 steps = 3 ways: 1 1 1, 1 2, 2 1

4 steps = 5 ways: 1 1 1 1, 1 1 2, 1 2 1, 2 1 1, 2 2

and so on

This is how to continue the pattern:

Extensions into 'what if we could take three at a time?' works too, because it is the previous three results added together instead of two:

3's added to the end of the 2 steps list, 2's to the 3 steps list and 1's added to the 4 step list will give you all of the 'sequences' for 5 steps

You can really go quite in depth with it if you want to.

- Log in to post comments

### started with fewer steps

So I saw Sergio's approach and decided to simplify even further. I considered 1 step and got 1 way. ways

2 steps, 2 ways.

3 steps, 3 ways.

4 steps, 5 ways.

5 steps, 8 ways.

I am noticing that the differences in "ways" appears to be Fibonacci. I haven't tried 6 steps but I will. Am I on the correct track?

- Log in to post comments

### 13 steps

Just posted a beginning solution. I did predict that 6 steps would have 13 ways (based on pattern in differences) and verified by writing them out. I am not sure if I included this in my previous comment.

- Log in to post comments

### Nice pattern spotting!

Good stuff Valerie, you've spotted a pattern that seems to work... I wonder if you can find an explanation why you get the Fibonacci sequence?

- Log in to post comments

### Seems to be a problem of counting and combinatorics

Assume that we go up the thirteen steps only by 1 step, and that we do not take steps two at a time.

This is equivalent to asking how many ways are there to order a sequence of 13 ones.

There are only 13_C_0, or 13!/13! ways, or only 1 way to go up the steps.

Now, assume that we go up the thirteen steps, and this time we only have one step that is two at a time.

This is equivalent to asking how many ways are there to order a sequence of 11 ones and 1 two.

There are 12_C_1, 12!/(11!*1!), or 12 ways to get up the steps.

We continue with going up the steps, two of the steps being two at a time.

This is equivalent to asking how many ways are there to order a sequence of 9 ones and 2 twos.

There are 11_C_2, 11!/(9!*2!), or 36 ways to get up the steps.

And so on, until we reach the final case, where six of the steps are two at a time, and only one step is one at a time.

The total ways possible is just the sum of all the ways in each case.

- Log in to post comments

### That's one way to solve it,

That's one way to solve it, but there is another very elegant way that's hinted at in some of the comments above!

- Log in to post comments

### Recursion is it...

Thinking about how this problem works when we allow 3 or more steps at a time...

We can use a recursion formula: $$f(n) = \sum_{k=0}^{n-1}f(k) \qquad \text{where} \ f(0)=1$$ Solving this recursion, you get $f(n) = 2^{n-1}$.

- Log in to post comments

### Help - I'm missing one 8 step combination

Help - I'm missing one of the 8 steps

11111111

1111112, 1111121, 1111211, 1112111, 1121111, 1211111, 2111111

111122, 111221, 112211, 122111, 221111, 212111, 211211, 211121, 211112, 121211, 121121, 121112, 112121, 112112, 111212

11222, 12221, 22211, 22121, 22112, 12212, 12122, 21122, 21221

2222

- Log in to post comments

### 13 steps

I worked through this problem by first seeing how many ways you could go up 2 steps which = 2 ways, then

3 steps = 3,

4 steps = 5,

5 steps = 8,

6 steps = 18

After I had worked out this I realised ...

- Log in to post comments

### Fibonacci

This is how I did it:

First step - 1 (way to get there)

Second step - 2 (1+1)

Third step - 3 (2+1)

Fourth - 5 (3+2)

Can you see the pattern?

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

I hope this is helpful.

- Log in to post comments

### Fibonacci

This is how I did it:

First step - 1 way to get there

Second step - 2

Third step - 3

Fourth - 5

Can you see the pattern?

First step - 1

Second step - 2 (1+1)

Third step - 3 (2+1)

Fourth - 5 (3+2)

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

I hope this is helpful.

- Log in to post comments

### Overall Formula

The overall formula from steps ($S$) to amount of combinations ($C$) is:

Where $\phi = \frac{1+\sqrt{5}}{2}$

This is similar to the Fibonacci formula, except for the '$S+1$' part.

- Log in to post comments