Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Escher's Relativity

      It's a long way to the top

      9 December, 2014
      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 pattern

      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 are of climbing n steps using leaps of one and two?

      Hint: Think recurrently! I could start my climb with a leap of one or two...

      Solution link
      It's a long way to the top: Solution
      • Log in or register to post comments

      Anonymous

      11 December 2014

      Permalink
      Comment

      S(1)=1
      S(n)=1+S(n-1)+S(n-2)+S(n-3)+...+S(1)

      • Log in or register to post comments

      Anonymous

      12 December 2014

      Permalink
      Comment

      To reach n, i should first reach n-2 or n-1; and to reach n-2, i should reach n-3 or n-2.
      Considering this, i will get:

      F(n) = F(n-1)+F(n-2)
      F(n-1) = F(n-2)+F(n-3)
      ...
      F(2)=2
      F(1)=1

      This means to reach the n-th step, the number of ways is a Fibonacci number F(n).

      • Log in or register to post comments

      Anonymous

      12 December 2014

      Permalink
      Comment

      To reach n, i should first reach n-2 or n-1; and to reach n-2, i should reach n-3 or n-2.
      Considering this, i will get:

      F(n) = F(n-1)+F(n-2)
      F(n-1) = F(n-2)+F(n-3)
      ...
      F(2)=2
      F(1)=1

      This means to reach the n-th step, the number of ways is a Fibonacci number F(n).

      By the way, F(10) = 89.

      • Log in or register to post comments

      Ayaan Dutt

      21 April 2015

      Permalink
      Comment

      When I first attempted this puzzle I tried finding a pattern in the possible ways of going up a smaller no. of steps. I used the binary system to find all the possible ways . Finally I got the formula: 2 to the power of n! Then I did 2 to the power of 10 (the no. of steps) and got 1024 (no. of ways to go up 10 steps). Then I checked the solution and found mine was wrong!! I don't understand what I did wrong!? Can somebody please explain??

      • Log in or register to post comments

      Anonymous

      17 May 2015

      In reply to BINARY by Ayaan Dutt

      Permalink
      Comment

      I too started with your approach Ayaan. Afterall, for n steps, there are n-1 points at which point I might take 2 steps at once. Since I can either take or not take 2 steps at each of the n-1 points, there are 2^n-1 such total possibilities.

      Note though that this approach does not give the correct answer because you cannot take 2 steps at two consecutive points.

      If we model the points as a binary number, the problem becomes this: in the binary representation of all numbers 0 to 2^(n-1), how many such numbers are formed without adjacent bits set?

      For n=2, the binary representations to consider are: 0 1
      For n=3, the binary representations to consider are: 00 01 10 11
      And for each successive n, we just tack a zero to the left of the previous representations and then a one to the left.
      Thus for n= 4, zero-tacking gives 000 001 010 011 and one-tacking gives 100 101 110 111.

      Finally zero-tacking means that any representation that did not previously contain two consecutive bits set will again be OK.
      But one-tacking means that any previous representation with the high bit set will now contain two consecutive bits.

      So

      n(I) = n(I-1) + n(I-1) with the high bit zero
      but
      n(I) with the high bit zero = n(I-1)
      so
      n(I) = n(I-1) + n(I-2)

      This is the Fibonacci solution derived by other posters.

      • Log in or register to post comments

      Ernest

      22 January 2019

      Permalink
      Comment

      [(n-0)! /(n-2×0)!]÷0! + [(n-1)!/(n-2×1)!]÷1! +[(n-2)!/(n-2×2)!]÷2! + ....................+ [(n-(n÷2))!/(n-n)!]÷(n÷2)!

      • Log in or register to post comments

      Shiro Kusakabe

      4 October 2022

      Permalink
      Comment

      I got a sigma notation expression:

      5
      Σ nCr(10-n, n)
      n=0

      In this case, n denotes the number of leaps of 2 steps, which leaves the number of single step to be (10-2n), and the total number of steps to be (10-2n)+n=10-n, among which there are n two-step leaps, and the number of different arrangements of such steps being nCr(10-n, n). Adding together the different number of ways this can be done (ranging from no two-step leaps to a max of 5 two-step leaps for a 10-step staircase) should give the answer.

      • Log in or register to post comments
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms