1 Step 2 Step

This problem is a tricky one because it can be a bit tempting to try to count all the possibilities one by one. While this is sometimes necessary, often there's a better approach.

Tayla, Cindy and Iris from Elm Park School started with smaller flights of stairs and spotted a pattern. Miss Hodgetts' Y9 Class from Ounsdale High School and many other people also saw the pattern. Well done.

Suppose Liam is going down $12$ steps. He can start by taking one step, then he has $11$ more steps to go down. The only other possibility is that he starts by taking two steps and has $10$ more steps to go down. So how does the number of ways of going down $12$ steps depend on the number of ways of going down $10$ steps and $11$ steps?

It helped to start with small numbers of steps and many people sent in lists like this one:

1 Step 1 Total 1 way
2 Steps 1,1 or 2 Total 2 ways
3 Steps 1,1,1 or 1,2 or 2,1 Total 3 ways
4 Steps 1,1,1,1 or 1,1,2 or 1,2,1 or 2,1,1 or 2,2 Total 5 ways
5 Steps 1,1,1,1,1 or 1,1,1,2 or 1,1,2,1 or 1,2,1,1 or 1,2,2 or 2,2,1 or 2,1,2 or 2,1,1,1 Total 8 ways
6 Steps 1,1,1,1,1,1 or 1,1,1,1,2 or 1,1,1,2,1 or 1,1,2,1,1 or 1,2,1,1,1 or 1,1,2,2 or 1,2,2,1 or 2,1,1,2 or 2,1,2,1 or 2,2,1,1 or 2,2,2 or 2,1,1,1,1 or 1,2,1,2 Total 13 ways
etc.    

The tricky pattern to spot is that each total on the right is the sum of the previous two totals.

Peter Zhu pointed out that this can be expressed simply as an algerbaic relation. He used the notation $S_n$ to mean the total number of ways of descending $n$ steps.

Then the formula is
 
$S_n = S_{n-1} + S_{n-2}$

So, since $S_1=1$ and $S_2=2$, that means $S_3=3$, $S_4=5$, $S_5=8$, $S_6=13$, $S_7=21$, $S_8=34$, $S_9=55$, $S_{10}=89$, $S_{11}=144$, and $S_{12}=233$.

The number of ways to get to the 12th step is 233.

The reason for this pattern is very simple. For the first step Liam has two choices:

i) Jump down 1 step. This leaves n-1 steps.
ii) Jump down 2 steps. This leaves n-2 steps.

So if you know that Liam has $S_{n-1}$ ways of going down n-1 steps, and also $S_{n-2}$ ways of going down n-2 steps, all of these, when combined with the right choice of first step, give a way of going down n steps. This sum is exactly the relation $S_n = S_{n-1} + S_{n-2}$.

Congratulations to everyone who managed to spot this pattern and find this answer. Those of you who have heard of the Fibonacci numbers will notice that the totals are the Fibonacci sequence, starting at 1, 2, ...

In fact there is a formula for finding any Fibonnaci number without having to add up all the previous ones. You might like to try and find out what it is. This would make counting the total number of ways of jumping down 1000000 steps much easier, but you'll probably never need to jump down that many steps.

Another interesting detail is that there are many number sequences that follow the pattern $S_n = S_{n-1} + S_{n-2}$. The Lucas numbers are an example. Can you see that if you specify the first two numbers, all the rest of the sequence is given without any more choice? What about if you are told only the first number, how many possible sequences with this addition property are there?

There is another reasonably quick and easy way to find the answer 233 if you're confident with combinations and binomial coefficients. These are some stage 5 topics that you can read about in this article. Matias Cano sent in his idea:

First of all I broke down all the different ways of down 12 stairs:
  1. Always jump one step at a time
  2. Jump two steps 1 time, and one step 10 times
  3. Jump two steps 2 times, and one step 8 times
  4. Jump two steps 3 times, and one step 6 times
  5. Jump two steps 4 times, and one step 4 times
  6. Jump two steps 5 times, and one step 2 times
  7. Always jump two steps at a time

Matias then used binomial coefficients. These strange and useful numbers have a special notation and formula, explained in more detail in the article.

$n \choose r$ means 'the number of ways of choosing $r$ objects from a total of $n$' where the order of the choices doesn't matter. It's said 'n choose r'

For example ${4 \choose 2} = 6$ because from the numbers 1, 2, 3, 4 I can make six pairs:
12, 13, 14, 23, 24, 34 (remember we consider 34 the same as 43)

The formula for the binomial coefficients uses the factorial notation $n! = n\times(n-1)\times(n-2)\times...\times 2 \times 1$ and is

$${n \choose r} = \frac{n!}{r!(n-r)!}$$

So the factorials on the right give a formula for 'n choose r'.

This can be linked to jumping down stairs because Liam can decide where to put his two-step jumps. If there are n total jumps, and exactly r of them are two-step, then there are $n \choose r$ possible ways of making the jumps. We have to 'choose' r different places out of the n steps to put the double jumps.

For the item 1 there's 1 posibility
For the item 2 there are 11 posibilities because this is 11 choose 1
For the item 3 there are 45 posibilities because this is 10 choose 2
For the item 4 there are 84 posibilities because this is 9 choose 3
For the item 5 there are 70 posibilities because this is 8 choose 4
For the item 6 there are 21 posibilities because this is 7 choose 5
For the item 7 there are 1 posibility

Total of the posibilities will be: 1+11+45+84+70+21+1 = 233
Final result = 233 posibilities.

Brilliant work everyone. This was a problem which can involve some sophisticated and difficult maths!