ONE
    Númas
    ← Back to the programme
    OlympiadMediumCombinatorics7–9

    A staircase has 1010 steps and can be climbed one or two steps at a time. In how many different orders can it be climbed?

    Uma escada tem 1010 degraus e pode ser subida um ou dois degraus de cada vez. De quantas maneiras diferentes se pode subir?

    Answer options

    Solution

    Step 1 of 3

    1. 1.Let ana_n be the number of ways to reach step nn. The last move came from step n−1n-1 or step n−2n-2, so an=an−1+an−2a_n = a_{n-1} + a_{n-2}.