Lesson Progress

0% Complete

Everyday at school, Jo climbs a flight of stairs. Jo can take the stairs , , or at a time. For example, Jo could climb , then , then . In how many ways can Jo climb the stairs?

Recursion – Combinatorics

Easy

Easy

Excursion in Mathematics

Do you really need a hint? Try it first!

Try to recall the concept of recursion . Then proceed to apply in this question . https://en.wikipedia.org/wiki/Recursion#In_mathematics

The number of ways to climb one stair is . \( \\ \) There are ways to climb two stairs: , or . \( \\ \) For 3 stairs, there are ways: (,,) (,) (,) () . \( \\ \) Try to aply this for 4 stairs in recursive manner .

For 4 stairs : After climbing 1 stair in one step , Jo can climb the rest 3 stairs in (1 , 1 , 1) ,(1 , 2), (2, 1) ,(3) i.e. in 4 ways . \( \\ \) After climbing 2 stairs in one step , Jo can climb the rest 2 stairs in (1 , 1 ) and ( 2) i.e. in 2 ways . \( \\ \) After climbing 3 stairs in one step , Jo can climb the rest 1 stair in a single step. \( \\ \) So to climb 4 stairs Jo can have (1+ 2 + 4) = 7 ways . Now time arrives to apply the recursion so proceed to apply .

Why will we apply recursion ? \( \\ \) Notice that to climb 5 stairs , \( \\ \) After climbing 1 stair in one step , we again have to find how many ways Jo can follow to climb the rest 4 stairs . \( \\ \) After climbing 2 stairs in one step , we again have to find how many ways Jo can follow to climb the rest 3 stairs . \( \\ \) After climbing 3 stairs in one step ,we again have to find how many ways Jo can follow to climb the rest 2 stairs . \( \\ \) So the no ways Jo can have for 5 stairs is ( 7 + 4 + 2) = 13 . \( \\ \) So for 6 stairs , the no ways Jo has (13 + 7 +4 ) = 24 .

Math Olympiad is the greatest and most challenging academic contest for school students. Brilliant school students from over 100 countries participate in it every year. Cheenta works with small groups of gifted students through an intense training program. It is a deeply personalized journey toward intellectual prowess and technical sophistication.