Stairs

Probability Level 3

Aaron wants to climb a flight of 8 stairs. He can reach up to 3 stairs at a time. How many ways are there for him to climb the steps?

81 100 24 64 34

1 solution

Geoff Pilling
Jun 30, 2016

If $N(n)$ is the number of ways to climb $n$ stairs, then we can see pretty quickly that $N(1) = 1$ , $N(2) = 2$ and $N(3) = 4$ .

For $n> 3$ , he must have reached the $n$ th step from either step $n-1$ , $n-2$ , or $n-3$ .

Therefore, $N(n) = N(n-1) + N(n-2) + N(n-3)$

So, $N(8) = \boxed{81}$

Just if anyone is curious, sequence that has the recurrence relationship as above is called "Tribonacci Sequence", which is a partially generalized form of Fibonacci Sequence. Here is a link to wolfram mathworld that has some information; http://mathworld.wolfram.com/TribonacciNumber.html

Nick Lee - 4 years, 11 months ago

Stairs

1 solution

0 pending reports