Add new comment

It's a long way to the top: Solution

Stairs

Every time I come home I have to climb a flight of stairs. When I'm feeling energetic I sometimes take two steps at a time. This gives me a number of ways to climb the stairs. For example, if there are ten steps, I could climb them taking five leaps of two, giving the pattern

2, 2, 2, 2, 2.

Or I could only use a leap of two at the beginning and the end, giving the patter

2, 1, 1, 1, 1, 1, 1, 2.

How many ways are there all together of climbing the ten steps?

Being a mathematician, I don’t have ten steps of course, but I have $n$ steps. Can you find a formula to express the number of ways there of climbing $n$ steps using leaps of one and two?

Solution

Let’s write $S(n)$ for the number of ways to climb a flight of stairs with $n$ steps. There are two possibilities for starting my climb: I could start it using a single step or a leap of two steps. If it’s the former, then there are $n-1$ steps left to climb, which I can do in $S(n-1)$ ways. If it’s the latter, there are $n-2$ steps left to climb, which I can do in $S(n-2)$ ways. This means that

  \[ S(n) = S(n-1) + S(n-2). \]    

This is a recurrence relation. If I know $S(1)$ and $S(2)$ then I can work out $S(3)$, which I can then use to work out $S(4)$, then $S(5)$, etc.

Clearly $S(1) = 1.$ There is only one way I can climb up one step and that’s using, well, one step. It’s also easy to see that $S(2) = 2.$ I can climb up two steps using two single steps or one leap of two. This gives

  \[ S(3) = S(2)+S(1) = 2+1 = 3, \]    
  \[ S(4) = S(3)+S(2) = 3+2 = 5, \]    
  \[ S(5) = S(4)+S(3) = 5+3 = 8, \]    
  \[ S(6) = S(5)+S(4) = 8+5 = 13, \]    

and so on. This sequence of numbers might start to look familiar. It's the Fibonacci sequence, which happens to be defined via a recurrence relation in exactly the same way as we defined it here: each number is the sum of the two previous ones. (To be totally accurate, the Fibonacci sequence actually has the first two terms being equal to 1 and 1, rather than 1 and 2, so what we have here is the sequence displaced by a term.)

Carrying on with the calculations we see

  \[ S(7) = S(6)+S(5) = 13+8 = 21, \]    
  \[ S(8) = S(7)+S(6) = 21+13 = 34, \]    
  \[ S(9) = S(8)+S(7) = 34+21 = 55, \]    
  \[ S(10) = S(9)+S(8) = 55+34 = 89. \]    

So there are 89 ways of climbing a flight of ten steps using steps of one and two!

See this article to find out more about the Fibonacci sequence.

Filtered HTML

  • Web page addresses and email addresses turn into links automatically.
  • Allowed HTML tags: <a href hreflang> <em> <strong> <cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.
  • Want facts and want them fast? Our Maths in a minute series explores key mathematical concepts in just a few words.

  • What do chocolate and mayonnaise have in common? It's maths! Find out how in this podcast featuring engineer Valerie Pinfield.

  • Is it possible to write unique music with the limited quantity of notes and chords available? We ask musician Oli Freke!

  • How can maths help to understand the Southern Ocean, a vital component of the Earth's climate system?

  • Was the mathematical modelling projecting the course of the pandemic too pessimistic, or were the projections justified? Matt Keeling tells our colleagues from SBIDER about the COVID models that fed into public policy.

  • PhD student Daniel Kreuter tells us about his work on the BloodCounts! project, which uses maths to make optimal use of the billions of blood tests performed every year around the globe.