10. Recursion · Mastering AMC 8

10.10%

Recursion Fundamentals

In this section you will be able to count the ways up a staircase by building a table from the bottom step.

Jeff is climbing 6 stairs, 1 or 2 at a time. Listing every climb by hand is slow and easy to mess up. Can the small staircases do the work for you?

Here’s the big idea. Think about Jeff’s last jump. He lands on the top stair from one stair below, or from two stairs below.

So the ways to reach the top are the ways to reach those two stairs, added together. Start at the bottom and fill a table one stair at a time.

Look:each box in the table only needs the boxes just before it.

Exploreplay first, formulas later

Try this: Press Fill the next stair a few times. Click a filled box. Which two earlier boxes add up to it?
Try this: Press Show a climb. Where did the last jump start? Is it always one of those two stairs?
Try this: Fill all six stairs. Do the numbers 1, 1, 2, 3, 5, 8, 13 look familiar?
Try this: Turn on jumps of 3 as well. Predict f(3) before you fill it.

Name it

Definition 10.1.1 · Recursion

Recursion is the process of finding smaller values and using them to calculate larger values.

Remark 10.1.2

Look: the numbers $1, 2, 3, 5, 8, 13$ follow the Fibonacci sequence. That's because the recursion for our sequence and the Fibonacci recursion are the same. However, this is not always the case for all recursion problems.

Watch itpredict, then reveal

Example 10.1

Jeff is climbing a 6 stair staircase. If he can climb 1 or 2 stairs at a time, in how many distinct ways can he get to the top?

1
You could do casework, but that takes a long time. Solve it for small values first. How many ways are there for Jeff to reach the 0th stair (the ground)?

Predict first:
Your prediction

Try it

Problem 10.4.1

Jeff is climbing a 7 step staircase. If he can climb 1 or 2 steps at a time, in how many ways can he get to the top?

Contest cornerreal contest problems

Problem 10.4.2

AMC 8

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?

Checkpoint for section 10.1

Get 2 of 3 right to master this section. One try each, no hints.

10.20%

Recursion with Constraints

In this section you will be able to handle special rules, like a different last jump or a stair you can't land on.

This time Jeff gets a bonus. On his very last jump, he may leap 3 stairs! Does the whole table change, or just the top box?

A rule that only touches the last jump only changes the last box. Fill the table as usual, then look again at the top stair: which stairs can the final jump start from?

Recursion works for more than stairs. Whenever a big case can be built from smaller cases, you can make a table.

Exploreplay first, formulas later

Try this: Fill the table up to stair 6. Then fill stair 7. Why does f(7) add three boxes, not two?
Try this: Turn off the Last jump switch. How much smaller is f(7) now?
Try this: Turn off jump 1 so only 2 and 3 are left. Which stairs get a 0? Why?

Name it

Concept 10.2.1 · Solving with Recursion

To solve a problem with recursion, follow these steps:

Solve the problem for a few smaller base cases by hand.
In general, you need as many base cases as the number of terms on the right-hand side of your recursion.
For a given $f(n)$ , find a recursive equation in terms of earlier values of the function. Think about the different ways to get to that point.
Calculate the values of $f(n)$ one by one until you reach the number you want.

Remark 10.2.2

You can also use $f(0) = 1$ as a base case. To get to the 0th stair you take no steps, and there is only 1 way to do that. This can be a little faster, but it can also be a little confusing, so the examples don't use it. Feel free to use it in the problems!

Remark 10.2.3

In general, it never hurts to find too many base cases. If your recursion runs into a value you're not sure how to calculate (like $f(2)$ or $f(3)$ ), you can always go back and work out more base cases by hand.

Watch itpredict, then reveal

Example 10.2

Jeff is climbing a 7 stair staircase. Jeff can climb 1 or 2 stairs at a time on every step, but on the last step, he is allowed to climb 3 stairs. In how many distinct ways can he get to the top?

1
Before the last jump, Jeff uses jumps of 1 or 2, just like Example 10.1. So $f(n) = f(n-1) + f(n-2)$ there. What is $f(6)$ ?

Predict first:
Your prediction

open on YouTube

Example 10.3

Mike is climbing a staircase with 10 stairs. He is in a rush, so he will climb 2 or 3 steps at a time for most of the journey. If he reaches the 9th stair, he is allowed to climb 1 stair to reach the 10th stair. How many ways are there for Mike to reach the top of the staircase?

1
Start with the base cases. How many ways can Mike reach the 1st stair?

Predict first:
Your prediction

Try it

Problem 10.4.6(additional)

Jeff is climbing a 10 step staircase. However, there are spiders on the 3rd and 9th steps, and he refuses to step on those stairs. If he can climb 1 or 2 steps at a time, in how many different ways can he get to the top?

Contest cornerreal contest problems

Problem 10.4.3

Omega Learn Math Contest

Brandon is trying to reach the top of a 7 step staircase. For each jump except the last jump, he can either jump 1 or 3 steps forward. On the last jump, he can jump 1, 2, or 3 steps forward. How many different ways can he reach the top of the staircase?

Problem 10.4.4

AMC 12

Call a set of integers spacy if it contains no more than one out of any three consecutive integers. How many subsets of $\{1, 2, 3, \ldots, 12\}$ , including the empty set, are spacy?

Checkpoint for section 10.2

Get 2 of 3 right to master this section. One try each, no hints.

10.30%

Probability Recursions

In this section you will be able to track the chance of being in each place, one step at a time, with a table.

A cricket hops between 4 leaves. Each hop goes to one of the other 3 leaves, chosen at random. Where is it likely to be after 4 hops?

You can’t list every hop for long. Instead, track the chance of being on each leaf after every hop. Each new row of the table comes from the row before it.

Look:the cricket is always on some leaf, so every row adds up to 1.

Exploreplay first, formulas later

leaves4

After 0 hops: back on A =

1

Chance of each leaf after every hop
Hop	A★	each other	all leaves (total = 1)
0	1	0

Each bar is split by leaf colour. Every bar is full: the chances always add up to 1.

Try this: Press Hop once. Why is the chance on A now 0?
Try this: Hop again. Look at the bars in the table. Does every row still add up to 1?
Try this: Turn on Show the formula. Use it to predict the next chance on A before you press Hop.
Try this: Change the number of leaves to 3. What happens to the chance on A after many hops?

Name it

Concept 10.3.1 · Probability Recursions

For probability recursions, it can be a good idea to simply make a table and find the probability of being at each location after every time step. Remember: the total probability after each hop must always be $1$ .

Watch itpredict, then reveal

Example 10.4

AMC 8

A cricket randomly hops between 4 leaves, on each turn hopping to one of the other 3 leaves with equal probability. After 4 hops what is the probability that the cricket has returned to the leaf where it started?

After 0 hops: back on A =

1

Chance of each leaf after every hop
Hop	A★	each other	all leaves (total = 1)
0	1	0

Each bar is split by leaf colour. Every bar is full: the chances always add up to 1.

1
Call the starting leaf A. Let $p_k$ be the chance the cricket is on A after $k$ hops. So $p_0 = 1$ . What is $p_1$ ?

Predict first:
Your prediction

open on YouTube

Checkpoint for section 10.3

Get 2 of 3 right to master this section. One try each, no hints.

10.4

Practice Problems

In this section you will be able to use recursion on a tough contest problem.

Here’s an AIME problem about building towers. The trick: grow the tower one cube at a time, and count where each new cube can go.

Want every problem from this chapter on one page? Open the problem set.

Contest cornerreal contest problems

Problem 10.4.5

AIME

A collection of 8 cubes consists of one cube with edge-length $k$ for each integer $k$ , $1 \le k \le 8$ . A tower is to be built using all 8 cubes according to the following rules: Any cube may be the bottom cube in the tower. The cube immediately on top of a cube with edge-length $k$ must have edge-length at most $k + 2$ . How many towers can be constructed?