Climbing Stairs

Probability Level 5

Amanda can climb 1, 2, 3, or 4 stairs at a time. How many different ways can she climb up 20 stairs?

Check out my other problems

The answer is 283953.

1 solution

Geoff Pilling
Apr 3, 2016

For 1-4 stairs you can quickly figure out that there are 1, 2, 4 and 8 ways respectively to get there. Now to get to the $n^\text{th}$ stair, she must have come from either stair $n-4, n-3, n-2$ , or $n-1$ . So if $f(n)$ is the number of ways, then $f(n) = f(n-4) + f(n-3) + f(n-2) + f(n-1)$ . Using this equation, $f(20) = 283953$ .

Also called Tetranacci Numbers

Vishnu Bhagyanath - 5 years, 2 months ago

Done by the same........but is there any short trick to calculate the value of f (20) ........I did it by simple addition...that is by finding f (5) Then f (6) and so on upto f (20)

Aniket Sanghi - 5 years, 2 months ago

Like yourself I worked it out the long way, and then thought a little harder later on. The iterates of the recurrence relation (that is 1,2,4,8,15, ......, 147312, 283953,...) occur as the coefficients in the expansion of $\frac{1}{1-x-x^2-x^3-x^4}$ .

If you ask WolframAlpha to expand this function and then ask for more terms of the series expansion about zero you will see the answers appear like a miracle.

This is an example of a generating function. If you need to find out more I suggest starting by studying the Fibonacci series and its generating function using the internet. If you want to go deeper check out 'Generatingfunctionology' by H. Wilf.

Best wishes.

Peter Macgregor - 5 years, 2 months ago

Climbing Stairs

The answer is 283953.

1 solution

0 pending reports