Steps question

HyuugaNeji SG

A stairway has 7 steps. John always walk up the stairs by taking either 1 step or 2 steps or 3 steps at a time. How many ways can he walk up the stairs?

The solution looks like this. (It might be wrong cos i vaguely remember it to be like this only)

Suppose only 1 step, there will only be 1 way.

Suppose there are 2 steps, there will be 2 ways to go up.

Suppose there are 3 steps, there will be 4 ways to go up. {1,1,1}{1,2}{2,1}{3}

Suppose there are 4 steps, there will be 1 + 2 + 4 = 7 ways to go up.

Suppose there are 5 steps, there will be 2 + 4 + 7 = 13 ways

Suppose there are 6 steps, there will be 4 + 7 + 13 = 24 ways.

Suppose there are 7 steps, there will be 7 + 13 + 24 = 44 ways.

Answer: 44 ways.

My friend told me this is the advanced fibonacci sequence whereby you add 3 terms instead of 2 terms.

Can someone check if there is any mistake and what is the real formula called? And explain to me the rationale of adding previous 3 terms?

Thanks in advance again.

skythewood SG

1111111 ==> 1 way

111112 ==> 6 ways
11122 ==> ? ways
1222 ==> 4 ways

11113 ==> 5 ways
133 ==> 3 ways

1123 ==> ? ways
223 ==> 3 ways

HyuugaNeji SG

1111111 ==> 1 way

111112 ==> 6 ways
11122 ==> ? ways
1222 ==> 4 ways

11113 ==> 5 ways
133 ==> 3 ways

1123 ==> ? ways
223 ==> 3 ways

11122 => 5!/2!3! = 10 ways

1123 = > 4!/2! = 12 ways

total = 44ways.

Thanks for your input and method.

skythewood SG

11122 => 5!/2!3! = 10 ways

1123 = > 4!/2! = 12 ways

total = 44ways.

yup. that's the way i will advise sec sch student to approach bah... down to earth, step by step...

unless you are going to find a very big number of steps, than find the pattern....

fibonacci goes like this... 1,1,2,3,5,8,13,21,34....

HyuugaNeji SG

i know why liao. So stupid. Only now then i understand the logic.

For steps more than 4, You can assume John take can make any of the 3 moves: 1 step, 2 steps and 3 steps.

If he take 1 step in the first move, then you just need to count for the remaining 3 steps.

If he take 2 steps in the first move, then you just need to count for the remaining 2 steps.

If he takes 3 steps in the first move, then you just need to count for the remaining 1 step.

Then you can just repeat them again.