IITD_2011 interview

Question

#IITD_2011

there is a frog who could climb either 1 stair or 3 stairs in one shot. In how many ways he could reach at 100th stair ?

Comments

Refer these links :

http://math.stackexchange.com/questions/789804/how-many-distinct-ways-to-climb-stairs-in-1-or-2-steps-at-a-time

 

http://math.stackexchange.com/questions/1456872/climbing-a-n-stair-staircase-taking-2-or-3-stairs-each-step

Answer 1

Its a question from recurrence relation here is the solution

 

http://math.stackexchange.com/questions/354499/how-to-solve-this-recurrence-relation

Answer 2

97C1+97C1*94C1/2!+97C1*94C1*91C1/3!+.......+97C1*94C1*91C1*.......*1C1/33!

there are 97 ways where i can take single 3 step,

there are 97 ways for 1st 3 step move and then 94 ways for another 33 step move and division is for removing duplicates.

e.g.  in no of ways where 2 times 3 steps can have a permuation where 3 step move taken at 3rd step and 52nd step counted twice so delete by the x!.

this is tedious job,but simple to understand.please correct me if anyting is wrong