Ways to climb ten stairs with jumps of any length

Question

A rabbit at ground level wants to reach the $10$ th step of a staircase. Each jump takes it up by any positive number of steps. Counting a route by the sequence of steps it lands on, how many routes end exactly on step $10$ ?

Short answer

$512$ . A route is fixed by which of the intermediate steps $1,\dots,9$ it lands on, and any subset is possible. There are $2^9=512$ subsets.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Counting and Combinatorics
Sample Spaces, Events, and the Probability Axioms
Conditional Probability, Total Probability, and Bayes' Rule

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free