C. Discrete Functions · Sequences and SeriesRecursive Procedures: Building a Sequence Step by Step
C1.2 C1.3 C1.4About 70 minutes
Learning goals- I can describe, in words and with a flow chart, a recursive procedure that generates a sequence.
- I can write a recursion formula using t₁ and tₙ₋₁.
- I can write terms of a sequence from a recursion formula.
- I can represent a sequence with a table of values and a graph.
Words to know
recursive procedure
A process that makes each new term by doing something to the term (or terms) before it.
recursion formula
A rule that gives the first term(s) and a formula for tₙ using earlier terms, e.g. t₁ = 1, tₙ = tₙ₋₁ + n.
tₙ₋₁
The term just before tₙ (the previous term). tₙ₋₂ is two terms before.
triangular numbers
1, 3, 6, 10, 15, 21, …: the numbers of dots that make triangles of 1, 2, 3, … rows.
flow chart
A diagram of boxes and arrows that shows the steps of a procedure in order, including steps that repeat.
Racking up the pins
In ten-pin bowling, the pins stand in a triangle: 1 pin in the front row, then 2, then 3, then 4. That makes 1 + 2 + 3 + 4 = 10 pins. If the triangle had 5 rows, it would need 15 pins; with 6 rows, 21 pins.
The numbers 1, 3, 6, 10, 15, 21, … are called the triangular numbers. Can you see how to get each one from the one before it? You add 2, then 3, then 4, then 5, then 6. Building a sequence this way, one step at a time from the previous term, is called a recursive procedure.
Describing a recursive procedure
A recursive procedure always has two parts:
- Where to start: the first term (or first few terms).
- How to get the next term from the term(s) before it.
You can describe it in words: "Start with 1. To get each new term, add its position number to the previous term."
You can also draw a flow chart. The loop in the chart repeats the same step over and over, which is exactly what a recursive procedure does.
Recursion formulas
Mathematicians write a recursive procedure as a recursion formula. We use tₙ₋₁ for the term just before tₙ.
For the triangular numbers:
t₁ = 1, tₙ = tₙ₋₁ + n, for n > 1
Read it as: "The first term is 1. Each term after that is the previous term plus n." Let's check: t₂ = t₁ + 2 = 3, t₃ = t₂ + 3 = 6, t₄ = t₃ + 4 = 10. ✓
A recursion formula needs both parts. Without t₁ = 1, the rule tₙ = tₙ₋₁ + n could start anywhere and give a different sequence.
Worked exampleExample 1: From terms to a recursion formula
Write a recursion formula for each sequence, and describe it in words.
(a) 5, 8, 11, 14, … (b) 3, 6, 12, 24, … (c) 2, 3, 5, 9, 17, …
- (a) Each term is 3 more than the one before: 8 − 5 = 11 − 8 = 3. t₁ = 5, tₙ = tₙ₋₁ + 3. In words: start at 5 and keep adding 3.
- (b) Each term is double the one before: 6 ÷ 3 = 12 ÷ 6 = 2. t₁ = 3, tₙ = 2tₙ₋₁. In words: start at 3 and keep doubling.
- (c) The differences are 1, 2, 4, 8, so it is not "add the same number". Try doubling: 2 × 2 = 4, one more than 3; 3 × 2 = 6, one more than 5. Try "double and subtract 1": 2(2) − 1 = 3, 2(3) − 1 = 5, 2(5) − 1 = 9, 2(9) − 1 = 17 ✓. t₁ = 2, tₙ = 2tₙ₋₁ − 1.
(a) t₁ = 5, tₙ = tₙ₋₁ + 3 (b) t₁ = 3, tₙ = 2tₙ₋₁ (c) t₁ = 2, tₙ = 2tₙ₋₁ − 1
Worked exampleExample 2: From a recursion formula to terms
Write the first five terms of t₁ = 4, tₙ = 3tₙ₋₁ − 5.
- t₁ = 4 (given).
- t₂ = 3t₁ − 5 = 3(4) − 5 = 7
- t₃ = 3t₂ − 5 = 3(7) − 5 = 16
- t₄ = 3(16) − 5 = 43
- t₅ = 3(43) − 5 = 124
Worked exampleExample 3: A recursion formula that uses n
Write the first five terms of t₁ = 2, tₙ = tₙ₋₁ + 2n, and describe the pattern you see.
- t₂ = t₁ + 2(2) = 2 + 4 = 6
- t₃ = t₂ + 2(3) = 6 + 6 = 12
- t₄ = 12 + 8 = 20, t₅ = 20 + 10 = 30
- Pattern: 2 = 1 × 2, 6 = 2 × 3, 12 = 3 × 4, 20 = 4 × 5, 30 = 5 × 6. Each term is its position times the next number: tₙ = n(n + 1). (Each term is also double a triangular number.)
Tables and graphs
A sequence is a discrete function, so we can show it as a table of values and as a graph of points. The table below adds a column of first differences (each term minus the previous term). For the triangular numbers, the first differences are 2, 3, 4, 5, 6, which is the recursive rule "add n" showing up in the table. The second differences are all 1. Remember from Grade 10: constant second differences mean the pattern is quadratic, so the graph curves upward like half a parabola.
| n | tₙ | first difference | second difference |
|---|
| 1 | 1 | | |
| 2 | 3 | 2 | |
| 3 | 6 | 3 | 1 |
| 4 | 10 | 4 | 1 |
| 5 | 15 | 5 | 1 |
| 6 | 21 | 6 | 1 |
Recursion with technology
Spreadsheets are made for recursion. Put 1 in cell A1 (n) and 1 in cell B1 (t₁). In A2 type =A1+1, and in B2 type =B1+A2 (previous term plus n). Fill both cells down. Each row uses the row above, exactly like tₙ = tₙ₋₁ + n. The same idea works in a graphing calculator's sequence mode or a short program loop.
Just for funTo understand recursion, you must first understand recursion.
(Don't worry: unlike that sentence, every recursion formula in this unit comes with a first term, so it knows where to stop looking back.)
Hands-on activityCoin triangles and squares
You need: about 40 small identical objects (coins, buttons, dried beans or cereal pieces) and paper.
- Build triangles of 1, 2, 3, 4 and 5 rows. Count the objects in each. You should get the triangular numbers.
- Now build squares: 1 × 1, 2 × 2, 3 × 3, 4 × 4. How many objects do you add each time to go from one square to the next?
- Write a recursion formula for the square numbers 1, 4, 9, 16, 25, ….
- Put two triangles of the same size side by side, one flipped. What shape do they almost make?
What to look for: to go from an (n − 1) × (n − 1) square to an n × n square you add an L-shape of 2n − 1 objects (3, 5, 7, 9, …). So the square numbers follow t₁ = 1, tₙ = tₙ₋₁ + 2n − 1. Two equal triangles of n rows fit together to make an n by (n + 1) rectangle, which shows that the nth triangular number is n(n + 1)/2.
Your turn
1Write a recursion formula for 7, 11, 15, 19, ….
2Write a recursion formula for 80, 40, 20, 10, ….
Each term is half the one before: t₁ = 80, tₙ = tₙ₋₁ ÷ 2 (or tₙ = 0.5tₙ₋₁).
3Write the first five terms of t₁ = 6, tₙ = tₙ₋₁ − 4.
4Write the first five terms of t₁ = 1, tₙ = 2tₙ₋₁ + 3.
t₂ = 2 + 3 = 5, t₃ = 13, t₄ = 29, t₅ = 61. So 1, 5, 13, 29, 61.
5Describe in words the recursive procedure for t₁ = 10, tₙ = tₙ₋₁ + 2n.
Start with 10. To get each new term, add twice its position number to the previous term. (Terms: 10, 14, 20, 28, 38, …)
6Find the 8th triangular number using the recursive rule and t₆ = 21.
t₇ = 21 + 7 = 28 and t₈ = 28 + 8 = 36.
7Write a recursion formula for 1, 2, 6, 24, 120, ….
Ratios: 2 ÷ 1 = 2, 6 ÷ 2 = 3, 24 ÷ 6 = 4, 120 ÷ 24 = 5. Each term is the previous term times its position: t₁ = 1, tₙ = n × tₙ₋₁. (These are the factorials, 1!, 2!, 3!, ….)
More practice: warm-up
1In the recursion formula tₙ = tₙ₋₁ + 5, what does tₙ₋₁ mean?
The previous term, the one just before tₙ.
2Write the first four terms of t₁ = 2, tₙ = tₙ₋₁ + 9.
3Write the first four terms of t₁ = 5, tₙ = 3tₙ₋₁.
4What two parts does every recursion formula need?
A starting term (or terms) and a rule that gives each term from earlier term(s).
5Write a recursion formula for 100, 90, 80, 70, ….
More practice: on your own
1Write a recursion formula for 3, 4, 6, 9, 13, 18, ….
Differences: 1, 2, 3, 4, 5, so you add one less than the position each time: t₁ = 3, tₙ = tₙ₋₁ + (n − 1). Check: t₂ = 3 + 1 = 4, t₆ = 13 + 5 = 18 ✓.
2Write the first five terms of t₁ = 64, tₙ = −tₙ₋₁ ÷ 2.
64, −32, 16, −8, 4. Each step halves the term and changes its sign.
3A sequence has t₁ = 3 and tₙ = tₙ₋₁² − 2. Find t₄.
t₂ = 9 − 2 = 7, t₃ = 49 − 2 = 47, t₄ = 47² − 2 = 2209 − 2 = 2207.
4Write a recursion formula for 2, 5, 11, 23, 47, ….
Each term is double the previous plus 1: 2(2) + 1 = 5, 2(5) + 1 = 11, 2(11) + 1 = 23, 2(23) + 1 = 47 ✓. t₁ = 2, tₙ = 2tₙ₋₁ + 1.
5Draw (or describe) a flow chart that generates 5, 8, 11, 14, … and stops after 10 terms.
Start → set t = 5, n = 1 → write down t → is n = 10? If yes, stop. If no: n = n + 1, t = t + 3, and go back to "write down t". (Look for: a starting box, an output step, a decision that stops the loop, and the update t = t + 3.)
Challenge
1The sequence 1, 3, 6, 10, 15, … satisfies tₙ = tₙ₋₁ + n. Use the idea of the activity (two triangles make a rectangle) to find t₅₀ without listing terms.
Two copies of a 50-row triangle make a 50 × 51 rectangle, so t₅₀ = 50 × 51 ÷ 2 = 1275.
2A recursion formula is t₁ = k, tₙ = 3tₙ₋₁ − 4. For which value of k is every term the same?
For every term to be equal, t₂ = t₁: 3k − 4 = k → 2k = 4 → k = 2. Check: 3(2) − 4 = 2, so the sequence is 2, 2, 2, …
3A sequence uses two previous terms: t₁ = 2, t₂ = 5, tₙ = tₙ₋₁ + tₙ₋₂. Write the first eight terms, then say which of them are even.
2, 5, 7, 12, 19, 31, 50, 81. The even terms are 2, 12 and 50: t₁, t₄ and t₇, every third term. (odd + odd = even and even + odd = odd, so the pattern even, odd, odd repeats.)
Quiz
1. What are the first four terms of t₁ = 3, tₙ = tₙ₋₁ + 6?
2. Which recursion formula generates 4, 12, 36, 108, …?
3. In a recursion formula, tₙ₋₁ stands for:
4. For t₁ = 2, tₙ = 2tₙ₋₁ + 1, what is t₄?
5. The triangular numbers follow t₁ = 1, tₙ = tₙ₋₁ + n. What is t₇?
6. Why must a recursion formula include a starting term?
Big idea: Expectation C1.2 asks students to find and describe a recursive procedure (in words or with a flow chart) from the first few terms, using the curriculum's own example of the triangular numbers 1, 3, 6, 10, 15, 21, …, and to show sequences as tables and graphs. This lesson also starts C1.3 and C1.4 by writing terms from recursion formulas.
How to help: Recursion is "what do I do to the last one to get the next one?" Give your teen a short list (like 2, 6, 18, 54) and ask for the rule in plain words first, then in symbols. A spreadsheet that fills down a recursive formula makes the idea very concrete.
Common difficulties:
- Forgetting the starting term t₁.
- Reading tₙ₋₁ as "tₙ minus 1". It means the previous term.
- Assuming every sequence adds a constant. Check differences and ratios, and also try "multiply then add" (Example 1c).
- Arithmetic slips in long recursions. Each term depends on the last, so one mistake carries forward. Check each step.