The number of distinct ways to climb a staircase of n steps, taking either one step or two at a time, is f(n) = f(n-1) + f(n-2), starting from f(1) = 1 and f(2) = 2. Those values are the Fibonacci numbers shifted one place along, so a flight of 10 steps can be climbed 89 different ways.
The reasoning behind the formula is short. Your final move onto the top step is either a single step or a double step. If it was a single, you were standing on step n-1, and there are f(n-1) ways of having got there. If it was a double, you were on step n-2, with f(n-2) ways of having got there. Those two groups cover every possible route and never overlap, so the counts simply add.
Counting the first few staircases by hand
Before trusting a formula, list the routes for small staircases and count them.
- 1 step. One route: a single. So f(1) = 1.
- 2 steps. Two routes: single then single, or one double. So f(2) = 2.
- 3 steps. Three routes: 1 and 1 and 1, or 1 then 2, or 2 then 1. So f(3) = 3.
- 4 steps. Five routes: 1,1,1,1 then 1,1,2 then 1,2,1 then 2,1,1 then 2,2. So f(4) = 5.
Now check the fourth case against the formula. f(4) = f(3) + f(2) = 3 + 2 = 5. It agrees, and it will keep agreeing all the way up.
The full pattern
Carrying the addition on gives the number of ways for each staircase height:
- n = 1: 1 way
- n = 2: 2 ways
- n = 3: 3 ways
- n = 4: 5 ways
- n = 5: 8 ways
- n = 6: 13 ways
- n = 7: 21 ways
- n = 8: 34 ways
- n = 9: 55 ways
- n = 10: 89 ways
- n = 11: 144 ways
- n = 12: 233 ways
Anyone who has met the Fibonacci sequence, 1, 1, 2, 3, 5, 8, 13, will recognise every number in that list. The staircase count for n steps is the Fibonacci number in position n+1, which is why the problem is often described as Fibonacci in disguise.
The base cases, where nearly everyone slips
The most common error by a distance is to start the sequence 1, 1 out of habit, because that is how Fibonacci is usually written down. Do that and every answer comes out one place too early: one way for two steps, two ways for three steps, three ways for four steps, and so on down the line.
Two steps genuinely has two routes, and you can see both by listing them. So set f(1) = 1 and f(2) = 2. The alternative is to define f(0) = 1, the single way of climbing nothing at all, and let everything else follow from the recurrence. Either convention works. Mixing the two does not.
This is worth dwelling on because it is exactly what a multiple choice version of the question tests. Offer 1, 2, 3, 5 and 8 as the options for a four step flight and the wrong base case lands you on 3 rather than 5.
A second method: count by the number of double steps
There is another route to the same answer, and it makes a good cross check.
Suppose you take exactly t double steps on an n step flight. Those doubles use 2t steps, leaving n - 2t singles, so you make n - t moves in total. The only question left is which t of those n - t moves are the doubles, which is a straightforward combination, written C(n - t, t).
Add up every possible value of t, from no doubles to as many as will fit. For a five step flight:
- No doubles: C(5, 0) = 1 route
- One double: C(4, 1) = 4 routes
- Two doubles: C(3, 2) = 3 routes
That totals 1 + 4 + 3 = 8, which matches the table above.
Common variations
The problem is rarely left in its original form. Three variations come up repeatedly.
Longer strides. If you may take one, two or three steps at a time, the same argument gives f(n) = f(n-1) + f(n-2) + f(n-3), and the sequence runs 1, 2, 4, 7, 13, 24, 44 for n from 1 to 7. The logic is unchanged: your last move now arrives from one of three places instead of two.
A broken step. If step b cannot be landed on, you have to clear it in a single stride from b-1 to b+1. The count becomes f(b-1) multiplied by f(n-b-1): the routes up to the step before it, times the routes on from the step after it. On a ten step flight with the fourth step out of use, that is f(3) x f(5), or 3 x 8, giving 24 routes. If the broken step is the top one, there is no way up at all.
Fewest moves rather than most routes. Some versions ask for the shortest climb instead of the number of climbs, which is a much duller question: take doubles the whole way and add one single at the end if n is odd.
Where this shows up in an aptitude test
You are unlikely to meet the staircase story word for word. What you will meet is its shape. A number series item running 1, 2, 3, 5, 8, 13 is this problem with the wrapping taken off, and a great many sequence and pattern questions reward the same instinct: work out how the current term is built from the terms before it, rather than hunting for a rule that produces it from n directly.
The problem also turns up as a standard teaching exercise in computing courses, where it is used to introduce recursion. The counting argument is identical either way, and it is the counting argument that an aptitude test is interested in.
Two things are worth taking away. Establish the small cases by listing them rather than assuming them. Then, once you have a formula, test it against a case you have already counted by hand.
Practice sequence and pattern questions
Questions built on this kind of reasoning appear throughout numerical reasoning tests and logical reasoning tests. For the specific skill of spotting how a term is built from the ones before it, work through our guide to number series questions, or take a broader sample with our free aptitude tests.
