Stairs and generalisation
BLOG: Heidelberg Laureate Forum
One of the great things about being a mathematician is that you learn how to tackle arithmetic and calculations and manipulate equations, so if you come across any of these problems in your work or life, you have the tools to be able to deal with them. But that’s not the only great thing. You also develop mathematical thinking skills, and learn to approach problems in new and exciting ways – and mathematical thinking isn’t always just about finding a straight answer.
Given a real-world physical system, or a particular instance of a puzzle or question, it’s often easy enough to put all of the values into a calculator and find a solution to the problem directly in front of you. For example, if I wanted to walk up a flight of stairs which has 4 steps, and I’m capable of stepping up one or two steps at a time, how many different possible walks up the stairs could I achieve? (Here, I’m assuming that it doesn’t matter which foot I step up with first, and that two walks up the stairs are considered the same if I step on the same treads).
I could take the first two steps together, then the second two together as well, and I could denote this walk up the stairs by (2,2). I could start with a double step, then two singles – (2,1,1). Or I could do two singles first, then a double step: (1,1,2). If I wanted to mix things up, I could do a single step, then two together and a single after that, giving (1,2,1). Finally, I have the boring grown-up option of taking all four stairs separately, denoted (1,1,1,1).
This puzzle is in itself fairly straightforward, and can be solved simply by checking all the cases. If I start with a double step, there are two options for how to finish (another 2, or two 1s). Then I can check what happens if I start with a single, and cover all the possibilities from there. The answer I get is 5 – five possible ways to walk up the stairs.
Of course, a mathematician faced with this problem is probably already thinking of other ways to approach it. If the four-step case seems daunting at first, what happens if we have only three steps? Or two, or one? If we treat one of these simpler cases first, do they give us an insight into what happens for larger staircases?
You might be thinking about the interesting fact that if you work out how many ways there are to walk up a three-step staircase, you can then add a single step at the start or end of each of these and get some of the four-step solutions. This tells you that if you increase the number of stairs by one, the number of ways to walk up the stairs will be at least as many as it was previously – but not necessarily twice as many, since adding a single one to the start and end of the sequence (1,1,1) gives you the same result.
You might even now be wondering if there’s a rule for which 3-step sequences will give different 4-step sequences if you add a single step at the start or end, or in the various points in the middle of the sequence – and for a given sequence, how can you work out how many ways there are to add a single step in the middle? And what about increasing the length by switching a single step for a double?
Someone who’s really thinking mathematically, might, despite me not having even suggested such a thing, be trying to work out what the answer to this question is in general, for a staircase of N stairs. Part of the game of thinking like a mathematician is making these kinds of mental jumps – from a specific case to a general case. This process is called generalisation, and is used to turn a single instance of a problem into a whole family of problems – by changing the value of a number, or some other property, in the original setup.
Modelling real-world problems is rarely as neat and whole-number-answer as this – but it’s often still possible to generalise a problem. If this bridge can take a certain amount of weight, what happens if I increase its span, or the thickness of the metal bars it’s made of? What would happen to this animal population if I changed the initial numbers of predators and prey? Sometimes curiosity is enough to motivate generalisation, but sometimes it’s useful to produce a model that can be deployed again when circumstances change.
While the staircase problem seems simple for small numbers, it might get very complicated if the numbers get much bigger, and making sure you’ve counted all the possibilities might get messy. If you can work out a solid way to get from the number of ways to walk up the N-step staircase to the number of ways for the N+1-step staircase, you can use mathematical induction – work out the answer for a small number of steps (e.g. one step, for which there’s exactly one way to do it) and use that to find the number of ways for two, then put that answer in to find the answer for three steps, and so on.
Maybe you’ve had a brilliant intuition about how the problem works, and found a guaranteed way to count all the possible paths up the stairs for a given number of steps. Then you probably don’t even need to try counting all the ways to walk up four steps, and when presented with the original problem, you immediately come up with a general formula and put in the value 4 to see what happens.
But not everybody can make that kind of intuitive leap. One more way to attack this kind of problem and get to a general result is to try the first few cases, and see what happens – down where the numbers are countable, for 1, 2, 3 and 4 steps, and maybe even 5 if you have a little patience. Once you have a few values, you can see if there’s any kind of sensible pattern in those numbers and maybe recognise something you vaguely remember having seen before.
Even if it’s not eerily familiar, maybe you can see a pattern in these numbers which might continue, that you can use to make a prediction about what will happen next. Then, if you can be bothered to count all the possibilities for 6, scribble them all down on a nearby bit of paper, and see if it matches your prediction (but of course, like a good thinker, don’t stop looking for new combinations once you’ve found as many as you predicted would exist; only stop when you’re completely sure you’ve checked all the possibilities, and don’t fall into the trap that so many have fallen into before of assuming your prediction is correct before you’ve completed the process of checking it).
Even though the mathematics involved here is fairly straightforward, and could probably be understood and worked out by an inquisitive child with a particular obsession with finding new ways to walk up the stairs (for the record, having an actual set of stairs to try this out on is unnecessary, but does add in an exciting physical element to the puzzle) – if you’ve made it this far and found yourself doing any of the things I’ve attributed to a mathematical thinker, then congratulations. You’re a mathematician, and there’s nothing you can do about it.
Not all stairs lead to the sky.
tell us the formula of the stairs
we aren’t as cute as you.
The solution to the stairs problem is the Fibonacci sequence (1,1,2,3,5,8,13,21,….).
For n steps there are F_(n+1) possible ways (F_n is the nth Fibonacci number). F_(4+1) = 5 as in the example.
But why? If you think about how new ways are added when you increase the number of stairs by one. E.g. with 5 steps you can either take 4 steps however you want and a last step, or take 3 steps and the last two steps at once. You basically add the number of the last two possibilities together, which is basically the definition of the Fibonacci sequence, and get F_(5+1)=8 possibilities.
With that knowledge it should also be possible to deduct the formula if you can take also take 3-steps at once 🙂 .
Thanks for your comments – I’ve deliberately not given the solution to this problem, as many people prefer a chance to work it out for themselves before being told the answer. Well done for working it out, and hopefully people who don’t want spoilers won’t scroll down this far!