AST21111

Discrete Mathematics

5. Sequences, Mathematical
Induction and Recursion

1
 Sequences
A sequence is an ordered list of numbers, typically it is
written as follows.

Each individual element ak is called a term. The k in ak is

called an index. am is initial term and an is the final term.

The notation

Denote an infinite sequence.

Note that each sequence has a function that governs how
the values of ak depend on k.
2
 Sequences
e.g.
Given a sequence a1, a2, a3,…, where

Show the first five terms of the sequences.

Solution:

So the sequence is ,… 3
 Arithmetic Progression
Definition:
An arithmetic progression is a sequence of the form:
a, a + d, a + 2d, …, a + nd, … where the initial term a and the
common difference d are real numbers for n ≥ 0.

Example:
Let a = −1 and d = 4. The governing function is a + kd for k ≥
0.
a0 = -1 + 0(4) = -1, a1 = -1 + 1(4) = 3, a2 = -1 + 2(4) = 7,
a3 = -1 + 3(4) = 11
So a0, a1, a2, a3,… = -1, 3, 7, 11, … 4
 Geometric Progression
Definition:
A geometric progression is a sequence of the form:
a, ar, ar2, …, arn, … where the initial term a and the
common ratio r are real numbers for n ≥ 0.

Example:
Let a = 1 and r = 2. The governing function is ark for k ≥ 0.
a0 = ar0 = 1, a1 = ar1 = 2, a2 = ar2 = 4, a3 = ar3 = 8

So a0, a1, a2, a3,… = 1, 2, 4, 8, …

5
 Summation Notation

e.g. Let a1 = −2, a2 = −1, a3 = 0, a4 = 1, and a5 = 2.

6
 Product Notation

e.g.

7
 Product Notation
e.g. Compute the following products:
a) b) b)

Solution:
a)

b)

8
 Properties of Summations
and Products
The general properties of summations and products are
as follows.

9
Mathematical Induction

10
 Mathematical Induction
In general, mathematical induction is a method for proving
that a property is true for all integers n ≥ some initial integer.
The Principle of Mathematical Induction is like pushing the
first domino in an infinite sequence of dominoes.

11
 Mathematical Induction
Consider an infinite sequence of standing dominoes,
labeled 1, 2, 3, …, n, …

Let P(n) be “the n-th domino is knocked over”.

1. If the 1-st domino is knocked over, that is, P(1) is true.
2. Whenever the k-th domino is knocked over, it also knocks
the (k + 1)-st domino over.
That is, P(k) → P(k + 1) is true for all positive integers k.

Hence, we can conclude that all dominoes are knocked

over, that means “P(n) is true for all positive integers n”.
12
 Mathematical Induction
Method of Proof by Mathematical Induction

To prove that P(n) is true for all positive integers n ≥ a,

we complete 2 steps:
Step 1 (Basis Step): show that P(a) is true.
Step 2 (Inductive Step): show that P(k) → P(k + 1) is
true for all k ≥ a.

13
 Mathematical Induction
Theorem 5.1
For all integers n ≥ 1, .

Proof:
Let P(n) be “the sum of the integers from 1 to n equals .”
Basis step: (To show that P(1) is true.)
We know that the sum of the integers from 1 to 1 = 1
Now for n = 1, on the R.H.S. =
L.H.S. = R.H.S., hence P(1) is true.
14
 Mathematical Induction
Inductive Step: (Show that for all integers k ≥ 1, if P(k) is true
then P(k + 1) is also true.)

Suppose that k is any integer with k  1 such that

P(k) : is true.

Based on that, we must show that

P(k + 1): 1 + 2 + 3 … + k + (k + 1) is true.

15
 Mathematical Induction
Note that the L.H.S. of P(k + 1):

1 + 2 + 3 … + k + (k + 1)

= R.H.S. of P(k + 1) 16
 Mathematical Induction
Theorem 5.2
For any real number r except 1, and any integer n ≥ 0,
the sum of geometric sequence

Proof:
Let P(n) be

17
 Mathematical Induction
Basis step: (To show that P(0) is true.)

On the L.H.S. of P(0), when n = 0 the sum = 1.

Now on the L.H.S. of P(0),

R.H.S = L.H.S, so P(0) is true.

18
 Mathematical Induction
Inductive Step: (Show that for all integers k ≥ 0, if P(k) is
true then P(k + 1) is also true.)

Suppose k be any integer with k  0 such that

P(k): is true.

Based on that, we must show that

P(k + 1): is also true.

19
 Mathematical Induction
Note that the L.H.S. of P(k + 1):

20
Mathematical Induction

= R.H.S. of P(k + 1)

21
 Proving Divisibility Results
Proposition 5.3
For all integers n  0, 22n – 1 is divisible by 3.

Proof:
Let P(n) be “22n – 1 is divisible by 3.”
Basis step: (To show that P(0) is true.)

When n = 0, 22(0) – 1 = 20 – 1 is divisible by 3.

So P(0) is true.

22
 Proving Divisibility Results
Inductive Step: (Show that for all integers k ≥ 0, if P(k) is
true then P(k + 1) is also true.)

Suppose that k ≥ 0 such that

P(k): “ 22k – 1 is divisible by 3.” is true.

Based on that, we must show that

P(k + 1): “ 22(k+1) – 1 is divisible by 3.” is true.

23
 Proving Divisibility Results
By definition of divisibility and the truth of P(k),
22k – 1 = 3r for some integer r.
Now,
22(k+1) – 1 = 22k+2 – 1
= 22k(4) – 1
= 22k(3 + 1) – 1
= 22k(3) + 22k – 1
= 22k(3) + 3r
= 3(22k + r)
Therefore 22(k+1) – 1 is divisible by 3.
24
 Proving an Inequality
Proposition 5.4
For all integers n  3, 2n + 1 < 2n.

Proof:
Let P(n) be “2n + 1 < 2n.”
Basis step: (To show that P(3) is true)

L.H.S. of P(3): 2(3) + 1 = 7

R.H.S. of P(3): 23 = 8
L.H.S. < R.H.S., hence P(3) is true.
25
 Proving an Inequality
Inductive Step: (Show that for all integers k ≥ 3, if P(k) is
true then P(k + 1) is also true.)

Suppose that k ≥ 3 such that

P(k): 2k + 1 < 2k is true.

Based on that, we must show that

P(k + 1): 2(k + 1) + 1 < 2(k+1) is true.

26
 Proving an Inequality
Note that
2(k + 1) + 1 = (2k + 1) + 2
< 2k + 2
< 2k + 2k 2 < 2k, when k ≥ 3
= 2(2k)
= 2(k+1)

So, 2(k + 1) + 1 < 2(k+1)

27
 Strong Mathematical
Induction
 A proof by strong mathematical induction also
consists of a basis step and an inductive step.

 The basis step may contain proofs for several initial

values.

 In the inductive step, the truth of P(n) is assumed not

just for one value of k, but for all values through k.

28
 Strong Mathematical
Induction
The Principle of Strong Mathematical Induction is as follows.

Let P(n) be a property that is defined for integer n, and let a

and b be fixed integers with a ≤ b.

If the following two statements are true:

1) Basis Step: P(a), P(a+1), …, and P(b) are all true.
2) Inductive Step: for any integer k ≥ b, (P(1) ∧ P(2) ∧ ∙∙∙ ∧
P(k)) → P(k + 1) is true.
then the statement: for all integers n ≥ a, P(n) is true.
29
 Strong Mathematical
Induction
Theorem 5.5
Any integer n > 1 is divisible by a prime number.

Proof:
Let P(n) be “n is divisible by a prime number.”

Basis step: (To show that P(2) is true.) (where a = b = 2)

As 2 is divisible by 2 and 2 is a prime number, so P(2) is
true.

30
 Strong Mathematical
Induction
b=2
Inductive Step:
(Show that for all integers k ≥ 2, if P(i) is true for all integers
i from 2 to k, then P(k + 1) is also true.)

Let k be any integer with k  2 and

suppose that i is divisible by a prime number for all integers
i from 2 to k. (i.e., (P(2) ∧ P(3) ∧ ∙∙∙ ∧ P(k)) is true.)
a=2
Based on that we need to show that
P(k + 1): “k + 1 is divisible by a prime number.” is true.
31
 Strong Mathematical
Induction
We have 2 cases:

Case 1 (k + 1 is prime):
k + 1 is divisible by a prime number, namely itself. So, in
this case, P(k + 1) is certainly true.

Case 2 (k + 1 is not prime):

k + 1 = cd, where c and d are integers with
1 < c < k + 1 and 1 < d < k + 1.
Note that c and d are divisible by some primes as we
assume P(c) and P(d) are true.
32
 Strong Mathematical
Induction
Since k + 1 is divisible by c and c is divisible by a prime
number p,

by Theorem 3.6 (transitivity of divisibility), k + 1 is

divisible by a prime number p.

Therefore, regardless of whether k + 1 is prime or not, it

is divisible by a prime number.

Hence P(k + 1) is true.

33
 Strong Mathematical
Induction
e.g. Define a sequence s0, s1, s2, … as follows:
s0 = 0, s1 = 4,
sk = 6sk-1 - 5sk-2 for all integer k  2.

s2 = 6s2-1 - 5s2-2 = 6(4) - 5(0) = 24

s3 = 6s3-1 - 5s3-2 = 6(24) - 5(4) = 124 and so on.

Show that the n-th term of the sequence

sn = 5n – 1, for all n ≥ 0.

34
 Strong Mathematical
Induction
Proof:
Given that s0 = 0, s1 = 4, sk = 6sk-1 - 5sk-2 for all integer k  2.
Let P(n) be “sn = 5n – 1.”

Basis step:
(To show that P(0) and P(1) are true.) (a = 0 and b = 1)
Given that s0 = 0 and s1 = 4,

s0 = 0 = 50 – 1 = 0, so P(a) = P(0) is true.

s1 = 4 = 51 – 1 = 4, so P(b) = P(1) is true.
35
 Strong Mathematical
Induction
b=1
Inductive Step:
(Show that for all integers k ≥ 1, if P(i) is true for all integer i
from 0 to k, then P(k + 1) is also true.)
a=0
Let k be any integer with k  1 and
suppose that if P(i) is true for all integer i from 0 to k. i.e.,
(P(0) ∧ P(1) ∧ ∙∙∙ ∧ P(k)) is true or
si = 5i – 1 for all integer i from 0 to k.

We need to show that

P(k + 1): “sk+1 = 5k+1 – 1.” is true.
36
 Strong Mathematical
Induction
We know that sk+1= 6sk - 5sk-1

Since k  1, we have k +1  2, so
sk+1= 6sk - 5sk-1
= 6(5k – 1) – 5(5k-1 – 1)
= 6(5k) – 6 – 5k + 5
= (6-1)5k – 1
= 5k+1 – 1

So P(k + 1) is true.
37
Recursion

38
 Defining Recursive
Sequences
 A sequence is usually defined by an explicit formula like
the following.

 A sequence can be defined by recursion.

 This requires an equation, called a recurrence relation, that
defines each later term in the sequence by reference to
earlier terms.
 And also one or more initial values for the sequence.
e.g. ak = 6ak-1 – 5ak-2 for all integer k  2 and a0 = 0, a1 = 4
39
 Fibonacci Sequence
Consider a pair of rabbit (male and female) is born at the
beginning of a year. Assume the followings:

1) Each rabbit pairs doesn’t give birth during the first month
of their life.
2) But, after that, each pair gives birth to one new male-
female pair at the end of every month.
3) No rabbits die.
How many rabbits will there be at the end of the year?

40
 Fibonacci Sequence
The number of rabbit pairs as a function of time can be
written as a recursively defined sequence.
Let Bk be the number of new born rabbit pairs at the end of
month k and Fk be the total number of rabbit pairs at the
end of month k.
The total number of
Fk-2 Fk-1 Fk
rabbit pairs:

The number of new

born rabbit pairs: Bk-2 Bk-1 Bk
41
 Fibonacci Sequence
no rabbits die no rabbits die
The total number of
Fk-2 Fk-1 Fk
rabbit pairs:

The number of new

born rabbit pairs: Bk-2 Bk-1 Bk

Note that:
(as no rabbits die)
The total number of rabbit The number of new
The total number of rabbit
= pairs at the end of month + born rabbit pairs at the
pairs at the end of month end of month k-1
k-2 (old pairs)
k-1
Fk-1 = Fk-2 + Bk-1
42
 Fibonacci Sequence
The total number of
Fk-2 = Fk-3 + Bk-2 Fk-1 = Fk-2 + Bk-1 Fk = Fk-1 + Bk
rabbit pairs:

The number of new

born rabbit pairs: Bk-2 Bk-1 Bk

Note that
1. Any new born pairs will not give birth during the first month of their life.
2. All old pairs keep on giving births every month. (i.e. Fk-2 = Bk )

So we obtain a recurrence
relation:
Fk = Fk-2 + Fk-1 43
 Fibonacci Sequence
How many rabbits will there be at the end of the year?

The initial condition:

At the end of month 0, we have 1 pair rabbit (i.e., F0 = 1), that
pair doesn’t give birth at the end of month 1 (i.e., F1 = 1).

The recurrence relation: Fk = Fk-2 + Fk-1 for k  2

44
 Fibonacci Sequence
By the initial conditions and recurrence relation,

45
 Fibonacci Sequence

So at the end of the month 12 (a whole year), F12 = 233,

we have 233 pairs of rabbits.

The sequence F0, F1, F2 ,F3 , … is known as Fibonacci

sequence.

46
 Examples of Recursively
Defined Sequences
e.g.
Suppose you have $1000 deposit in a bank account. The
bank gives you 4% annual compound interest at the end of
each year. Show the amount in your bank account by
recurrence relation.

Let An be the amount in your account at the end of year n.

47
 Examples of Recursively
Defined Sequences
At the end of year k, the amount in your bank equals the sum
of the amount at the end of year k-1 and the interest you
earn at year k-1.

Ak = Ak-1 + Ak-1 (0.04) = (1.04) Ak-1

We know that A0 = 1000,

so A1 = (1.04) A0
A2 = (1.04) A1 = (1.04) (1.04) A0
A3 = (1.04) A2 = (1.04) (1.04) (1.04) A0
An = (1.04) An-1 = (1.04)n A0 (it forms a geometric sequence) 48
Solving Recurrence Relations

49
 Solving Recurrence
Relations
Given a recurrence relation and the initial conditions, we
can generate each term easily. But it would be nice if an
explicit formula can be obtained.

e.g.
mk = 2mk-1 + 1 for all k ≥ 2 and with m1 = 1
The explicit formula is given by

Ak = Ak-1 + Ak-1 (0.04) and with A0 = 1000

The explicit formula is given by An = 1000(1.04)n
50
 The method of Iteration
Let a0, a1, a2, . . . be the sequence defined recursively
as follows: For all integers k  1,

We use the method of iteration to guess an explicit

formula for the sequence.
We know that
.
…

51
 The method of Iteration
We can give the value of each term by substitutions:

By observation, we can see a pattern there. So we can

generalize the observation to obtain the explicit formula:

52
 The method of Iteration
e.g.
A sequence m1, m2, m3, . . . satisfies the recurrence
relation

and has the initial condition

Use iteration to guess an explicit formula for this

sequence, to simplify the answer.

53
 The method of Iteration
By the method of iteration,

54
 The method of Iteration
A special pattern appears. It appears that, in general,

By the formula for the sum of a geometric sequence

(Theorem 5.2),

55
 Second-Order Linear
Homogeneous Recurrence
Relations

The sequence F0, F1, F2 ,F3 , … is known as Fibonacci

sequence, where the recurrence relation:

Fk = Fk-2 + Fk-1 for k  2 and F0 = F1 = 1

To find the explicit formula for the sequence, the method of

iteration doesn’t work.

Indeed the recurrence relation of Fibonacci sequence is a

Second-Order Linear Homogeneous Recurrence Relation.
56
 Second-Order Linear
Homogeneous Recurrence
Relations

“Second-order” means the expression for ak contains the

two previous terms ak−1 and ak−2.
“linear” means that ak−1 and ak−2 appear in separate terms
and their degree are 1,
“homogeneous” to the fact that the total degree of each
term is the same (thus there is no constant term) 57
 Distinct-Roots Theorem
The explicit formula of a sequence with a second-order
recurrence relation can be obtained by using the result of
following theorem.

Theorem 5.6 (Distinct-Roots Theorem)

58
 Distinct-Roots Theorem
e.g.
The Fibonacci sequence F0, F1, F2, . . . satisfies the
recurrence relation

Fk = Fk-2 + Fk-1 for all integers k  2

with initial conditions

F0 = F1 = 1.

Find an explicit formula for this sequence.

59
 Distinct-Roots Theorem
Solution:
The Fibonacci relation Fk = Fk-2 + Fk-1 for all k  2, is a
second-order linear homogeneous recurrence relation with
constant coefficients (A = 1 and B = 1).

The characteristic equation would be

t 2 – At – B = t 2 – t – 1 = 0.

The characteristic equation has two distinct roots:

60
 Distinct-Roots Theorem
By Distinct-Roots Theorem, the Fibonacci sequence is
given by the explicit formula

To find C and D, write

and
61
 Distinct-Roots Theorem
Solving the system of equations, we have

Substituting these values for C and D into formula gives

for all integers n  0.

62
 Single-Root Theorem
What about the characteristic equation has just one root?
Theorem 5.7 (Single-Roots Theorem)

63
 Single-Root Theorem
e.g.
Suppose a sequence b0, b1, b2, . . . satisfies the recurrence
relation

with initial conditions

b0 = 1 and b1 = 3.
Find an explicit formula for b0, b1, b2, . . . .

64
 Single-Root Theorem
Solution:

The recurrence relation bk = 4bk-2 – 4bk-1 is a second-

order linear homogeneous recurrence relation with
constant coefficients (A = 4 and B = -4).

The characteristic equation would be

t 2 – At – B = t 2 – 4t + 4 = 0.

It has the unique root r = 2 [since t 2 – 4t + 4 = (t – 2)2].

65
 Single-Root Theorem
It follows from the single-root theorem that b0, b1, b2, . . .
is given by the explicit formula

To find C and D, write

Solve the simultaneous equation and substitute C = 1

and D = 1/2 into the explicit formula to conclude that

66