COUNTING, COMBINATORY &

RECURRENCE RELATION

Prepared By:
Ramesh Rimal
INTRODUCTION
 Combinatorics is the study of arrangements or
possible combination of objects.
 Enumeration, the counting of objects with
certain properties, is an important part of
combinatorics.
 Counting is used to determine the complexity of
Algorithms, to determine whether there are
enough telephone numbers or Internet protocol
addresses to meet demand etc.
 Recently, it has played a key role in
mathematical biology, especially in sequencing
DNA. Furthermore, counting techniques are used
extensively when probabilities of events are
computed.
BASICS OF COUNTING

There are two basic counting principles that can

be used to solve the counting problems.

Sum rule: The principle of disjunctive counting.

Product Rule: Principle of sequential counting.

Tuesday, October 06, 2020 3

SUM RULE: THE PRINCIPLE OF
DISJUNCTIVE COUNTING.
 If the first task can be done in ‘m’ ways and
the second task can be done in ‘n’ ways and
if both the tasks cannot be done at a time,
then there are m + n ways to do one of the
task.
 We can generalize this rule as, if a set X is
union of disjoint nonempty subsets S1, S2,
…,Sn, then |X| = | S1| + | S2| + … + | Sn|.
 Remember: the set must be disjoint, for
overlapping set we use different principle
called inclusion exclusion principle.
Tuesday, October 06, 2020 4
EXAMPLES
 In how many ways we can draw a heart or a diamond from an
ordinary deck of playing cards?
 Solution:
There are total 13 cards of heart and 13 card of diamond. So, by
sum rule total number of ways of picking heart or diamond is 13 +
13 = 26.

 How many ways we can get a sum of 4 or of 8 when two

distinguishable dice (say one die is red and the other is white)
are rolled?
 Solution:
Since dice are distinguishable outcome (1, 3) is different form (3,
1) so to get 4 as sum we have the pairs (1, 3), (3, 1), (2, 2), so
total of 3 ways.
 And similarly getting 8 can be from pairs (2, 6), (6, 2), (3, 5), (5,
3), (4, 4), so total 5 ways. Hence getting sum of 4 or 8 is 3 + 5 =
8.
Tuesday, October 06, 2020 5
EXERCISE
 Question: Suppose that either a member of the
mathematics faculty or a student who is a
mathematics major is chosen as a representative to
a university committee. How many different choices
are there for this representative if there are 37
members of the mathematics faculty and 83
mathematics majors and no one is both a faculty
member and a student?

There are 37 ways to choose a member of the

mathematics faculty and there are 83 ways to choose
a student who is a mathematics major. Choosing a
member of the mathematics faculty is never the same
as choosing a student who is a mathematics major
because no one is both a faculty member and a
student. By the sum rule it follows that there are 37
+ 83 = 120 possible ways to pick this representative.

Tuesday, October 06, 2020 6

EXERCISE
 Question: A student can choose a
computer project from one of three lists.
The three lists contain 23, 15 and 19
possible projects, respectively. No
project is on more than one list. How
many possible projects are there to
choose from?
The student can choose a project by
selecting a project from the first list, the
second list, or the third list. Because no
project is on more than one list, by the sum
rule there are 23 + 15 + 19 = 57 ways to
choose a project.

Tuesday, October 06, 2020 7

PRODUCT RULE: PRINCIPLE OF
SEQUENTIAL COUNTING.
 Suppose that a procedure can be broken down into a
sequence of two tasks. If there are n1 ways to do the
first task and for each of these ways of doing the first
task, there are n2 ways to do the second task, then
there are n1n2 ways to do the procedure.
 In other words, if a work can be done in m ways and
another work can be done after the completion of
first work in n ways, then there are m  n ways to do
the task that consists both the work.
 Generalizing the rule, if S1, S2, …, Sn are non empty
sets, then the number of elements in then Cartesian
product S1  S2  … Snn, is the product i 1| si | i.e. |
S1  S2  … Sn| =  i 1 | s |
i

Tuesday, October 06, 2020 8

EXAMPLES
 Question: An office building contains 27 floors and has 37
offices on each floor. How many offices are there are in the
building?
 Solution: By the product rule there are 27.37 = 999 offices
in the building.

 Question: A new company with just two employees, Ram and

Shyam, rents a floor of a building with 12 offices. How many
ways are there to assign different offices to these two
employees?
 Solution:

The procedure of assigning offices to these two employees

consists of assigning an office to Ram, which can be done in 12
ways, then assigning an office to Shyam different from the
office assigned to Ram, which can be done in 11 ways.
By the product rule, there are 12 · 11 = 132 ways to assign
offices to these two employees.

Tuesday, October 06, 2020 9

EXAMPLE
 The chairs of an auditorium are to be labeled
with an uppercase English letter followed by
a positive integer not exceeding 100. What is
the largest number of chairs that can be
labeled differently?
 Solution:
The procedure of labeling a chair consists of two tasks,
namely, assigning to the seat one of the 26 uppercase English
letters, and then assigning to it one of the 100 possible
integers.
The product rule shows that there are 26 · 100 = 2600
different ways that a chair can be labeled.
Therefore, the largest number of chairs that can be labeled
differently is 2600.

Tuesday, October 06, 2020 10

EXERCISE
 How many different license plates can be
made if each plate contains a sequence of
three uppercase English letters followed by
three digits (and no sequences of letters are
prohibited, even if they are obscene)?
--- ---

26 choices 10 choices for

for each letter each digit

There are 26 choices for each of the three uppercase English

letters and ten choices for each of the three digits. Hence, by
the product rule there are a total of 26 · 26 · 26 · 10 · 10 · 10 =
17,576,000 possible license plates.

Tuesday, October 06, 2020 11

INCLUSION-EXCLUSION PRINCIPLE
 When two tasks can be done at the same time,
we cannot use the sum rule to count the
number of ways to do one of the two tasks.
 Adding the number of ways to do each task
leads to an over count, since the ways to do
both tasks are counted twice.
 To correctly count the number of ways to do
one of the two tasks, we add the number of
ways to do each of the two tasks and then
subtract the number of ways to do both tasks.
This technique is called principle of inclusion-
exclusion.

Tuesday, October 06, 2020 12

INCLUSION-EXCLUSION
PRINCIPLE
 This counting principle can be phrased in terms of
sets.
 Let A1 and A2 be sets and let T1 be the task of choosing
an element from A1 and T2 the task of choosing an
element from A2.
 There are |A1| ways to do T1 and |A2| ways to do T2.
The number of ways to do either T1 or T2 is the sum of
the number of ways to do T1 and the number of ways
to do T2, minus the number of ways to do both T1 and
T2.
 Since, there are |A1 A2| ways to do either T1 or T2
and |A1 A2| ways to do both T1 and T2, we have |
A1 A2 | = |A1| + |A2| - |A1 A2|.
Tuesday, October 06, 2020 13
EXAMPLE
 How many bit strings of length eight either start with a 1 bit or end
with the two bits 00?
 Solution:
1 00 1 00
-------- -------- --------
27=128 ways 26=64 ways 25=32 ways

 The first task, constructing a bit string of length eight beginning with
a 1 bit, can be done in 27 = 128 ways (using product rule).
 The second task, constructing a bit string of length eight ending with
the two bits 00, can be done in 26 = 64 ways (using product rule).
 Both tasks, constructing a bit string of length eight that begins with a
1 and ends with 00 can be done in 25 = 32 ways (using product rule).
 Hence, the number of bit strings of length eight that either start with
a 1 bit or end with the two bits 00 is 128 + 64 – 32 = 160.

Tuesday, October 06, 2020 14

PIGEONHOLE PRINCIPLE
 The pigeonhole principle states that if there
are more pigeons than pigeonholes, then
there must be at least one pigeonhole with
at least two pigeons. The concept of pigeons
can be extended to any objects. It is also
known as Dirichlet drawer principle.

Tuesday, October 06, 2020 15

PIGEONHOLE PRINCIPLE
 If k+1 or more objects are placed into k boxes,
then there is at least one box containing two or
more objects.
 Proof:
 We use proof by contradiction here. Suppose that
k+1 or more objects are placed into k boxes and
no boxes contain more than one object in it.
 If there are k boxes then there must be k objects
such that there are no two objects in a box.
 This contradicts our assumption. So there is at
least one box containing two or more of the
objects.
Tuesday, October 06, 2020 16
EXAMPLES
 Among any group of 367 people, there must be at
least two with the same birthday, because there
are only 366 possible birthdays.
 In any group of 27 English words, there must be at
least two that begin with the same letter, because
there are 26 letters in the English alphabet.
 How many students must be in a class to
guarantee that at least two students receive the
same score on the final exam, if the exam is
graded on a scale from 0 to 100 points?
 Solution: There are 101 possible scores on the
final. The pigeonhole principle shows that among
any 102 students there must be at least 2 students
with the same score.
Tuesday, October 06, 2020 17
PERMUTATION
 Many counting problems can be solved by
finding the number of ways to arrange a
specified number of distinct elements of a
set of a particular size, where the order of
these elements matters.
 Many other counting problems can be solved
by finding the number of ways to select a
particular number of elements from a set of
a particular size, where the order of the
elements selected does not matter.

Tuesday, October 06, 2020 18

PERMUTATION
 Let us consider two numbers 123 and 321.
These two numbers consist of same digits 1,
2 and 3 but their arrangement is different.
So they are different permutations of the
digits 1, 2 and 3.
 So we can form many different permutation
from a given set of objects taken all at a
time or taken particular number of objects
at a time.

Tuesday, October 06, 2020 19

EXAMPLE
 In how many ways can we select three students from a group of
five students to stand in line for a picture? In how many ways can
we arrange all five of these students in a line for a picture?
 Solution:
First, note that the order in which we select the students
matters. There are five ways to select the first student to stand
at the start of the line.
Once this student has been selected, there are four ways to
select the second student in the line. After the first and second
students have been selected, there are three ways to select the
third student in the line.
By the product rule, there are 5 · 4 · 3 = 60 ways to select three
students from a group of five students to stand in line for a
picture.
 To arrange all five students in a line for a picture, we select the
first student in five ways, the second in four ways, the third in
three ways, the fourth in two ways, and the fifth in one way.
Consequently, there are 5 · 4 · 3 · 2 · 1 = 120 ways to arrange all
five students in a line for a picture.
Tuesday, October 06, 2020 20
PERMUTATION
 A permutation of a set of distinct objects is an ordered
arrangement of these objects.
 An ordered arrangement of r elements of a set is called
an r-permutation.
 Let S = {a, b, c}. The 2-permutations of S are the ordered
arrangements a, b; a, c; b, a; b, c; c, a; and c, b.
Consequently, there are six 2-permutations of this set
with three elements. There are always six 2-permutations
of a set with three elements.
 There are three ways to choose the first element of the
arrangement. There are two ways to choose the second
element of the arrangement, because it must be different
from the first element.
 Hence, by the product rule, we see that P(3, 2) = 3 · 2 =
6. the first element. By the product rule, it follows that
P(3, 2) = 3 · 2 = 6.
Tuesday, October 06, 2020 21
PERMUTATION
 If n is a positive integer and r is an integer
with 1  r  n, then there are
P(n, r) = n(n − 1)(n − 2) · · · (n − r + 1)
r-permutations of a set with n distinct
elements.
 In other words “The total number of
permutation of a set of n objects taken r at a
time is given by P(n, r) = n(n − 1)(n − 2) · · ·
(n − r + 1), (n  r)”
 Corollary: If n and r are integers with 0  r 
n, then P(n, r) =n!/(n − r)!
Tuesday, October 06, 2020 22
EXAMPLE
 How many ways are there to select a first-prize
winner, a second-prize winner, and a third-
prize winner from 100 different people who
have entered a contest?
 Solution: Because it matters which person wins
which prize, the number of ways to pick the
three prize winners is the number of ordered
selections of three elements from a set of 100
elements, that is, the number of 3-
permutations of a set of 100 elements.
Consequently, the answer is
P(100, 3) = 100 · 99 · 98 = 970,200
Tuesday, October 06, 2020 23
EXAMPLES
 Suppose that there are eight runners in a race. The winner
receives a gold medal, the second-place finisher receives a silver
medal, and the third-place finisher receives a bronze medal. How
many different ways are there to award these medals, if all
possible outcomes of the race can occur and there are no ties?
 Solution: The number of different ways to award the medals is
the number of 3-permutations of the set with eight elements.
Hence, there are P(8, 3) = 8.7.6 = 336 possible ways to award the
medals.
 Suppose that a saleswoman has to visit eight different cities. She
must begin her trip in a specified city, but she can visit other
seven cities in any order she wishes. How many possible orders
can the saleswoman use when visiting these cities?
 Solution: The number of possible paths between the cities is the
number of permutations of seven elements, since the first city is
determined, but the remaining seven can be ordered arbitrarily.
Hence, there are 7! = 7.6.5.4.3.2.1 = 5040 ways for the
saleswoman to choose her tour.
Tuesday, October 06, 2020 24
EXAMPLE
 How many ways are there to arrange the
three letters A, B, and C in a row with
repetition?
 The first letter can be selected in 3 ways. As
the repetition allowed the second letter can
also be selected in 3 ways and third letter
can also be selected in 3 ways. Therefore,
the total number of ways of arranging 3
letters is 3×3×3 =27.

Tuesday, October 06, 2020 25

EXAMPLE
 How many permutations of the letters
ABCDEFGH contain the string ABC ?
 Solution: Because the letters ABC must occur
as a block, we can find the answer by finding
the number of permutations of six objects,
namely, the block ABC and the individual
letters D, E, F, G, and H. Because these six
objects can occur in any order, there are 6! =
720 permutations of the letters ABCDEFGH in
which ABC occurs as a block.

Tuesday, October 06, 2020 26

COMBINATION
 Combination of objects refers to just collection of
objects without any regard to order or arrangement.
 The absence of order in the combination of objects
makes it different from the permutations of the
objects.
 There is only one combination of n objects; but for
the same n objects the number of permutations is n!
 The number of combinations of n objects taken r at
a time is less than the number of permutations of n
objects taken r at a time.
 The number of r-combinations of a set with n distinct
elements is denoted by C(n, r).

Tuesday, October 06, 2020 27

COMBINATION
 An r-combination of elements of a set is an
unordered selection of r elements from the set.
Thus, an r-combination is simply a subset of the
set with r elements.
 Example: Let S be the set {1, 2, 3, 4}. Then {1,
3, 4} is a 3-combination from S. (Note that {4,
1, 3} is the same 3-combination as {1, 3, 4},
because the order in which the elements of a
set are listed does not matter.)
 We see that C(4, 2) = 6, because the 2-
combinations of {a, b, c, d} are the six subsets
{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, and {c, d}.
Tuesday, October 06, 2020 28
COMBINATION
 Corollary: Let n and r be nonnegative
integers with r  n. Then C(n, r) = C(n, n − r).
 How many ways are there to select five
players from a 10-member tennis team to
make a trip to a match at another school?
 Solution: The answer is given by the number
of 5-combinations of a set with 10 elements.
The number of such combinations is
C(10, 5) = 10!/(5! 5!) = 252.

Tuesday, October 06, 2020 29

EXAMPLE
 A group of 30 people have been trained as astronauts
to go on the first mission to Mars. How many ways are
there to select a crew of six people to go on this
mission (assuming that all crew members have the
same job)?
 Solution: The number of ways to select a crew of six
from the pool of 30 people is the number of 6-
combinations of a set with 30 elements, because the
order in which these people are chosen does not
matter.
 Therefore, the number of such combinations is
C(30, 6) = 30!/(6! 24!)
=(30 · 29 · 28 · 27 · 26 · 25)/(6·5·4·3·2·1)
= 593,775.
Tuesday, October 06, 2020 30
EXAMPLE
 Suppose that there are 9 faculty members in the
mathematics department and 11 in the computer
science department. How many ways are there to
select a committee to develop a discrete mathematics
course at a school if the committee is to consist of
three faculty members from the mathematics
department and four from the computer science
department?
 Solution: By the product rule, the answer is the
product of the number of 3-combinations of a set with
nine elements and the number of 4-combinations of a
set with 11 elements.
 The number of ways to select the committee is
C(9, 3) · C(11, 4) = 9!/3!6! × 11!/4!7!
= 84 · 330
= 27,720.
Tuesday, October 06, 2020 31
BINOMIAL COEFFICIENT
 The number of r-combinations from a set
with n elements is often denoted by  nr 
 This number is also called a binomial
coefficient because these numbers occur as
coefficients in the expansion of powers of
binomial expressions such as (x + y)n.
 The Binomial Theorem
The binomial theorem gives the coefficients
of the expansion of the expansion of powers
of binomial expression. A binomial expression
is simply the sum of two terms, such as x + y.

Tuesday, October 06, 2020 32

BINOMIAL THEOREM
 Let x and y be variables, and let n be a
nonnegative integer. Then
(x+y) =   nj  x n - j y j
n
 n

 x  x  x
j 0

n1 n n 2 2
=
n
0+
n n
+1 y 2 y
  xy +
n
+------------+ n  1
n 1
 y
n
n
n

Tuesday, October 06, 2020 33

CONTD…
 The co-efficient  0n ,  1n ,....  nn 
in the binomial expansion are called binomial
co-efficient which are also denoted by C0, C1,
….. Cn,
EXAMPLE
EXAMPLE
EXAMPLE
GENERAL TERM
 The (r+1)th term in the expansion of (x + y)n is
usually called its general term which is
denoted by tr+1.
 In the expansion of (x + y)n ,
t1 =1st term = C(n,0) xn
t2 =2nd term = C(n,1) xn-1y
t3 =3rd term = C(n,2) xn-2y2

tr+1 = (r+1)th term = C(n, r) xn-r yr

 Therefore, the general term in the expansion
of (x + y)n , denoted by tr+1 is C(n, r) xn-r yr.
COROLLARY 1

 Therefore, sum of Binomial co-efficient is 2n.

COROLLARY 2
MIDDLE TERM
 We have to consider two cases; when n is even
integer and when n is odd integer in order to
find the middle term in the expansion of (x +
y)n.
 When n is even integer, the number of terms in
the expansion of (x + y)n is odd i.e. n+1. So,
there is exactly one middle term which is t n/2+1 .
 When n is odd integer, the number of terms in
the expansion of (x + y)n is even i.e. n+1. And
there are two middle term which are t(n+1)/2 and
t(n+1)/2+1 .
EXAMPLE
 Find the middle term in the expansion of (x-
1/x)18.
Solution:
 Here, n=18, is even. So, there are 18+1=19 terms
in the expansion of (x-1/x)18, which is odd.
 Therefore, there exist exactly one middle term
which is tn/2+1 i.e. t10.
  t10 = C(n,9)xn-9(-1/x)9 = C(18,9)x18-9(-1/x)9

= (-1)

=-
EXAMPLE
 What is the expanion of (x+y)4?
 What is the coefficient of x12y13 in the
expansion of (x + y)25?
 What is the coefficient of x12y13 in the
expansion of (2x − 3y)25?
 What is the coefficient of x13y7 in the
expansion of (x-3y)20?

We write (x - 3y)20 as (x + (-3y))20 and apply

the binomial theorem, which gives us the
term C(20, 7)x13(-3y)7 = -37C(20, 7)x13y7.
Tuesday, October 06, 2020 43
RECURRENCE RELATIONS
 Some counting problems cannot be solved using the
methods we have learnt before. One of the ways of
solving counting problems is by finding relationships,
called recurrence relation, between the terms of a
sequence.
 When we represent some problem using recursive
definition then we specify some initial condition and the
recursive condition.
 We use such definition to solve the relation called
recurrence relation.
 A recurrence relation for the sequence {an} is an equation
that expresses an in terms of one or more of the previous
terms of the sequence, namely, a0, a1, …, an-1, for all
integers n with n ≥ n0, where n0 is a nonnegative integer.
 A sequence is called a solution of a recurrence relation if
its term satisfies the recurrence relation.
Tuesday, October 06, 2020 44
EXAMPLES
 Question: Let {an} be a sequence that satisfies the
recurrence relation an = an-1 + 1 for n = 1, 2, …, and
suppose that a1=1. What is the sequence?
 Solution: We have a1 = 1, a2 = a1+1= 1 + 1 = 2 ….. In
similar way we have the set {1, 2, ….}.
 Question: For an = -2an-1, a0 = -1 find a1, a2, … a5.
 Solution:
We have a0 =- -1
a1 = -2a0 = -2.-1 = 2.
a2 = -2a1 = -2.2 = -4.
a3 = -2a2 = -2.-4 = 8.
a4 = -2a3 = -2.8 = -16.
a5 = -2a4 = -2.-16 = 32.
Tuesday, October 06, 2020 45
EXAMPLE
 Determine whether the sequence {an},
where an=3n for every nonnegative
integer n, is a solution of the
recurrence relation an=2an-1 – an-2 for
n=2,3,4… Answer the same question
where an=2n and an=5.
 We have an=3n for every nonnegative
integer n. Then for n2, we see that 2an-
1–an-2 = 2.3(n-1)-3(n-2)=3n=an. Therefore,
{an}, where an=3n, is a solution of the
recurrence relation. Tuesday, October 06, 2020 46
CONTD…
 We have an=2n for every nonnegative
integer n. Here, a0=1,a1=2,a2=4.2a1-
a0=2.2-1=3a2. Therefore, {an}, where
an=2n, is not a solution of the recurrence
relation.
 We have an=5 for every nonnegative
integer n. Then for n2, we see that 2an-1–
an-2 = 2.5-5=5=an. Therefore, {an}, where
an=5, is a solution of the recurrence
relation.
EXAMPLE
 Is the sequence {an} a solution of the
recurrence relation an = -3an-1 + 4an-2 if a) an =
0? and b) an = 2n? (TU2070)
 Solution:
 Here, we see that -3an-1 + 4an-2= -3.0+4.0 = 0
= an. we have a) an = 0 so the sequence {an} is
a solution.
 Here, we see that -3an-1 + 4an-2= -3.2(n-1) +
4.2(n-2) = -6n + 6 + 8n – 16 =2n – 10  2n, so
it is not a solution.
Tuesday, October 06, 2020 48
MODELING WITH RECURRENCE RELATION
 Suppose that a person deposits Rs. 10,000 in a
saving account at a bank yielding 11% per year
with interest compounded annually. How much
will be in the account after 10 years? (TU2067)
 Solution: Let Pn be the amount in the bank after n
years.
 The amount in the bank after n years equals the
amount in the bank after (n-1) years plus interest
for the nth year.
 Therefore, the sequence {Pn} satisfies the
recurrence relation Pn = Pn-1 + 0.11 Pn-1 =(1.11) Pn-1
 The initial condition is P0 = 10000
Tuesday, October 06, 2020 49
EXAMPLE CONTD.
 We can use an iterative approach to find a formula for Pn
P1 = (1.11)P0
P2 = (1.11)P1 = (1.11)2P0
P3 = (1.11)P2 = (1.11)3P0

Pn = (1.11)Pn-1 = (1.11)nP0
 When we insert the initial condition P0 = 10000, the formula Pn =
(1.11)n 10000 is obtained.
 We can use mathematical induction to establish its validity. The
formula is valid for n=0 is a consequence of the initial condition.
 Now assume that Pn = (1.11)n 10000 then Pn+1 = (1.11)n+1 10000
 Pn+1 = (1.11)Pn = (1.11)(1.11)nP0 =(1.11)n+1 10000
 This shows that the explicit formula for Pn is valid.
 Inserting n=10 into the formula Pn = (1.11)n 10000 shows that
after 10 years the account will contain
P10 = (1.11)1010000 = Rs. 28394.21
Tuesday, October 06, 2020 50
SOLVING LINEAR RECURRENCE RELATIONS
 We encounter different types of recurrence
relations. There is no specific technique to
solve all the recurrence relation.
 However, we solve recurrence relation with
some particular forms by using the
systematic methods.
 In this section we are going to see few of
them.

Tuesday, October 06, 2020 51

SOLVING LINEAR RECURRENCE RELATIONS
 A linear homogeneous recurrence relation of degree k
with constant coefficients is a recurrence relation of the
form an = c1an-1 + c2an-2 + … + ckan-k, where c1, c2, …, ck
are real numbers, and ck  0.
 The above relation is linear since right hand side is a
sum of the multiples of previous terms of the sequence.
 It is homogeneous since no term occurs without being
multiple if some ajs.
 All the coefficients of the terms are constants, rather
than functions that depend on n and degree is k due to
the representation of an in terms of previous k terms of
the sequence.
 In solving the recurrence relation of the type above, the
approach is to look for the solution of the form a n = rn,
where r is a constant.

Tuesday, October 06, 2020 52

EXAMPLE
 The recurrence relation Pn = (1.11)Pn−1 is a
linear homogeneous recurrence relation of
degree one.
 The recurrence relation fn = fn−1 + fn−2 is a linear
homogeneous recurrence relation of degree
two.
 The recurrence relation an = an−5 is a linear
homogeneous recurrence relation of degree
five.
 The recurrence relation an = an−1 + a2n−2 is not
linear. The recurrence relation Hn = 2Hn−1 +1 is
not homogeneous. The recurrence relation B n =
nBn−1 does not have constant coefficients.
Tuesday, October 06, 2020 53
SOLVING LINEAR HOMOGENEOUS RECURRENCE
RELATIONS WITH CONSTANT COEFFICIENTS
 The basic approach for solving linear homogeneous
recurrence relations is to look for solutions of the form a n =
rn, where r is a constant.
 Note that an = rn is a solution of the recurrence relation a n =
c1an−1 + c2an−2 + ··· + ckan−k if and only if rn = c1rn−1 + c2rn−2 + ···
+ ckrn−k.
 When both sides of this equation are divided by r n−k and the
right-hand side is subtracted from the left, we obtain the
equation
rk − c1rk−1 − c2rk−2 −· · ·−ck-1r − ck = 0.
 Consequently, the sequence {an} with an = rn is a solution if
and only if r is a solution of this last equation. We call this
the characteristic equation of the recurrence relation.
 The solutions of this equation are called the characteristic
roots of the recurrence relation.
Tuesday, October 06, 2020 54
THEOREM 1 (WITHOUT PROOF)
 Let c1 and c2 be real numbers. Suppose that r2 − c1r − c2 = 0 has
two distinct roots r1 and r2. Then the sequence {an} is a solution
of the recurrence relation an = c1an−1 + c2an−2 if and only if an =
1r1n + 2r2n for n = 0, 1, 2, . . . , where 1 and 2 are constants.
 Example: What is the solution of the recurrence relation an = an−1
+ 2an−2 with a0 = 2 and a1 = 7?
 Solution:
 The characteristic equation of the recurrence relation is r2 − r −
2 = 0. Its roots are r = 2 and r = −1.
 Hence, the sequence {an} is a solution to the recurrence relation
if and only if an = 12n + 2(−1)n, for some constants 1 and 2.
 From the initial conditions, it follows that
a0 = 2 = 1 + 2, & a1 = 7 = 1 · 2 + 2 · (−1).
 Solving these two equations shows that 1 = 3 and 2 = −1.
Hence, the solution to the recurrence relation and initial
conditions is the sequence {an} with an = 3 · 2n − (−1)n.
Tuesday, October 06, 2020 55
EXERCISE
 Solve the recurrence relation an = an-1 + 6an-2 for n
 2, a0 = 3, a1 = 6.
 Solution:

The characteristic equation of the given relation is r2 - r -

6 = 0 and its roots are r = 3 and r = -2.
Hence, the sequence {an} is a solution to the recurrence
relation if and only if
an = 13n + 2(-2)n, for some constants 1 & 2.
From the initial conditions, we have
a0 = 3 = 1+ 2 & a1 = 6 = 31+ (-2) 2.
Solving these two equations we have
1 = 12/5 and 2 = 3/5.
Hence, the solution is the sequence {an} with an = (12.3n +
3(-2)n)/5.

Tuesday, October 06, 2020 56

EXERCISE
 Find an explicit formula for the Fibonacci
numbers. [TU 2070, 2068]
We know that the sequence of Fibonacci
numbers satisfies the recurrence relation fn
= fn−1 + fn−2 and also satisfies the initial
conditions f0 = 0 and f1 = 1.
The roots of the characteristic equation r2 −
r − 1 = 0 are r1 = (1 + 5)/2 & r2 = (1 − 
5)/2.
Therefore, from Theorem 1 it follows that
the Fibonacci numbers are given by
fn = 1[(1+ 5)/2]n + 2[(1 -5)/2]n
for some constant 1 & 2 .
Tuesday, October 06, 2020 57
EXERCISE CONTD.
The initial conditions f0 = 0 and f1 = 1 can
be used to find these constants. We have
f0 = 1+ 2 = 0 &
f1 = 1[(1+ 5)/2] + 2[(1 -5)/2]
Solving these two equations we have
1 = 1/5, 2 = −1/5.
Consequently, the Fibonacci numbers are
given by
fn = [1/5][(1+ 5)/2]n – [1/5][(1 -5)/2]n

Tuesday, October 06, 2020 58

THEOREM 2 (WITHOUT PROOF)
 Theorem 1 does not apply when there is one
characteristic root of multiplicity two. If this
happens, then an = nr0n is another solution of
the recurrence relation when r0 is a root of
multiplicity two of the characteristic equation.
 Theorem2: Let c1 and c2 be real numbers with
c2  0. Suppose that r2 − c1r − c2 = 0 has only
one root r0. A sequence {an} is a solution of the
recurrence relation an = c1an−1 +c2an−2 if and only
if an = 1r0n + 2nr0n , for n = 0, 1, 2, . . . ,
where 1 and 2 are constants.

Tuesday, October 06, 2020 59

EXAMPLE
 What is the solution of the recurrence relation an = 6an−1 −
9an−2 with initial conditions a0 = 1 and a1 = 6?
 Solution:
 The characteristic equation of the given recurrence
relation is r2 − 6r + 9 = 0 and its root is r = 3.
 Hence, the solution to this recurrence relation is
an = 13n + 2n3n for some constants 1 and 2.
 Using the initial conditions, it follows that
a0 = 1 = 1,
a1 = 6 = 1·3 + 2·3
 Solving these two equations shows that
1 = 1 and 2 = 1.
 Consequently, the solution to this recurrence relation and
the initial conditions is
an = 3n + n3n. Tuesday, October 06, 2020 60
EXERCISE
 Solve the recurrence relation an = 2an-1 - an-2
for n  2, a0 = 3, a1 = 6.
 Solution:
The characteristic equation of the given relation is r2 -
2r + 1 = 0 so its only root is r = 1.
Hence, the sequence {an} is a solution to the recurrence
relation if and only if
an = 11n + 2n1n, for some constants 1 & 2.
From the initial conditions we have
a0 = 3 = 1 and a1 = 6 = 1 + 2.
Solving these two equations we have 1 = 3 and 2 = 3.
Hence, the solution is the sequence {an} with an = 3(1n +
n1n) = 3(1 + n).

Tuesday, October 06, 2020 61