10. Recursion · Mastering AMC 10/12

10.10%

Recursion Fundamentals

In this section you will be able to count the ways to climb a staircase by building each answer from the smaller ones.

Jeff climbs a 6-stair staircase, 1 or 2 stairs at a time. Listing every climb is slow. Can you count them without listing?

Don’t attack stair 6 head-on. Ask a smaller question: how many ways reach stair 1? Stair 2? Then ask how the last jump onto a stair can start. That turns one big count into a chain of small ones.

Look:every climb to stair

n

ends with a single jump. Sort the climbs by where that jump starts.

Exploreplay first, formulas later

Try this: Press Fill the next stair until you reach f(6). Which two cells feed each new one?
Try this: Press Show a climb a few times. Is the last jump always a 1 or a 2? Why does that give f(n) = f(n − 1) + f(n − 2)?
Try this: Turn on jump 3 as well (that's Problem 10.5.1). Which cells feed f(6) now?

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 · Fibonacci?

Look: the numbers $1, 2, 3, 5, 8, 13$ follow the Fibonacci sequence. That's because the recursion $f(n) = f(n-1) + f(n-2)$ is the same as Fibonacci's. This is not the case for every recursion problem.

Remark 10.1.3 · Engineering induction

You can often get the answer to a recursion problem by engineering induction: work out the first few values, spot the pattern, and trust it. (See the meta-solving section in Chapter 45.)

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
Casework would take a long time. Start small instead. How many ways are there for Jeff to reach the 0th stair (the ground)?

Predict first:
Your prediction

Try it

Problem 10.5.1

AMC

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 set up base cases and a recursion when the rules change along the way.

Mike takes 2 or 3 stairs at a time, but from stair 9 he may take a single step to the top. One special rule at the end. Does it break the recursion?

Every recursion problem runs the same four steps: base cases by hand, a recursion from the ways to arrive, then the values one by one. Special rules just change which cells you add, and where.

Look:a recursion that reaches back 3 steps needs 3 base cases before it can run on its own.

Exploreplay first, formulas later

stairs10

jumps:

Find f(10): the ways to reach stair 10

Jumps of 2 or 3; the last jump onto stair 10 may be 1, 2 or 3.

Try this: Fill the first stairs. Why is f(1) = 0 for Mike?
Try this: The last jump may be a 1. Select the top cell: which three cells add up to it?
Try this: Turn off "Last jump may be 1, 2 or 3". How does the top change? That's the trap in Example 10.2.

Name it

Concept 10.2.1 · The recursion method

Solving a problem with recursion is a multi-step process:

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

Remark 10.2.2 · f(0) = 1

You can also use $f(0) = 1$ as a base case: to get to the 0th stair you take no steps, and there is exactly 1 way to do that. It can be faster, though a bit confusing at first, so the examples don't use it. Feel free to use it in the problems.

Remark 10.2.3 · More base cases never hurt

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)$ ), go back and count more base cases by hand.

Watch itpredict, then reveal

Example 10.2

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 base cases. How many ways can Mike reach the 1st stair?

Predict first:
Your prediction

Checkpoint for section 10.2

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

10.30%

More Complex Recursions

In this section you will be able to find recursions by inserting the newest object, or by asking what happens to the last one.

Eight cubes, sizes 1 to 8, stacked so each cube is at most 2 bigger than the one below. There are thousands of orders. How many work?

The staircase trick still works when the objects aren’t stairs. Build a size- $n$ answer from a size- $(n-1)$ answer. For towers, insert the biggest cube into a smaller tower. For sets, ask whether $n$ itself is in or out.

Look:if every big arrangement comes from exactly one small one, the counts just multiply.

Exploreplay first, formulas later

Try this: Insert cube 4 into the tower of 1–3. How many places are legal?
Try this: Keep inserting. Does the number of legal places change once n ≥ 3? Look at the ×3 under the table.
Try this: Press Take out a few times. Is what's left always a legal tower?

Name it

Remark 10.3.1 · Check your recursion

To check your recursive equation, count a few small cases by hand and see whether the recursion gives the same numbers.

Watch itpredict, then reveal

Example 10.3

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 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$ .

Let $T$ be the number of different towers that can be constructed. What is the remainder when $T$ is divided by 1000?

1
Let $T(n)$ be the number of legal towers using cubes $1$ to $n$ . What is $T(2)$ ?

Predict first:
Your prediction

open on YouTube

Example 10.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?

n3

Spacy sets: at most one of any three in a row

a(3): n is chosen · 1

{3}

b(3): n is not chosen · 3

∅
{2}
{1}

a(3) = 1: a base case, counted by handb(3) = 3: a base case, counted by handtotal for n = 3: a(3) + b(3) = 4

Dashed columns are base cases, counted by hand. Outlined cells feed the selected column.

1
Let $S(n)$ be the number of spacy subsets of $\{1, \ldots, n\}$ . Count $S(1)$ , $S(2)$ and $S(3)$ by hand. What is $S(3)$ ?

Predict first:
Your prediction

open on YouTube

Contest cornerreal contest problems

Problem 10.5.5(additional)

AIME

Call a permutation $a_1, a_2, \ldots, a_n$ of the integers $1, 2, \ldots, n$ quasi-increasing if $a_k \le a_{k+1} + 2$ for each $1 \le k \le n-1$ . For example, $53421$ and $14253$ are quasi-increasing permutations of the integers $1, 2, 3, 4, 5$ , but $45123$ is not. Find the number of quasi-increasing permutations of the integers $1, 2, \ldots, 7$ .

Problem 10.5.8(additional)

AIMEChallenge

Find the number of permutations of $1, 2, 3, 4, 5, 6$ such that for each $k$ with $1 \le k \le 5$ , at least one of the first $k$ terms of the permutation is greater than $k$ .

Checkpoint for section 10.3

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

10.40%

Multiple Recursions

In this section you will be able to track two counts at once, split by how the string ends.

A mail carrier on a street of 19 houses never delivers to two neighbors, and never skips three houses in a row. How many delivery patterns are possible?

One count isn’t enough here: what can come next depends on how the pattern ends. So keep two counts, $a(n)$ for patterns ending with mail and $b(n)$ for patterns ending without. Each one feeds the other.

Look:the answer is a combination of the two counts, here

a(19) + b(19)

.

Exploreplay first, formulas later

modoff

n4

Mail: no two neighbors, never three without

a(4): last house gets mail · 2

b(4): last house gets no mail · 3

a(4) = b(3) = 2b(4) = a(3) + a(2) = 2 + 1 = 3total for n = 4: a(4) + b(4) = 5

Dashed columns are base cases, counted by hand. Outlined cells feed the selected column.

Try this: Look at the list for n = 4. A pattern ends with mail: what must the house before it be?
Try this: A pattern ends without mail: how far back can the last mail be? Select n = 6 and check which cells light up.
Try this: Switch to Runs ≤ 3, then set mod to 12. Look at the note under the table: how often do the totals repeat?

Name it

Concept 10.4.1 · Two recursive functions

Often it is simpler to define two recursive functions, say $a(n)$ and $b(n)$ , where the actual answer is some combination of the two (for example $a(n) + b(n)$ ).

Watch itpredict, then reveal

Example 10.5

AIME 2001

A mail carrier delivers mail to the nineteen houses on the east side of Elm Street. The carrier notices that no two adjacent houses ever get mail on the same day, but that there are never more than two houses in a row that get no mail on the same day. How many different patterns of mail delivery are possible?

n3

Mail: no two neighbors, never three without

a(3): last house gets mail · 2

b(3): last house gets no mail · 2

a(3) = b(2) = 2b(3) = a(2) + a(1) = 1 + 1 = 2total for n = 3: a(3) + b(3) = 4

Dashed columns are base cases, counted by hand. Outlined cells feed the selected column.

1
Let $a(n)$ count the patterns for $n$ houses where the last house gets mail, and $b(n)$ those where it doesn't. If the last house gets mail, what must the house before it be?

Predict first:
Click a choice or type its letter (A–E).

Contest cornerreal contest problems

Problem 10.5.3(additional)

AIME

There are $2^{10} = 1024$ possible 10-letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than 3 adjacent letters that are identical.

n4

A/B strings, at most 3 equal letters in a row

f(4): ends in A · 7

BBBA
BBAA
BABA
BAAA
ABBA
ABAA
AABA

g(4): ends in B · 7

BBAB
BABB
BAAB
ABBB
ABAB
AABB
AAAB

f(4) = g(3) + g(2) + g(1) = 4 + 2 + 1 = 7g(4) = f(3) + f(2) + f(1) = 4 + 2 + 1 = 7total for n = 4: f(4) + g(4) = 14

Dashed columns are base cases, counted by hand. Outlined cells feed the selected column.

Problem 10.5.4(additional)

AMC 12

For each positive integer $n$ , let $S(n)$ be the number of sequences of length $n$ consisting solely of the letters $A$ and $B$ , with no more than three $A$ s in a row and no more than three $B$ s in a row. What is the remainder when $S(2015)$ is divided by 12?

mod12

n4

A/B strings, at most 3 equal letters in a row

f(4) = g(3) + g(2) + g(1) ≡ 4 + 2 + 1 ≡ 7g(4) = f(3) + f(2) + f(1) ≡ 4 + 2 + 1 ≡ 7total for n = 4: f(4) + g(4) ≡ 2 (mod 12)

Mod 12, the totals repeat every 52 columns.

Dashed columns are base cases, counted by hand. Outlined cells feed the selected column.

Checkpoint for section 10.4

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

10.5

Practice Problems

In this section you will be able to use recursion on games, rings and shrinking triangles.

Three challenge problems. A brick game, a painted ring and a triangle that keeps shrinking: each one hides a recursion.

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

Contest cornerreal contest problems

Problem 10.5.2

AMC 10/12Challenge

This problem also appears in the book as 3.3.14.

Arjun and Beth play a game in which they take turns removing one brick or two adjacent bricks from one "wall" among a set of several walls of bricks, with gaps possibly creating new walls. The walls are one brick tall. For example, a set of walls of sizes $4$ and $2$ can be changed into any of the following by one move: $(3, 2)$ , $(2, 1, 2)$ , $(4)$ , $(4, 1)$ , $(2, 2)$ , or $(1, 1, 2)$ .

Arjun plays first, and the player who removes the last brick wins. For which starting configuration is there a strategy that guarantees a win for Beth?

Problem 10.5.6(additional)

AIMEChallenge

The figure below shows a ring made of six small sections which you are to paint on a wall. You have four paint colors available and you will paint each of the six sections a solid color. Find the number of ways you can choose to paint the sections if no two adjacent sections can be painted with the same color.

Problem 10.5.7(additional)

AMC 12Challenge

Let $\triangle A_0B_0C_0$ be a triangle whose angle measures are exactly $59.999^\circ$ , $60^\circ$ , and $60.001^\circ$ . For each positive integer $n$ , define $A_n$ to be the foot of the altitude from $A_{n-1}$ to line $B_{n-1}C_{n-1}$ . Likewise, define $B_n$ to be the foot of the altitude from $B_{n-1}$ to line $A_{n-1}C_{n-1}$ , and $C_n$ to be the foot of the altitude from $C_{n-1}$ to line $A_{n-1}B_{n-1}$ . What is the least positive integer $n$ for which $\triangle A_nB_nC_n$ is obtuse?