Going upstairs

Probability Level 4

I can climb stairs either 1, 2, or 3 steps at a time. Our staircase has 20 steps. How many different ways can I go up the stairs?

Image credit: Wikipedia Matthew Logelin

The answer is 121415.

1 solution

Nidhin Basheer
Dec 18, 2014

Let 'F(N)' be the number of ways he can climb the stairs where N is the no: of stairs in the staricase.

So F(1)=1, F(2)=2, F(3)=4, F(4)=7, F(5)=13, F(6)=24

As u can see from the above series

F(k)= F(k-1)+F(k-2)+F(k-3)

Enough said!! F(20)= 121,415

How do you say that this pattern will go on? Thanks!

Satvik Golechha - 6 years, 5 months ago

How did you do it? @Satvik Golechha

Krishna Ar - 6 years, 5 months ago

I never did it, and neither did I say I did...

Satvik Golechha - 6 years, 5 months ago

@Satvik Golechha – -_- Bullcrap. How did you get it right then?

Krishna Ar - 6 years, 5 months ago

@Krishna Ar – I never did, and neither did I say I did...

Satvik Golechha - 6 years, 5 months ago

This is known as the Tribonacci Sequence , which is a close relation of the Fibonacci Sequence.

It does not have a "nice" closed from like the Fibonacci sequence, because the equation $x^3 - x^2 - x - 1 = 0$ does not have nice roots. It grows approximately as $C \times 1.84^n$ , where $1.839$ is the approximate value of the largest absolute value of the roots.

Calvin Lin Staff - 6 years, 5 months ago

I had the same logic. It does seem unnecessary to have such a large staircase if this is the intended method of solving.

Mike Pannekoek - 1 year, 10 months ago

Going upstairs

Image credit: Wikipedia Matthew Logelin

The answer is 121415.

1 solution

0 pending reports