The Staircase of Problems

Probability Level 3

Mr. Hu is running up a staircase. If he can take one, two, or three steps at a time, then in how many distinct ways can he run up eleven steps of the staircase?

Note: Running up one stair then two stairs is considered different from running up two stairs then one stair.

165 277 462 504

2 solutions

Geoff Pilling
Nov 15, 2018

If $a_n =$ The number of ways he can get to the $n$ th step, then,

$a_0 = 1$
$a_1 = 1$
$a_2 = 2$

Beyond that, (for $n > 2$ ):

$a_n = a_{n-3} + a_{n-2} + a_{n-1}$

$a_{11} = \boxed{504}$

Vijay Simha
Nov 13, 2018

The solution to this problem lies in finding the 11th Tribonacci number:

Refer to http://mathworld.wolfram.com/TribonacciNumber.html to know more about these numbers.

The first few tribonacci numbers are: 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504,

In the above sequence omit 0, 0 and 1 because they are repetitive.

Start with the 1 which comes before 2 and let that be the first one, then count 11 including that one to get 504.

The Staircase of Problems

2 solutions

0 pending reports