2010 AMC 8 Problem 25 Recursion – Combinatorics

Understand the problem

Everyday at school, Jo climbs a flight of $6$ stairs. Jo can take the stairs $1$, $2$, or $3$ at a time. For example, Jo could climb $3$, then $1$, then $2$. In how many ways can Jo climb the stairs? $\textbf{(A)}\ 13 \qquad\textbf{(B)}\ 18\qquad\textbf{(C)}\ 20\qquad\textbf{(D)}\ 22\qquad\textbf{(E)}\ 24$
Source of the problem

2010 AMC 8 Problem 25

Topic
Recursion – Combinatorics
Difficulty Level
Easy
Difficulty Level
Easy
Suggested Book
Excursion in Mathematics

Start with hints

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 $1$. \( \\ \) There are $2$ ways to climb two stairs: $1$,$1$ or $2$. \( \\ \) For 3 stairs, there are $4$ ways: ($1$,$1$,$1$) ($1$,$2$) ($2$,$1$) ($3$) . \( \\ \) 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 .

Watch the video

Connected Program at Cheenta

Math Olympiad Program

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.

Similar Problems

Pattern Problem| AMC 8, 2002| Problem 23

Try this beautiful problem from Pattern from AMC-8(2002) problem no 23.You may use sequential hints to solve the problem.

Quadratic Equation Problem | PRMO-2018 | Problem 9

Try this beautiful problem from Algebra based on Quadratic equation from PRMO 8, 2018. You may use sequential hints to solve the problem.

Set theory | ISI-B.stat Entrance | Objective from TOMATO

Try this beautiful problem Based on Set Theory .You may use sequential hints to solve the problem.

Arrangement Problem | AIME 2012 | Question 3

Try this beautiful problem from the American Invitational Mathematics Examination, AIME, 2012 based on Arrangement. You may use sequential hints.

Area of the Trapezoid | AMC 8, 2002 | Problem 20

Try this beautiful problem from AMC-8, 2002, (Problem-20) based on area of Trapezoid.You may use sequential hints to solve the problem.

Problem related to Money | AMC 8, 2002 | Problem 25

Try this beautiful problem from Algebra based on Number theory fro AMC-8(2002) problem no 25.You may use sequential hints to solve the problem.

Divisibility Problem | PRMO 2019 | Question 8

Try this beautiful problem from the American Invitational Mathematics Examination, AIME, 2015 based on Smallest Perimeter of Triangle.

Area of Trapezoid | AMC 10A, 2018 | Problem 9

Try this beautiful problem from AMC 10A, 2018 based on area of trapezoid. You may use sequential hints to solve the problem.

Problem on Series and Sequences | SMO, 2012 | Problem 23

Try this beautiful problem from Singapore Mathematics Olympiad, 2012 based on Series and Sequences. You may use sequential hints to solve the problem.

Problem from Probability | AMC 8, 2004 | Problem no. 21

Try this beautiful problem from Probability from AMC 8, 2004, Problem 21.You may use sequential hints to solve the problem.