• Review
• Expand 3𝑥 + 2𝑦 7
4 2 6
• Find the coefficient of 𝑎 𝑏 in the expansion of 4𝑎 − 5𝑏
• Use the binomial theorem to find the coefficient of 𝑎
𝑥 𝑦 𝑏 in the expansion
3 4 12
of 𝑥 − 4𝑦 where a = 15, b = 28
MODULE 4
R ECURSION AND S EQUENCES
This module discusses sequences expressed either by explicit formula or by
recurrence relations with the initial condition. It also illustrates how to generate a
sequence from a given formula. It also identifies some common types of sequence.
At the end of this module, you must:
1. Differentiate finite and infinite sequences.
2. Identify a recursive sequence.
3. Construct a recursive formula and an explicit formula for a given sequence of
numbers.
4. Identify the common types of sequence.
S EQUENCE
A sequence is an ordered list of numbers.
Example 1:
Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, …
The dots mean that there are more numbers in the sequence.
Infinite sequence - a sequence that does not end.
Term of a sequence- number in a sequence separated by commas.
𝐹0 = 0 𝐹1 = 1 𝐹2 = 1 𝐹3 = 2 𝐹4 = 3 𝐹5 = 𝐹4 + 𝐹3 𝐹𝑛 = 𝐹𝑛 − 1 + 𝐹𝑛 − 2
The first term in the Fibonacci sequence is 1; the second term is 2 and so on.
The notation an or Fn in Fibonacci sequence is used to designate the nth term of a sequence.
A rule or a formula that can be used to generate all the terms of a sequence describes the nth-term formula
or general term.
Example 2:
The nth-term of a sequence is given by an = 3n – 2.
Find the first four terms, the tenth term and the 15th term.
Solution
a1 = 3(1) – 2 = 1 a2 = 3(2) – 2 = 4 a3 = 3(3) – 2 = 7 a4 = 3(4) – 2 = 10
a10 = 3(10) – 2 = 28 a15 = 3(15) – 2 = 43 a7 = 3(7) – 2 = 19 a31 = 3(31) – 2 = 91
RECURSIVE SEQUENCE
It is also known as a recurrence sequence. In a recursively defined sequence, each term is related to
the previous term by a rule or formula with some initial conditions.
Example 1: Fibonacci sequence is an example of a recursively defined sequence with two initial condition:
F0 = 0; F1 = 1; Fn = Fn - 1 + Fn - 2
The next four terms in the sequence are the following:
F2 = F1 + F0 = 1 + 0 = 1
F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 = 2 + 1 = 3
F5 = F4 + F3 = 3 + 2 = 5
Learning task 4.2
Explicit Formula and Recurrence Relation
The ancient Greek mathematicians were
fascinated with geometric shapes associated
with numbers so they created the following
sequence and figures, Aufmann et al (2013).
Triangular numbers:
1, 3, 6, 10, 15, . . ., n(n+1)/2
Square Numbers:
1, 4, 9, 16, 25, . . ., n2
Pentagonal numbers:
1, 5, 12, 22, 35, . . . , n(3n – 1)/2
For some sequence, we may know the first few terms but not the general term. In such case,
we may look for a pattern.
Example:
For each sequence, find a general term.
a. -1, 2, -4, 8, -16, ...
b. 1, 3, 5, 7, . . .
Solution
a. -1, 2, -4, 8, -16, ...
For the negative sign, we have (-1 )n . For the numbers, we have the powers of two with the
general term of an = (2n–1)Thus the general term would be an = (-1 )n (2n–1)
b. 1, 3, 5, 7,...
The numbers are odd so the general form would be an = 2n – 1.
B INOMIAL NUMBERS
The binomial numbers are considered triangular sequence called Pascal’s triangle. In the triangle, the
rows are represented by n and columns are represented by r from left to right.
Example: =10
ARITHMETIC SEQUENCE
It is also known as arithmetic progression and is discrete analogue of the linear function
f(x) = dx + a.
Form: a, a + d, a + 2d, ..., a + nd, .... where the initial term (first term) a and the common
difference d are real constants.
The explicit formula is an = a + nd,n, r N
The recurrence relation is n, r N = {a if n = 0 or an - 1 + d if n > 0
Example 1:
4, 7, 10, 13, 16, . . . is an arithmetic sequence generated by a = 4, and d = 3
Example 2:
Find the first term, common difference and the 10th term of the arithmetic sequence:
2, 8, 14, 20, ...
Solution:
a0 = 2 a1 = 8 = 2 + 1*6 a2 = 14 = 2 + 2*6
a3 = 20 = 2 + 3*6 an = 2 + n*6
a = 2, d = 6, a10 = 2 + 10(6) = 62
Example: 3, 8, 13, 18,…
a0 = 3 a1 = 3 + 5*1
d=5 an = 3 + 5n
GEOMETRIC SEQUENCE
It is also known as geometric progression and is discrete analogue of the exponential
function f(x) = arx
Form: a, ar, ar2, ar3 , ...., arn , ... where the initial term (first term) a and the common
ratio (r) are real constant.
The explicit formula is an = arn , n N
The recurrence relation isn, r N = {a if n = 0 or arn -1 if n > 0.
Example1:
The power sequence 1, 2, 4, 8, 16, ... is a geometric sequence generated by a = 1, r = 2.
an = 2n-1 a1 = 21-1 a2 = 22-1 = 2 a3 = 23-1 = 4 a7 = 27-1 = 64
Example 2:
Find the initial term, common ratio and 6th term of the geometric sequence:
4, 8, 16, 32, ....
Solution:
a1 = 4 = 2*2 a2 = 8 = 2*2*2 = 2*22
a3 = 16 = 2*2*2*2 = 2*23 an = 2*2n
a = 4, r = 2, a6 =2(2)6 =128
Learning task 4.3
In conclusion:
An infinite sequence has no end.
Recursive sequence has an initial condition or first term and the formula in related to the
previous term.
Explicit formula for a given sequence of numbers can be done using the pattern in the
first few terms or using the arithmetic or geometric sequence.
Some common types of sequence.
1. triangular numbers 5. square numbers
2. pentagonal numbers 6. binomial numbers
3. arithmetic sequence 7. geometric sequence
4. Fibonacci numbers
THANK YOU