Introduction of Sets

A set is defined as a collection of distinct objects of the same type or class of objects. The
purposes of a set are called elements or members of the set. An object can be numbers,
alphabets, names, etc.

Examples of sets are:

a. A set of rivers of India.

b. A set of vowels.

Sets Representation:

Sets are represented in two forms:-

a) Roster or tabular form: In this form of representation we list all the elements of the
set within braces { } and separate them by commas.

Example: If A= set of all odd numbers less then 10 then in the roster from it can be
expressed as A={ 1,3,5,7,9}.

b) Set Builder form: In this form of representation we list the properties fulfilled by all
the elements of the set. We note as {x: x satisfies properties P}. and read as 'the set of
those entire x such that each x has properties P.'

where n ∈ N and 1≤ n ≥5}

Example: If B= {2, 4, 8, 16, 32}, then the set builder representation will be: B={x: x=2 n,

Standard Notations:
x∈A x belongs to A or x is an element of set A.

x∉A x does not belong to set A.

∅ Empty Set.

U Universal Set.

N The set of all natural numbers.

I The set of all integers.

I0 The set of all non- zero integers.

I+ The set of all + ve integers.

C, C0 The set of all complex, non-zero complex numbers respectively.

Q, Q0, Q+ The sets of rational, non- zero rational, +ve rational numbers respectively.
 R, R0, R+ The set of real, non-zero real, +ve real number respectively.

Cardinality of a Sets:

The total number of unique elements in the set is called the cardinality of the set. The
cardinality of the countably infinite set is countably infinite.

Examples:

1. Let P = {k, l, m, n}
The cardinality of the set P is 4.

2. Let A is the set of all non-negative even integers, i.e.

A = {0, 2, 4, 6, 8, 10......}.

As A is countably infinite set hence the cardinality.

Types of Sets

Sets can be classified into many categories. Some of which are finite, infinite, subset,
universal, proper, power, singleton set, etc.

1. Finite Sets: A set is said to be finite if it contains exactly n distinct element where n
is a non-negative integer. Here, n is said to be "cardinality of sets." The cardinality of sets
is denoted by|A|, # A, card (A) or n (A).

Example:

1. Cardinality of empty set θ is 0 and is denoted by |θ| = 0

2. Sets of even positive integer is not a finite set.

A set is called a finite set if there is one to one correspondence between the elements in
the set and the element in some set n, where n is a natural number and n is the
cardinality of the set. Finite Sets are also called numerable sets. n is termed as the
cardinality of sets or a cardinal number of sets.

2. Infinite Sets: A set which is not finite is called as Infinite Sets.

Countable Infinite: If there is one to one correspondence between the elements in set
and element in N. A countably infinite set is also known as Denumerable. A set that is
either finite or denumerable is known as countable. A set which is not countable is known
as Uncountable. The set of a non-negative even integer is countable Infinite.

Uncountable Infinite: A set which is not countable is called Uncountable Infinite Set or
non-denumerable set or simply Uncountable.

Example: Set R of all +ve real numbers less than 1 that can be represented by the
decimal form 0. a1,a2,a3..... Where a1 is an integer such that 0 ≤ ai ≤ 9.

subset of B. It can be denoted as A ⊆ B. Here B is called Superset of A.

3. Subsets: If every element in a set A is also an element of a set B, then A is called a

Example: If A= {1, 2} and B= {4, 2, 1} the A is the subset of B or A ⊆ B.

Properties of Subsets:
 1. Every set is a subset of itself.

2. The Null Set i.e.∅ is a subset of every set.

3. If A is a subset of B and B is a subset of C, then A will be the subset of C. If A⊂B

and B⊂ C ⟹ A ⊂ C

4. A finite set having n elements has 2n subsets.

4. Proper Subset: If A is a subset of B and A ≠ B then A is said to be a proper subset of

B. If A is a proper subset of B then B is not a subset of A, i.e., there is at least one
element in B which is not in A.

Example:

(i) Let A = {2, 3, 4}

B = {2, 3, 4, 5}

A is a proper subset of B.

(ii) The null ∅ is a proper subset of every set.

5. Improper Subset: If A is a subset of B and A = B, then A is said to be an improper

subset of B.

Example

(i) A = {2, 3, 4}, B = {2, 3, 4}

A is an improper subset of B.

(ii) Every set is an improper subset of itself.

6. Universal Set: If all the sets under investigations are subsets of a fixed set U, then
the set U is called Universal Set.

Example: In the human population studies the universal set consists of all the people in
the world.

7. Null Set or Empty Set: A set having no elements is called a Null set or void set. It is
denoted by∅.

8. Singleton Set: It contains only one element. It is denoted by {s}.

Example: S= {x|x∈N, 7<x<9} = {8}

9. Equal Sets: Two sets A and B are said to be equal and written as A = B if both have
the same elements. Therefore, every element which belongs to A is also an element of
the set B and every element which belongs to the set B is also an element of the set A.

1. A = B ⟺ {x ϵ A ⟺ x ϵ B}.

If there is some element in set A that does not belong to set B or vice versa then A ≠ B,
i.e., A is not equal to B.

10. Equivalent Sets: If the cardinalities of two sets are equal, they are called
equivalent sets.
Example: If A= {1, 2, 6} and B= {16, 17, 22}, they are equivalent as cardinality of A is
equal to the cardinality of B. i.e. |A|=|B|=3

11. Disjoint Sets: Two sets A and B are said to be disjoint if no element of A is in B and
no element of B is in A.

Example:

R = {a, b, c}
S = {k, p, m}

R and S are disjoint sets.

12. Power Sets: The power of any given set A is the set of all subsets of A and is
denoted by P (A). If A has n elements, then P (A) has 2n elements.

Example: A = {1, 2, 3}
P (A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Partitions of a Set:

Let S be a nonempty set. A partition of S is a subdivision of S into nonoverlapping,

nonempty subsets. Speceficially, a partition of S is a collection {Ai} of nonempty subsets
of S such that:

o Each a in S belongs to one of the Ai.

o The sets of {Ai} are mutually disjoint; that is,

Aj≠ Ak Then Aj ∩ Ak= ∅

The subsets in a partition are called cells.

Fig: Venn diagram of a partition of the rectangular set S of points into five
cells,A1,A2,A3,A4,A5

Venn Diagrams:

Venn diagram is a pictorial representation of sets in which an enclosed area in the plane
represents sets.
Examples:

Operations on Sets

The basic set operations are:

1. Union of Sets: Union of Sets A and B is defined to be the set of all those elements
which belong to A or B or both and is denoted by A∪B.

1. A∪B = {x: x ∈ A or x ∈ B}

Example: Let A = {1, 2, 3}, B= {3, 4, 5, 6}

A∪B = {1, 2, 3, 4, 5, 6}.

2. Intersection of Sets: Intersection of two sets A and B is the set of all those elements
which belong to both A and B and is denoted by A ∩ B.

1. A ∩ B = {x: x ∈ A and x ∈ B}

Example: Let A = {11, 12, 13}, B = {13, 14, 15}

A ∩ B = {13}.
3. Difference of Sets: The difference of two sets A and B is a set of all those elements
which belongs to A but do not belong to B and is denoted by A - B.

1. A - B = {x: x ∈ A and x ∉ B}

Example: Let A = {1, 2, 3, 4} and B = {3, 4, 5, 6} then A - B = {3, 4} and B - A = {5, 6}

4. Complement of a Set: The Complement of a Set A is a set of all those elements of

the universal set which do not belong to A and is denoted by A c.

Ac = U - A = {x: x ∈ U and x ∉ A} = {x: x ∉ A}

Example: Let U is the set of all natural numbers.

A = {1, 2, 3}
Ac = {all natural numbers except 1, 2, and 3}.
set containing all the elements that are in A or B but not in both and is denoted by A ⨁ B
5. Symmetric Difference of Sets: The symmetric difference of two sets A and B is the

i.e.

1. A ⨁ B = (A ∪ B) - (A ∩ B)

Example: Let A = {a, b, c, d}

A ⨁ B = {c, d, l, m}
B = {a, b, l, m}

Algebra of Sets

Sets under the operations of union, intersection, and complement satisfy various laws (identities) which are
listed in Table 1.

Table: Law of Algebra of Sets

Idempotent Laws (a) A ∪ A = A (b) A ∩ A = A

Associative Laws (a) (A ∪ B) ∪ C = A ∪ (B ∪ C) (b) (A ∩ B) ∩ C = A ∩ (B ∩ C)

Commutative (a) A ∪ B = B ∪ A (b) A ∩ B = B ∩ A

Laws
 Distributive Laws (a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ (b) A ∩ (B ∪ C) =(A ∩ B) ∪ (A ∩
C) C)

De Morgan's (a) (A ∪B)c=Ac∩ Bc (b) (A ∩B)c=Ac∪ Bc

Laws

∪ ∅
(b) A ∪ U = U (d) A ∩ ∅ = ∅
Identity Laws (a) A = A (c) A ∩ U =A

∪ ∅
(b) A ∩ Ac= ∅ (d) ∅c = U
Complement (a) A Ac= U (c) U c=
Laws

Involution Law (a) (Ac)c = A

Multisets

A multiset is an unordered collection of elements, in which the multiplicity of an element

may be one or more than one or zero. The multiplicity of an element is the number of
times the element repeated in the multiset. In other words, we can say that an element
can appear any number of times in a set.

Example:

1. A = {l, l, m, m, n, n, n, n}
2. B = {a, a, a, a, a, c}
Operations on Multisets

1. Union of Multisets: The Union of two multisets A and B is a multiset such that the

and B and is denoted by A ∪ B.

multiplicity of an element is equal to the maximum of the multiplicity of an element in A

Example:

1. Let A = {l, l, m, m, n, n, n, n}
2. B = {l, m, m, m, n},
3. A ∪ B = {l, l, m, m, m, n, n, n, n}
2. Intersections of Multisets: The intersection of two multisets A and B, is a multiset
such that the multiplicity of an element is equal to the minimum of the multiplicity of an
element in A and B and is denoted by A ∩ B.

Example:

1. Let A = {l, l, m, n, p, q, q, r}
2. B = {l, m, m, p, q, r, r, r, r}
3. A ∩ B = {l, m, p, q, r}.

3. Difference of Multisets: The difference of two multisets A and B, is a multiset such

that the multiplicity of an element is equal to the multiplicity of the element in A minus
the multiplicity of the element in B if the difference is +ve, and is equal to 0 if the
difference is 0 or negativeDifference between JDK, JRE, and JVM

Example:

1. Let A = {l, m, m, m, n, n, n, p, p, p}
2. B = {l, m, m, m, n, r, r, r}
3. A - B = {n, n, p, p, p}

4. Sum of Multisets: The sum of two multisets A and B, is a multiset such that the
multiplicity of an element is equal to the sum of the multiplicity of an element in A and B

Example:

1. Let A = {l, m, n, p, r}
2. B = {l, l, m, n, n, n, p, r, r}
3. A + B = {l, l, l, m, m, n, n, n, n, p, p, r, r, r}

5. Cardinality of Sets: The cardinality of a multiset is the number of distinct elements

in a multiset without considering the multiplicity of an element

Example:
1. A = {l, l, m, m, n, n, n, p, p, p, p, q, q, q}

The cardinality of the multiset A is 5.

Ordered Set

It is defined as the ordered collection of distinct objects.

Example:
1. Roll no {3, 6, 7, 8, 9}
2. Week Days {S, M, T, W, W, TH, F, S, S}
Ordered Pairs

An Ordered Pair consists of two elements such that one of them is designated as the first
member and other as the second member.
(a, b) and (b, a) are two different ordered pair. An ordered triple can also be written
regarding an ordered pair as {(a, b) c}

An ordered Quadrable is an ordered pair {(((a, b), c) d)} with the first element as ordered
triple.

An ordered n-tuple is an ordered pair where the first component is an ordered (n - 1)

tuples, and the nth element is the second component.

1. {(n -1), n}
Inclusion-Exclusion Principle

Let A, B be any two finite sets. Then n (A ∪ B) = n (A) + n (B) - n (A ∩ B)

Here "include" n (A) and n (B) and we "exclude" n (A ∩ B)

Example 1:

Suppose A, B, C are finite sets. Then A ∪ B ∪ C is finite and n (A ∪ B ∪ C) = n(A) + n(B) +

n(C) - n(A ∩ B) - n(A ∩ C) - n(B ∩ C) + n(A ∩ B ∩ C)

Example 2:

In a town of 10000 families it was found that 40% of families buy newspaper A, 20%
family buy newspaper B, 10% family buy newspaper C, 5% family buy newspaper A and
B, 3% family buy newspaper B and C and 4% family buy newspaper A and C. If 2% family
buy all the newspaper. Find the number of families which buy

1. Number of families which buy all three newspapers.

2. Number of families which buy newspaper A only

3. Number of families which buy newspaper B only

4. Number of families which buy newspaper C only

5. Number of families which buy None of A, B, C

6. Number of families which buy exactly only one newspaper

7. Number of families which buy newspaper A and B only

8. Number of families which buy newspaper B and C only

9. Number of families which buy newspaper C and A only

10. Number of families which buy at least two newspapers

11. Number of families which buy at most two newspapers

12. Number of families which buy exactly two newspapers

Solution:
1. Number of families which buy all three newspapers:

1. n (A ∪ B ∪ C) = n(A) + n(B) + n(C) - n(A ∩ B) - n(A ∩ C) - n(B ∩ C) + n(A ∩ B ∩ C)

2. n (A ∪ B ∪ C) = 40 + 20 + 10 - 5 - 3 - 4 + 2 = 60%

2. Number of families which buy newspaper A only

1. = 40 - 7 = 33%

3. Number of families which buy newspaper B only

1. = 20 - 6 = 14%

4. Number of families which buy newspaper C only

1. = 10 - 5 = 5%

5. Number of families which buy None of A, B, and C

n (A ∪B ∪C)c = 100 - n (A ∪ B ∪ C)
n (A ∪B ∪C)c = 100 - [40 + 20 + 10 - 5- 3- 4 + 2]
n (A ∪B ∪C)c = 100 - 60 = 40 %

6. Number of families which buy exactly only one newspaper

1. = 33 + 14 + 5 = 52%

7. Number of families which buy newspaper A and B only

1. = 3%

8. Number of families which buy newspaper B and C only

 1. = 1%

9. Number of families which buy newspaper C and A only

1. = 2%

10. Number of families which buy at least two newspapers

1. = 8%

11. Number of families which buy at most two newspapers

1. = 98%

12. Number of families which buy exactly two newspapers

1. = 6%
Mathematical Induction

The process to establish the validity of an ordinary result involving natural numbers is
the principle of mathematical induction.

Working Rule

Let n0 be a fixed integer. Suppose P (n) is a statement involving the natural number n
and we wish to prove that P (n) is true for all n ≥n 0.

1. Basic of Induction: P (n0) is true i.e. P (n) is true for n = n0.

2. Induction Step: Assume that the P (k) is true for n = k.

Then P (K+1) must also be true.
Then P (n) is true for all n ≥n0.

Example 1:

Prove the follo2wing by Mathematical Induction:

1 + 3 + 5 +.... + 2n - 1 = n2.

Solution: let us assume that.

P (n) = 1 + 3 + 5 +..... + 2n - 1 = n2.

For n = 1, P (1) = 1 = 12 = 1
It is true for n = 1................ (i)

Induction Step: For n = r,

P (r) = 1 + 3 + 5 +..... +2r-1 = r2 is true......................... (ii)

Adding 2r + 1 in both sides
P (r + 1) = 1 + 3 + 5 +..... +2r-1 + 2r +1
= r 2 + (2r + 1) = r2 + 2r +1 = (r+1)2.....................
(iii)
As P(r) is true. Hence P (r+1) is also true.
From (i), (ii) and (iii) we conclude that.
 1 + 3 + 5 +..... + 2n - 1 =n 2 is true for n = 1, 2, 3, 4,
5 ....Hence Proved.

Example 2:

12 + 22 + 32 +.......+ n2 =

Solution: For n = 1,

P (1) = 12 = =1

It is true for n = 1.

Induction Step: For n = r,................... (i)

P (r) = 12 + 22 + 32 +........ + r2 = is true........... (ii)

Adding (r+1)2 on both sides, we get

P (r+1) = 12 + 22 + 32 +.......+ r2+ (r+1)2 = + (r+1)2

As P (r) is true, hence P (r+1) is true.

From (i), (ii) and (iii) we conclude that

12 + 22 + 32 +......+ n2= is true for n = 1, 2, 3, 4, 5 ..... Hence Proved.

Example3: Show that for any integer n

11n+2 + 122n+1 is divisible by 133.

Solution:

Let P (n) = 11n+2+122n+1

For n = 1,
P (1) = 113+123=3059=133 x 23
So, 133 divide P (1).................. (i)

Induction Step: For n = r,

P (r) = 11r+2+122r+1=133 x s............ (ii)

Now, for n = r + 1,
P (r+1) = 11r+2+1+122(r)+3=11[133s-122r+1] + 144. 122r+1
= 11 x 133s + 122r+1.133=133[11s+122r+1]=133 x t........... (iii)
As (i), (ii), and (iii) all are true, hence P (n) is divisible by 133.
Binary Relation

from a set P to Q. If (a, b) ∈ R and R ⊆ P x Q then a is related to b by R i.e., aRb. If sets P

Let P and Q be two non- empty sets. A binary relation R is defined to be a subset of P x Q

and Q are equal, then we say R ⊆ P x P is a relation on P e.g.

1. (i) Let A = {a, b, c}

2. B = {r, s, t}
3. Then R = {(a, r), (b, r), (b, t), (c, s)}
4. is a relation from A to B.
5.
6. (ii) Let A = {1, 2, 3} and B = A
7. R = {(1, 1), (2, 2), (3, 3)}
8. is a relation (equal) on A.

Example1: If a set has n elements, how many relations are there from A to A.

Solution: If a set A has n elements, A x A has n 2 elements. So, there are 2n2 relations
from A to A.

Example2: If A has m elements and B has n elements. How many relations are there
from A to B and vice versa?

Solution: There are m x n elements; hence there are 2m x n relations from A to A.

Example3: If a set A = {1, 2}. Determine all relations from A to A.

Solution: There are 22= 4 elements i.e., {(1, 2), (2, 1), (1, 1), (2, 2)} in A x A. So, there
are 24= 16 relations from A to A. i.e.

1. {(1, 2), (2, 1), (1, 1), (2, 2)}, {(1, 2), (2, 1)}, {(1, 2), (1, 1)}, {(1, 2), (2, 2)},
2. {(2, 1), (1, 1)},{(2,1), (2, 2)}, {(1, 1),(2, 2)},{(1, 2), (2, 1), (1, 1)}, {(1, 2), (1, 1),
3. (2, 2)}, {(2,1), (1, 1), (2, 2)}, {(1, 2), (2, 1), (2, 2)}, {(1, 2), (2, 1), (1, 1), (2, 2)} a
nd ∅.
Domain and Range of Relation

Domain of Relation: The Domain of relation R is the set of elements in P which are
related to some elements in Q, or it is the set of all first entries of the ordered pairs in R.
It is denoted by DOM (R).

Range of Relation: The range of relation R is the set of elements in Q which are related
to some element in P, or it is the set of all second entries of the ordered pairs in R. It is
denoted by RAN (R).

Example:

1. Let A = {1, 2, 3, 4}
2. B = {a, b, c, d}
3. R = {(1, a), (1, b), (1, c), (2, b), (2, c), (2, d)}.
Solution:

DOM (R) = {1, 2}

RAN (R) = {a, b, c, d}
Complement of a Relation

Consider a relation R from a set A to set B. The complement of relation R denoted by R is

a relation from A to B such that

R = {(a, b): {a, b) ∉ R}.

Example:

1. Consider the relation R from X to Y

2. X = {1, 2, 3}
3. Y = {8, 9}
4. R = {(1, 8) (2, 8) (1, 9) (3, 9)}
5. Find the complement relation of R.

Solution:

X x Y = {(1, 8), (2, 8), (3, 8), (1, 9), (2, 9), (3, 9)}
Now we find the complement relation R from X x Y
R = {(3, 8), (2, 9)}

Representation of Relations

Relations can be represented in many ways. Some of which are as follows:

1. Relation as a Matrix: Let P = [a1,a2,a3,.......am] and Q = [b1,b2,b3......bn] are finite sets,

containing m and n number of elements respectively. R is a relation from P to Q. The
relation R can be represented by m x n matrix M = [Mij], defined as

Mij = 0 if (ai,bj) ∉ R
1 if (ai,bj )∈ R

Example

1. Let P = {1, 2, 3, 4}, Q = {a, b, c, d}

2. and R = {(1, a), (1, b), (1, c), (2, b), (2, c), (2, d)}.

The matrix of relation R is shown as fig:

2. Relation as a Directed Graph: There is another way of picturing a relation R when
R is a relation from a finite set to itself.

Example

1. A = {1, 2, 3, 4}
2. R = {(1, 2) (2, 2) (2, 4) (3, 2) (3, 4) (4, 1) (4, 3)}

3. Relation as an Arrow Diagram: If P and Q are finite sets and R is a relation from P
to Q. Relation R can be represented as an arrow diagram as follows.

Draw two ellipses for the sets P and Q. Write down the elements of P and elements of Q

ellipse if a is related to b and a ∈ P and b ∈ Q.

column-wise in three ellipses. Then draw an arrow from the first ellipse to the second

Example

1. Let P = {1, 2, 3, 4}
2. Q = {a, b, c, d}
3. R = {(1, a), (2, a), (3, a), (1, b), (4, b), (4, c), (4, d)

The arrow diagram of relation R is shown in fig:

4. Relation as a Table: If P and Q are finite sets and R is a relation from P to Q.
Relation R can be represented in tabular form.

Make the table which contains rows equivalent to an element of P and columns
equivalent to the element of Q. Then place a cross (X) in the boxes which represent
relations of elements on set P to set Q.

Example

1. Let P = {1, 2, 3, 4}
2. Q = {x, y, z, k}
3. R = {(1, x), (1, y), (2, z), (3, z), (4, k)}.

The tabular form of relation as shown in fig:

Composition of Relations

Let A, B, and C be sets, and let R be a relation from A to B and let S be a relation from B
to C. That is, R is a subset of A × B and S is a subset of B × C. Then R and S give rise to a
relation from A to C indicated by R◦S and defined by:

1. a (R◦S)c if for some b ∈ B we have aRb and bSc.

2. is,
3. R ◦ S = {(a, c)| there exists b ∈ B for which (a, b) ∈ R and (b, c) ∈ S}
The relation R◦S is known the composition of R and S; it is sometimes denoted simply by
RS.

Let R is a relation on a set A, that is, R is a relation from a set A to itself. Then R◦R, the
composition of R with itself, is always represented. Also, R◦R is sometimes denoted by
R2. Similarly, R3 = R2◦R = R◦R◦R, and so on. Thus Rn is defined for all positive n.

Example1: Let X = {4, 5, 6}, Y = {a, b, c} and Z = {l, m, n}. Consider the relation
R1 from X to Y and R2 from Y to Z.

R1 = {(4, a), (4, b), (5, c), (6, a), (6, c)}
R2 = {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)}

Find the composition of relation (i) R1 o R2 (ii) R1o R1-1

Solution:

(i) The composition relation R1 o R2 as shown in fig:

R1 o R2 = {(4, l), (4, n), (4, m), (5, l), (5, m), (5, n), (6, l), (6, m), (6, n)}

(ii) The composition relation R1o R1-1 as shown in fig:

R1o R1-1 = {(4, 4), (5, 5), (5, 6), (6, 4), (6, 5), (4, 6), (6, 6)}

Composition of Relations and Matrices

There is another way of finding R◦S. Let M R and MS denote respectively the matrix
representations of the relations R and S. Then

Example

1. Let P = {2, 3, 4, 5}. Consider the relation R and S on P defined by

2. R = {(2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (5, 3)}
3. S = {(2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 5), (5, 2), (5, 5)}.
4.
5. Find the matrices of the above relations.
6. Use matrices to find the following composition of the relation R and S.
7. (i)RoS (ii)RoR (iii)SoR

Solution: The matrices of the relation R and S are a shown in fig:

(i) To obtain the composition of relation R and S. First multiply M R with MS to obtain the
matrix MR x MS as shown in fig:

The non zero entries in the matrix MR x MS tells the elements related in RoS. So,
Hence the composition R o S of the relation R and S is

1. R o S = {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (4, 2), (4, 5), (5, 2), (5, 3), (5, 4), (5, 5)}
.

(ii) First, multiply the matrix MR by itself, as shown in fig

Hence the composition R o R of the relation R and S is

1. R o R = {(2, 2), (3, 2), (3, 3), (3, 4), (4, 2), (4, 5), (5, 2), (5, 3), (5, 5)}

(iii) Multiply the matrix MS with MR to obtain the matrix MS x MR as shown in fig:

The non-zero entries in matrix MS x MR tells the elements related in S o R.

Hence the composition S o R of the relation S and R is

1. S o R = {(2, 4) , (2, 5), (3, 3), (3, 4), (3, 5), (4, 2), (4, 4), (4, 5), (5, 2), (5, 3), (5, 4),
(5, 5)}.
Closure Properties of Relations
Consider a given set A, and the collection of all relations on A. Let P be a property of such
relations, such as being symmetric or being transitive. A relation with property P will be
called a P-relation. The P-closure of an arbitrary relation R on A, indicated P (R), is a P-
relation such that

1. R ⊆ P (R) ⊆ S

(1) Reflexive and Symmetric Closures: The next theorem tells us how to obtain the
reflexive and symmetric closures of a relation easily.

Theorem: Let R be a relation on a set A. Then:

o R ∪ ∆A is the reflexive closure of R

o R ∪ R-1 is the symmetric closure of R.

Example1:

1. Let A = {k, l, m}. Let R is a relation on A defined by

2. R = {(k, k), (k, l), (l, m), (m, k)}.

Find the reflexive closure of R.

Solution: R ∪ ∆ is the smallest relation having reflexive property, Hence,

RF = R ∪ ∆ = {(k, k), (k, l), (l, l), (l, m), (m, m), (m, k)}.

Example2: Consider the relation R on A = {4, 5, 6, 7} defined by

1. R = {(4, 5), (5, 5), (5, 6), (6, 7), (7, 4), (7, 7)}

Find the symmetric closure of R.

Solution: The smallest relation containing R having the symmetric property is R ∪ R-1,i.e.

RS = R ∪ R-1 = {(4, 5), (5, 4), (5, 5), (5, 6), (6, 5), (6, 7), (7, 6), (7,
4), (4, 7), (7, 7)}.

(2)Transitive Closures: Consider a relation R on a set A. The transitive closure R of a

relation R of a relation R is the smallest transitive relation containing R.

Recall that R2 = R◦ R and Rn = Rn-1 ◦ R. We define

The following Theorem applies:

Theorem1: R* is the transitive closure of R

Suppose A is a finite set with n elements.

 R* = R ∪R2 ∪.....∪ Rn

Theorem 2: Let R be a relation on a set A with n elements. Then

Transitive (R) = R ∪ R2∪.....∪ Rn

Example1: Consider the relation R = {(1, 2), (2, 3), (3, 3)} on A = {1, 2, 3}. Then
R2 = R◦ R = {(1, 3), (2, 3), (3, 3)} and R 3 = R2 ◦ R = {(1, 3), (2, 3), (3, 3)} Accordingly,
Transitive (R) = {(1, 2), (2, 3), (3, 3), (1, 3)}

Example2: Let A = {4, 6, 8, 10} and R = {(4, 4), (4, 10), (6, 6), (6, 8), (8, 10)} is a
relation on set A. Determine transitive closure of R.

Solution: The matrix of relation R is shown in fig:

Now, find the powers of MR as in fig:

Hence, the transitive closure of M R is MR* as shown in Fig (where MR* is the ORing of a
power of MR).
Thus, R* = {(4, 4), (4, 10), (6, 8), (6, 6), (6, 10), (8, 10)}

Equivalence Relations

A relation R on a set A is called an equivalence relation if it satisfies following three

properties:

1. Relation R is Reflexive, i.e. aRa ∀ a∈A.

2. Relation R is Symmetric, i.e., aRb ⟹ bRa

3. Relation R is transitive, i.e., aRb and bRc ⟹ aRc.

Example: Let A = {1, 2, 3, 4} and R = {(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2),
(4, 4)}.

Show that R is an Equivalence Relation.

Solution:

Reflexive: Relation R is reflexive as (1, 1), (2, 2), (3, 3) and (4, 4) ∈ R.

Symmetric: Relation R is symmetric because whenever (a, b) ∈ R, (b, a) also belongs to

R.

Example: (2, 4) ∈ R ⟹ (4, 2) ∈ R.

Transitive: Relation R is transitive because whenever (a, b) and (b, c) belongs to R, (a,
c) also belongs to R.

Example: (3, 1) ∈ R and (1, 3) ∈ R ⟹ (3, 3) ∈ R.

So, as R is reflexive, symmetric and transitive, hence, R is an Equivalence Relation.

Note1: If R1and R2 are equivalence relation then R1∩ R2 is also an equivalence relation.

Example: A = {1, 2, 3}
R1 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
R2 = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}
R1∩ R2 = {(1, 1), (2, 2), (3, 3)}

Note2: If R1and R2 are equivalence relation then R1∪ R2 may or may not be an equivalence
relation.

Example: A = {1, 2, 3}
R1 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
 R1∪ R2= {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2)}
R2 = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}

Hence, Reflexive or Symmetric are Equivalence Relation but transitive may or may not
be an equivalence relation.

Inverse Relation

Let R be any relation from set A to set B. The inverse of R denoted by R -1 is the relations
from B to A which consist of those ordered pairs which when reversed belong to R that is:

R-1 = {(b, a): (a, b) ∈ R}

Example1: A = {1, 2, 3}
B = {x, y, z}

Solution: R = {(1, y), (1, z), (3, y)

R-1 = {(y, 1), (z, 1), (y, 3)}
Clearly (R-1)-1 = R

Note1: Domain and Range of R-1 is equal to range and domain of R.

Example2: R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3), (3, 2)}
R-1 = {(1, 1), (2, 2), (3, 3), (2, 1), (3, 2), (2, 3)}

Note2: If R is an Equivalence Relation then R-1 is always an Equivalence Relation.

Example: Let A = {1, 2, 3}

R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
R-1 = {(1, 1), (2, 2), (3, 3), (2, 1), (1, 2)}
-1
R is a Equivalence Relation.

Note3: If R is a Symmetric Relation then R-1=R and vice-versa.

Example: Let A = {1, 2, 3}

R = {(1, 1), (2, 2), (1, 2), (2, 1), (2, 3), (3, 2)}
R-1 = {(1, 1), (2, 2), (2, 1), (1, 2), (3, 2), (2, 3)}

Partial Order Relations

A relation R on a set A is called a partial order relation if it satisfies the following three
properties:

1. Relation R is Reflexive, i.e. aRa ∀ a∈A.

2. Relation R is Antisymmetric, i.e., aRb and bRa ⟹ a = b.

3. Relation R is transitive, i.e., aRb and bRc ⟹ aRc.

Example1: Show whether the relation (x, y) ∈ R, if, x ≥ y defined on the set of +ve
integers is a partial order relation.

Solution: Consider the set A = {1, 2, 3, 4} containing four +ve integers. Find the
relation for this set such as R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3), (1, 1), (2, 2), (3,
3), (4, 4)}.

Reflexive: The relation is reflexive as for every a ∈ A. (a, a) ∈ R, i.e. (1, 1), (2, 2), (3, 3),
(4, 4) ∈ R.
 45.5M

850

Difference between JDK, JRE, and JVM

Antisymmetric: The relation is antisymmetric as whenever (a, b) and (b, a) ∈ R, we

have a = b.

Transitive: The relation is transitive as whenever (a, b) and (b, c) ∈ R, we have (a, c) ∈
R.

Example: (4, 2) ∈ R and (2, 1) ∈ R, implies (4, 1) ∈ R.

As the relation is reflexive, antisymmetric and transitive. Hence, it is a partial order

relation.

Example2: Show that the relation 'Divides' defined on N is a partial order relation.

Solution:

Reflexive: We have a divides a, ∀ a∈N. Therefore, relation 'Divides' is reflexive.

Antisymmetric: Let a, b, c ∈N, such that a divides b. It implies b divides a iff a = b. So,
the relation is antisymmetric.

Transitive: Let a, b, c ∈N, such that a divides b and b divides c.

Then a divides c. Hence the relation is transitive. Thus, the relation being reflexive,
antisymmetric and transitive, the relation 'divides' is a partial order relation.

Example3: (a) The relation ⊆ of a set of inclusion is a partial ordering or any collection
of sets since set inclusion has three desired properties:

1. A ⊆ A for any set A.

2. If A ⊆ B and B ⊆ A then B = A.

3. If A ⊆ B and B ⊆ C then A ⊆ C

(b) The relation ≤ on the set R of real no that is Reflexive, Antisymmetric and transitive.

(c) Relation ≤ is a Partial Order Relation.

n-Ary Relations

By an n-ary relation, we mean a set of ordered n-tuples. For any set S, a subset of the
product set Sn is called an n-ary relation on S. In particular, a subset of S 3 is called a
ternary relation on S.

Partial Order Set (POSET):

The set A together with a partial order relation R on the set A and is denoted by (A, R) is
called a partial orders set or POSET.
Total Order Relation

Consider the relation R on the set A. If it is also called the case that for all, a, b ∈ A, we
have either (a, b) ∈ R or (b, a) ∈ R or a = b, then the relation R is known total order
relation on set A.

Example: Show that the relation '<' (less than) defined on N, the set of +ve integers is
neither an equivalence relation nor partially ordered relation but is a total order relation.

Solution:

∈
⟹ '<' is not reflexive.
Reflexive: Let a N, then a < a

As, the relation '<' (less than) is not reflexive, it is neither an equivalence relation nor the
partial order relation.

But, as ∀ a, b ∈ N, we have either a < b or b < a or a = b. So, the relation is a total order
relation.

Equivalence Class

Consider, an equivalence relation R on a set A. The equivalence class of an element a ∈

A, is the set of elements of A to which element a is related. It is denoted by [a].

Example: Let R be an equivalence relations on the set A = {4, 5, 6, 7} defined by

R = {(4, 4), (5, 5), (6, 6), (7, 7), (4, 6), (6, 4)}.

Determine its equivalence classes.

Solution: The equivalence classes are as follows:

{4} = {6} = {4, 6}
{5} = {5}
{7} = {7}.

Circular Relation

Consider a binary relation R on a set A. Relation R is called circular if (a, b) ∈ R and (b, c)
∈ R implies (c, a) ∈ R.

Example: Consider R is an equivalence relation. Show that R is reflexive and circular.

Solution: Reflexive: As, the relation, R is an equivalence relation. So, reflexivity is the
property of an equivalence relation. Hence, R is reflexive.

∈ ∈
⇒ (a, c) ∈
Circular: Let (a, b) R and (b, c) R

⇒ (c, a) ∈ R
R (∵ R is transitive)
(∵ R is symmetric)

Thus, R is Circular.

Compatible Relation

A binary relation R on a set A that is Reflexive and symmetric is called Compatible

Relation.
Every Equivalence Relation is compatible, but every compatible relation need not be an
equivalence.

Example: Set of a friend is compatible but may not be an equivalence relation.

Friend Friend
a → b, b→c but possible that a and c are not friends.

Functions

It is a mapping in which every element of set A is uniquely associated at the element

with set B. The set of A is called Domain of a function and set of B is called Co domain.

Domain, Co-Domain, and Range of a Function:

Domain of a Function: Let f be a function from P to Q. The set P is called the domain of
the function f.

Co-Domain of a Function: Let f be a function from P to Q. The set Q is called Co-

domain of the function f.

Range of a Function: The range of a function is the set of picture of its domain. In
other words, we can say it is a subset of its co-domain. It is denoted as f (domain).

1. If f: P → Q, then f (P) = {f(x): x ∈ P} = {y: y ∈ Q | ∃ x ∈ P, such that f (x) = y}.

Example: Find the Domain, Co-Domain, and Range of function.

1. Let x = {1, 2, 3, 4}
2. y = {a, b, c, d, e}
3. f = {(1, b), (2, a), (3, d), (4, c)
Solution:

Domain of function: {1, 2, 3, 4}

Range of function: {a, b, c, d}
Co-Domain of function: {a, b, c, d, e}
Functions as a Set

If P and Q are two non-empty sets, then a function f from P to Q is a subset of P x Q, with
two important restrictions

1. ∀ a ∈ P, (a, b) ∈ f for some b ∈ Q

2. If (a, b) ∈ f and (a, c) ∈ f then b = c.

Note1: There may be some elements of the Q which are not related to any element of set P.
2. Every element of P must be related with at least one element of Q.

Example1: If a set A has n elements, how many functions are there from A to A?

Solution: If a set A has n elements, then there are nn functions from A to A.

Representation of a Function

The two sets P and Q are represented by two circles. The function f: P → Q is represented
by a collection of arrows joining the points which represent the elements of P and
corresponds elements of Q

Example1:

1. Let X = {a, b, c} and Y = {x, y, z} and f: X → Y such that

2. f= {(a, x), (b, z), (c, x)}

Then f can be represented diagrammatically as follows

Example2: Let X = {x, y, z, k} and Y = {1, 2, 3, 4}. Determine which of the following
functions. Give reasons if it is not. Find range if it is a function.

a. f = {(x, 1), (y, 2), (z, 3), (k, 4)

b. g = {(x, 1), (y, 1), (k, 4)

c. h = {(x, 1), (x, 2), (x, 3), (x, 4)

d. l = {(x, 1), (y, 1), (z, 1), (k, 1)}

e. d = {(x, 1), (y, 2), (y, 3), (z, 4), (z, 4)}.

Solution:

1. It is a function. Range (f) = {1, 2, 3, 4}

2. It is not a function because every element of X does not relate with some element
of Y i.e., Z is not related with any element of Y.

3. h is not a function because h (x) = {1, 2, 3, 4} i.e., element x has more than one
image in set Y.

4. d is not a function because d (y) = {2, 3} i.e., element y has more than image in
set Y.

Types of Functions

1. Injective (One-to-One) Functions: A function in which one element of Domain Set

is connected to one element of Co-Domain Set.
2. Surjective (Onto) Functions: A function in which every element of Co-Domain Set
has one pre-image.

Example: Consider, A = {1, 2, 3, 4}, B = {a, b, c} and f = {(1, b), (2, a), (3, c), (4, c)}.

It is a Surjective Function, as every element of B is the image of some A

32.1M

593

History of Java

Note: In an Onto Function, Range is equal to Co-Domain.

3. Bijective (One-to-One Onto) Functions: A function which is both injective (one to -

one) and surjective (onto) is called bijective (One-to-One Onto) Function.
Example:

1. Consider P = {x, y, z}
2. Q = {a, b, c}
3. and f: P → Q such that
4. f = {(x, a), (y, b), (z, c)}

The f is a one-to-one function and also it is onto. So it is a bijective function.

4. Into Functions: A function in which there must be an element of co-domain Y does

not have a pre-image in domain X.

Example:

1. Consider, A = {a, b, c}
2. B = {1, 2, 3, 4} and f: A → B such that
3. f = {(a, 1), (b, 2), (c, 3)}
4. In the function f, the range i.e., {1, 2, 3} ≠ co-domain of Y i.e., {1, 2, 3, 4}

Therefore, it is an into function

5. One-One Into Functions: Let f: X → Y. The function f is called one-one into function if
different elements of X have different unique images of Y.

Example:

1. Consider, X = {k, l, m}
2. Y = {1, 2, 3, 4} and f: X → Y such that
3. f = {(k, 1), (l, 3), (m, 4)}

The function f is a one-one into function

6. Many-One Functions: Let f: X → Y. The function f is said to be many-one functions if

there exist two or more than two different elements in X having the same image in Y.

Example:

1. Consider X = {1, 2, 3, 4, 5}
2. Y = {x, y, z} and f: X → Y such that
3. f = {(1, x), (2, x), (3, x), (4, y), (5, z)}

The function f is a many-one function

7. Many-One Into Functions: Let f: X → Y. The function f is called the many-one
function if and only if is both many one and into function.

Example:

1. Consider X = {a, b, c}
2. Y = {1, 2} and f: X → Y such that
3. f = {(a, 1), (b, 1), (c, 1)}

As the function f is a many-one and into, so it is a many-one into function.

8. Many-One Onto Functions: Let f: X → Y. The function f is called many-one onto

function if and only if is both many one and onto.

Example:

1. Consider X = {1, 2, 3, 4}
2. Y = {k, l} and f: X → Y such that
3. f = {(1, k), (2, k), (3, l), (4, l)}
The function f is a many-one (as the two elements have the same image in Y) and it is
onto (as every element of Y is the image of some element X). So, it is many-one onto
function

Identity Functions

itself i.e. f (a) = a ∀ a ∈ A.

The function f is called the identity function if each element of set A has an image on

It is denoted by I.

Example:

1. Consider, A = {1, 2, 3, 4, 5} and f: A → A such that

2. f = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)}.

The function f is an identity function as each element of A is mapped onto itself. The
function f is a one-one and onto

32.1M

593

History of Java
Invertible (Inverse) Functions

A function f: X → Y is invertible if and only if it is a bijective function.

Consider the bijective (one to one onto) function f: X → Y. As f is a one to one, therefore,
each element of X corresponds to a distinct element of Y. As f is onto, there is no element
of Y which is not the image of any element of X, i.e., range = co-domain Y.

The inverse function for f exists if f-1 is a function from Y to X.

Example:

1. Consider, X = {1, 2, 3}
2. Y = {k, l, m} and f: X→Y such that
3. f = {(1, k), (2, m), (3, l)

The inverse function of f is shown in fig:

 Compositions of Functions

Consider functions, f: A → B and g: B → C. The composition of f with g is a function from A

into C defined by (gof) (x) = g [f(x)] and is defined by gof.

To find the composition of f and g, first find the image of x under f and then find the
image of f (x) under g.

Example1:

1. Let X = {1, 2, 3}
2. Y = {a, b}
3. Z = {5, 6, 7}.

Consider the function f = {(1, a), (2, a), (3, b)} and g = {(a, 5), (b, 7)} as in figure. Find
the composition of gof.

Solution: The composition function gof is shown in fig:

(gof) (1) = g [f (1)] = g (a) = 5, (gof) (2) = g [f (2)] = g (a) = 5
(gof) (3) = g [f (3)] = g (b) = 7.

Example2: Consider f, g and h, all functions on the integers, by f (n) =n 2, g (n) = n + 1

and h (n) = n - 1.

Determine (i) hofog (ii) gofoh (iii) fogoh.

Solution:

(i) hofog (n) = n + 1,

hofog (n + 1) = (n+1)2
h [(n+1)2 ] = (n+1)2 - 1 = n2 + 1 + 2n - 1 = n2 + 2n.

(ii) gofoh (n) = n - 1, gof (n - 1) = (n-1)2

g [(n-1)2 ] = (n-1)2 + 1 = n2 + 1 - 2n + 1 = n2 - 2n + 2.

(iii) fogoh (n) = n - 1

fog (n - 1) = (n - 1) + 1
f (n) = n2.

Note:

o If f and g are one-to-one, then the function (gof) (gof) is also one-to-one.

o If f and g are onto then the function (gof) (gof) is also onto.

o Composition consistently holds associative property but does not hold

commutative property.

Mathematical Functions

The following are the functions which are widely used in computer science.

1. Floor Functions: The floor function for any real number x is defined as f (x) is the
greatest integer 1 less than or equal to x. It is denoted by [x].

Example: Determine the value of

(i)[3. 5] (ii)[-2.4] (iii)[3. 143].

Solution:

(i)[3 . 5] = 3
(ii) [-2 .4] = -3
(iii) [3. 143] = 3

2. Ceiling Functions: The ceiling function for any real number x is defined as h (x) is
the smallest integer greater than or equal to x. It is denoted by [x].

Example: Determine the value of

(i)[3. 5] (ii) [-2.4] (iii) [3. 143].

Solution:

(i)[3. 5] = 4
(ii) [-2 .4] = -2
(iii) [3. 143] = 4.

3. Remainder Functions: The integer remainder is obtained when some a is divided by

m. It is denoted by a (MOD m). We can also define it as, a (MOD m) is the unique integer
t such that a = Mq + t. Here q is quotient 0 ≤ r < M.

Example: Determine the value of the following:

(i) 35 (MOD 7) (ii) 20 (MOD 3) (iii) 4 (MOD 9)

Solution:

(i) 35 (MOD 7) = 0
(ii) 20 (MOD 3) = 2
(iii) 4 (MOD 9) = 4

4. Exponential Functions: Consider two sets A and B. Let A = B = I + and also let f: A →
B be defined by f (n) = kn. Here n is a +ve integer. The function f is called the base k
exponential function.

Note1: k t= k. k. k.......k (t times).

2: k0=1,k-M=

3. For rational number, a/b, the exponential function is

Example: Determine the value of the following:

(i) 103 (ii) 51/2 (iii) 3-5

Solution:

103= 10. 10. 10 = 1000

51/2=2.23607

3-5=

5. Logarithmic Functions: Consider two sets A and B. Let A = B = R (the set of real
numbers and also let f_n:A→B be defined for each positive integer n > 1 as f n (x)=logn(x)
the base n of x.
Note1: k = logn x and nk are equivalent.
2. For any base n, logn 1=0 as n0=1.
3. For any base n, logn n=1 as n1=n.

Example: Determine the value of the following:

(i) log2?16 (ii) log2 100 (iii) log_2 0.001.

Solution:

(i)log216 = 4 as 24=16.
(ii)log2 100 = 6 as 26= 64 but 27=128 which is greater

(iii)log2 0.001=-9 as 2-9= but 2-10= which is greater.

Algorithms and Functions

Algorithm: An algorithm is a step-by-step method for solving some problem.

Characteristics of Algorithms:

Algorithms generally have the following characteristics:

1. Input: The algorithm receives input. Zero or more quantities are externally
supplied.

2. Output: The algorithm produces output. At least one quantity is produced.

3. Precision: The steps are precisely stated. Each instruction is clear and
unambiguous.

4. Feasibility: It must be feasible to execute each instruction.

5. Flexibility: It should also be possible to make changes in the algorithm without

putting so much effort on it.

6. Generality: The algorithm applies to a set of inputs.

7. Finiteness: Algorithm must complete after a finite number of instruction have

been executed.

Analysis (Complexity) of Algorithms

The Analysis of an algorithm refers to the process of deriving estimates for the time and
space needed to execute the algorithm.

It is important to estimate the time (e.g., the number of steps) and space (e.g., the
number of variables) required by algorithms. Knowing the time and space required by
algorithm allows us to compare the algorithms that solve the same problem. For
example, if one algorithm takes n steps to solve a problem and another algorithm takes
n^2 steps to solve the same problem, we would prefer the first algorithm. This
estimation of time and space needed to execute the algorithm is called the time and
space complexity of the algorithm.

The time required to execute an algorithm is a function of the input. Instead of

dealing directly with the input, parameters are used to characterize the size of the input.
e.g. if the input is a set containing n elements, the size of the input n. There are three
cases worth noting about the time complexity of an algorithm since determining the
exact time complexity of an algorithm in a difficult task.

o Worst-case: f (n) represent by the maximum number of steps taken on any

instance of size n.

o Best-case: f (n) represent by the minimum number of steps taken on any

instance of size n.

o Average case: f (n) represent by the average number of steps taken on any
instance of size n.

Asymptotic Notations

Asymptotic Notations are used to describe the execution time of an algorithm. The
notations show the order of growth of functions. Here the time taken by an algorithm is
mapped regarding mathematical functions. There are many asymptotic notations like 0,
θ, Ω,w each having its importance.

1. Big-oh notation: The function f (n) =O (g (n)) [read as "f of n is big-oh of g of n"] if
and only if exist positive constant c and n0 such that

f (n) ⩽ C x g (n) for all n, n ≥ n0

Example1: The function 4n + 3 = O (n) as 4n + 3 ⩽ 5n for all n ≥.

Example2: The function 20n2 + 5n + 2 = O (n2) as 20n2+ 5n +2⩽21n2 for all n ≥.

2. Omega (Ω) Notation: The function f (n) = Ω (g (n)) [read as "f of n is omega of g of
n"] if and only if there exists positive constant c and n 0 such that

f (n) ≥ C* g (n) for all n, n ≥ n0

Example1: The function 4n + 3 = Ω (n) as 4n + 3 ≥ 4n for all n ≥1.

Example2: The function 20n2+ 5n +2 = Ω (n) as 20n2+ 5n +2 ≥ 20n2 for all n ≥1.

3. Theta (θ): The function f (n) = θ (g (n)) [read as "f is the theta of g of n"] if and only if
there exists positive constant k1, k2 and k0 such that

k1* g (n) ≤ f (n)≤k2* g(n)for all n, n≥n0

Example1: The function 4n + 3 = θ (n) as 4n + 3 ≥ 4n for all n ≥ 3 and 4n + 3 ≤ 5n for

all n ≥ 3.

Example2: The function 20n2+ 5n +2 = θ (n2) as 20n2+ 5n +2 ≤ 21n2 for all n ≥1 and
20n2+ 5n +2 ≥ 20n2 for all n ≥ 1.

Counting Techniques
Basic Counting Principles

Sum Rule Principle: Assume some event E can occur in m ways and a second event F
can occur in n ways, and suppose both events cannot occur simultaneously. Then E or F
can occur in m + n ways.

In general, if there are n events and no two events occurs in same time then the event
can occur in n1+n2..........n ways.

Example: If 8 male processor and 5 female processor teaching DMS then the student
can choose professor in 8+5=13 ways.

Product Rule Principle: Suppose there is an event E which can occur in m ways and,
independent of this event, there is a second event F which can occur in n ways. Then
combinations of E and F can occur in mn ways.

46.2M

932

Exception Handling in Java - Javatpoint

In general, if there are n events occurring independently then all events can occur in the
order indicated as n1 x n2 x n3.........n ways.

Example: In class, there are 4 boys and 10 girls if a boy and a girl have to be chosen for
the class monitor, the students can choose class monitor in 4 x 10 = 40 ways.

Mathematical Functions:

Factorial Function: The product of the first n natural number is called factorial n. It is
denoted by n!, read "n Factorial."

The Factorial n can also be written as

1. n! = n (n-1) (n-2) (n-3)......1.

2. = 1 and 0! = 1.

Example1: Find the value of 5!

Solution:

5! = 5 x (5-1) (5-2) (5-3) (5-4)

= 5 x 4 x 3 x 2 x 1 = 120

Example2: Find the value of

Solution: = = 10 x 9=90
Binomial Coefficients: Binomial Coefficient is represented by n Cr where r and n are
positive integer with r ≤ n is defined as follows:

Example: 8C2 = = = 28.

Permutation and Combinations:

Permutation:

Any arrangement of a set of n objects in a given order is called Permutation of Object.

Any arrangement of any r ≤ n of these objects in a given order is called an r-permutation
or a permutation of n object taken r at a time.

It is denoted by P (n, r)

P (n, r) =

Theorem: Prove that the number of permutations of n things taken all at a time is n!.

Proof: We know that

Example: 4 x np3=n+1P3

Solution: 4 x

4 (n-2) = (n+1)
4n - 8 = n+1
3n = 9
n = 3.

Permutation with Restrictions:

The number of permutations of n different objects taken r at a time in which p particular

objects do not occur is

The number of permutations of n different objects taken r at a time in which p particular

objects are present is
Example: How many 6-digit numbers can be formed by using the digits 0, 1, 2, 3, 4, 5,
6, 7, 8 if every number is to start with '30' with no digit repeated?

Solution: All the numbers begin with '30.'So, we have to choose 4-digits from the
remaining 7-digits.

∴ Total number of numbers that begins with '30' is

7P4 = =840.

Permutations with Repeated Objects:

Theorem: Prove that the number of different permutations of n distinct objects taken at
a time when every object is allowed to repeat any number of times is given by n r.

Proof: Assume that with n objects we have to fill r place when repetition of the object is
allowed.

Therefore, the number of ways of filling the first place is = n

The number of ways of filling the second place = n
.............................
.............................
The number of ways of filling the rth place = n
Thus, the total number of ways of filling r places with n elements is
= n. n. n..............r times =nr.

Circular Permutations:

A permutation which is done around a circle is called Circular Permutation.

Example: In how many ways can get these letters a, b, c, d, e, f, g, h, i, j arranged in a

circle?

Solution: (10 - 1) = 9! = 362880

Theorem: Prove that the number of circular permutations of n different objects is (n-1)!

Proof: Let us consider that K be the number of permutations required.

For each such circular permutations of K, there are n corresponding linear permutations.
As shown earlier, we start from every object of n object in the circular permutations.
Thus, for K circular permutations, we have K...n linear permutations.

Combination:

A Combination is a selection of some or all, objects from a set of given objects, where the
order of the objects does not matter. The number of combinations of n objects, taken r at
a time represented by nCr or C (n, r).

Proof: The number of permutations of n different things, taken r at a time is given by

As there is no matter about the order of arrangement of the objects, therefore, to every
combination of r things, there are r! arrangements i.e.,

Example: A farmer purchased 3 cows, 2 pigs, and 4 hens from a man who has 6 cows, 5
pigs, and 8 hens. Find the number m of choices that the farmer has.

The farmer can choose the cows in C (6, 3) ways, the pigs in C (5, 2) ways, and the hens
in C (8, 4) ways. Thus the number m of choices follows:

The Pigeonhole Principle

If n pigeonholes are occupied by n+1 or more pigeons, then at least one pigeonhole is
occupied by greater than one pigeon. Generalized pigeonhole principle is: - If n
pigeonholes are occupied by kn+1 or more pigeons, where k is a positive integer, then at
least one pigeonhole is occupied by k+1 or more pigeons.

Example1: Find the minimum number of students in a class to be sure that three of
them are born in the same month.
Solution: Here n = 12 months are the Pigeonholes
And k + 1 = 3
K=2

Example2: Show that at least two people must have their birthday in the same month if
13 people are assembled in a room.

Solution: We assigned each person the month of the year on which he was born. Since
there are 12 months in a year.

So, according to the pigeonhole principle, there must be at least two people assigned to
the same month.

Inclusion-Exclusion Principle:

Let A1,A2......Ar be the subset of Universal set U. Then the number m of the element which
do not appear in any subset A1,A2......Ar of U.

Example: Let U be the set of positive integer not exceeding 1000. Then |U|= 1000 Find |
S| where S is the set of such integer which is not divisible by 3, 5 or 7?

Solution: Let A be the subset of integer which is divisible by 3

Let B be the subset of integer which is divisible by 5
Let C be the subset of integer which is divisible by 7

Then S = Ac ∩ Bc∩ Cc since each element of S is not divisible by 3, 5, or 7.

By Integer division,

|A|= 1000/3 = 333

|B|= 1000/5 = 200
|C| = 1000/7 = 142
|A∩B|=1000/15=66
|B∩C|=1000/21=47
|C∩A|=1000/35=28
|A∩B∩C|=1000/105=9

Thus by Inclusion-Exclusion Principle

|S|=1000-(333+200+142)+(66+47+28)-9
|S|=1000-675+141-9=457

Recurrence Relations

A recurrence relation is a functional relation between the independent variable x,

dependent variable f(x) and the differences of various order of f (x). A recurrence relation
is also called a difference equation, and we will use these two terms interchangeably.

Example1: The equation f (x + 3h) + 3f (x + 2h) + 6f (x + h) + 9f (x) = 0 is a recurrence

relation.

It can also be written as

ar+3 + 3ar+2 + 6ar+1 + 9ar = 0

yk+3 + 3yk+2 + 6yk+1 + 9yk = 0
Example2: The Fibonacci sequence is defined by the recurrence relation a r = ar-2 + ar-1,
r≥2,with the initial conditions a0=1 and a1=1.

Order of the Recurrence Relation:

The order of the recurrence relation or difference equation is defined to be the difference
between the highest and lowest subscripts of f(x) or a r=yk.

Example1: The equation 13ar+20ar-1=0 is a first order recurrence relation.

Example2: The equation 8f (x) + 4f (x + 1) + 8f (x+2) = k (x)

Degree of the Difference Equation:

The degree of a difference equation is defined to be the highest power of f (x) or a r=yk

Example1: The equation y3k+3+2y2k+2+2yk+1=0 has the degree 3, as the highest power of
yk is 3.

Example2: The equation a4r+3a3r-1+6a2r-2+4ar-3 =0 has the degree 4, as the highest

power of ar is 4.

Example3: The equation yk+3 +2yk+2 +4yk+1+2yk= k(x) has the degree 1, because the
highest power of yk is 1 and its order is 3.

Example4: The equation f (x+2h) - 4f(x+h) +2f(x) = 0 has the degree1 and its order is
2.

Recurrence Relations

A recurrence relation is a functional relation between the independent variable x,

dependent variable f(x) and the differences of various order of f (x). A recurrence relation
is also called a difference equation, and we will use these two terms interchangeably.

Example1: The equation f (x + 3h) + 3f (x + 2h) + 6f (x + h) + 9f (x) = 0 is a recurrence

relation.

It can also be written as

ar+3 + 3ar+2 + 6ar+1 + 9ar = 0

yk+3 + 3yk+2 + 6yk+1 + 9yk = 0

Example2: The Fibonacci sequence is defined by the recurrence relation a r = ar-2 + ar-1,
r≥2,with the initial conditions a0=1 and a1=1.

46.2M

932

Exception Handling in Java - Javatpoint

Order of the Recurrence Relation:

The order of the recurrence relation or difference equation is defined to be the difference
between the highest and lowest subscripts of f(x) or a r=yk.

Example1: The equation 13ar+20ar-1=0 is a first order recurrence relation.

Example2: The equation 8f (x) + 4f (x + 1) + 8f (x+2) = k (x)

Degree of the Difference Equation:

The degree of a difference equation is defined to be the highest power of f (x) or a r=yk

Example1: The equation y3k+3+2y2k+2+2yk+1=0 has the degree 3, as the highest power of
yk is 3.

Example2: The equation a4r+3a3r-1+6a2r-2+4ar-3 =0 has the degree 4, as the highest

power of ar is 4.

Example3: The equation yk+3 +2yk+2 +4yk+1+2yk= k(x) has the degree 1, because the
highest power of yk is 1 and its order is 3.

Example4: The equation f (x+2h) - 4f(x+h) +2f(x) = 0 has the degree1 and its order is
2.

Linear Recurrence Relations with Constant Coefficients

A Recurrence Relations is called linear if its degree is one.

The general form of linear recurrence relation with constant coefficient is

C0 yn+r+C1 yn+r-1+C2 yn+r-2+⋯+Cr yn=R (n)

Where C0,C1,C2......Cn are constant and R (n) is same function of independent variable n.

A solution of a recurrence relation in any function which satisfies the given equation.

Linear Homogeneous Recurrence Relations with Constant Coefficients:

The equation is said to be linear homogeneous difference equation if and only if R (n) = 0
and it will be of order n.

The equation is said to be linear non-homogeneous difference equation if R (n) ≠ 0.

Example1: The equation ar+3+6ar+2+12ar+1+8ar=0 is a linear non-homogeneous

equation of order 3.

Example2: The equation ar+2-4ar+1+4ar= 3r + 2r is a linear non-homogeneous equation

of order 2.

A linear homogeneous difference equation with constant coefficients is given by

C0 yn+C1 yn-1+C2 yn-2+⋯......+Cr yn-r=0 ....... equation (i)

Where C0,C1,C2.....Cn are constants.

The solution of the equation (i) is of the form , where ∝1 is the characteristics root
and A is constant.

Substitute the values of A ∝K for yn in equation (1), we have

C0 A∝K+C1 A∝K-1+C2 A∝K-2+⋯....+Cr A∝K-r=0.......equation (ii)

After simplifying equation (ii), we have

C0 ∝r+C1 ∝r-1+C2 ∝r-2+⋯Cr=0..........equation (iii)

The equation (iii) is called the characteristics equation of the difference equation.

If ∝1 is one of the roots of the characteristics equation, then is a homogeneous

solution to the difference equation.

To find the solution of the linear homogeneous difference equations, we have the four
cases that are discussed as follows:

Case1: If the characteristic equation has n distinct real roots∝1, ∝2, ∝3,.......∝n.

Thus, are all solutions of equation (i).

Also, we have are all solutions of equation (i). The sums

of solutions are also solutions.

Hence, the homogeneous solutions of the difference equation are

Case2: If the characteristics equation has repeated real roots.

If ∝1=∝2, then (A1+A2 K) is also a solution.

If ∝1=∝2=∝3 then (A1+A2 K+A3 K2) is also a solution.

Similarly, if root ∝1 is repeated n times, then.

(A1+A2 K+A3 K2+......+An Kn-1)

The solution to the homogeneous equation.

Case3: If the characteristics equation has one imaginary root.

If α+iβ is the root of the characteristics equation, then α-iβ is also the root, where α and
β are real.

Thus, (α+iβ)K and (α-iβ)K are solutions of the equations. This implies

(α+iβ)K A1+α-iβ)K A2

Is also a solution to the characteristics equation, where A 1 and A2 are constants which are
to be determined.

Case4: If the characteristics equation has repeated imaginary roots.

When the characteristics equation has repeated imaginary roots,

 (C1+C2 k) (α+iβ)K +(C3+C4 K)(α-iβ)K

Is the solution to the homogeneous equation.

Example1: Solve the difference equation ar-3ar-1+2ar-2=0.

Solution: The characteristics equation is given by

⇒ s = 1, 2
s2-3s+2=0 or (s-1)(s-2)=0

Therefore, the homogeneous solution of the equation is given by

ar=C1r+C2.2r.

Example2: Solve the difference equation 9yK+2-6yK+1+yK=0.

Solution: The characteristics equation is

9s2-6s+1=0 or (3s-1)2=0

⇒s= and

Therefore, the homoeneous solution of the equation is given by

yK=(C1+C2 k).

Example3: Solve the difference equation yK-yK-1-yK-2=0.

Solution: The characteristics equation is s2-s-1=0

s=

Therefore, the homogeneous solution of the equation is

Example4: Solve the difference equation yK+4+4yK+3+8yK+2+8yK+1+4yK=0.

Solution: The characteristics equation is s4+4s3+8s2+8s+4=0

2
(s +2s+2) (s2+2s+2)=0
s = -1±i,-1±i

Therefore, the homogeneous solution of the equation is given by

yK=(C1+C2 K)(-1+i)K+(C3 +C4 K)(-1-i)

Particular Solution
(a) Homogeneous Linear Difference Equations and Particular Solution:

We can find the particular solution of the difference equation when the equation is of
homogeneous linear type by putting the values of the initial conditions in the
homogeneous solutions.

Example1: Solve the difference equation 2ar-5ar-1+2ar-2=0 and find particular solutions
such that a0=0 and a1=1.

Solution: The characteristics equation is 2s 2-5s+2=0

(2s-1)(s-2)=0

s= and 2.

Therefore, the homogeneous solution of the equation is given by

ar(h)= C1 +C2 .2r..........equation (i)

Putting r=0 and r=1 in equation (i), we get

a0=C1+C2=0...........equation (a)

a1= C1+2C2=1...........equation.(b)

Solving eq (a) and (b), we have

C1=- and C2=

Hence, the particular solution is

Example2: Solve the difference equation ar-4ar-1+4ar-2=0 and find particular solutions
such that a0=0 and a1=6.

Solution: The characteristics equation is

s2-4s+4=0 or (s-2)2=0 s = 2, 2

Therefore, the homogeneous solution of the equation is given by

ar(n)=(C1+C2 r).2r.............. equation (i)

Putting r = 0 and r = 1 in equation (i), we get

a0=(C1+0).20 = 1 ∴C1=1
a1=(C1+C2).2=6 ∴C1+C2=3⇒C2=2

Hence, the particular solution is

ar(P)=(1+2r).2r.

Example3: Solve the difference equation 9ar-6ar-1+ar-2=0 satisfying the conditions a0=0
and a1=2.
Solution: The characteristics equation is

9s2-6s+1=0 or (3s-1)2=0

s=

Therefore, the homogeneous solution of the equation is given by

ar(h)=(C1+C2 r). ..........equation (i)

Putting r = 0 and r = 1 in equation (i), we get

a0=C_1=0

a1= (C1+C2). =2. ∴C1+C2=6⇒C2=6

Hence, the particular solution is

ar(P)=6r. .

(b) Non-Homogeneous Linear Difference Equations and Particular Solution:

There are two methods to find the particular solution of a non-homogeneous linear
difference equation. These are as follows:

1. Undetermined coefficients method

2. E and ∆ operator method.

1. Undetermined Coefficients Method: This method is used to find a particular

solution of non-homogeneous linear difference equations, whose R.H.S term R (n) consist
of terms of special forms.

In this method, firstly we assume the general form of the particular solutions according to
the type of R (n) containing some unknown constant coefficients, which have to be
determined. Then according to the difference equation, we will determine the exact
solution.

The general form of a particular solution to be assumed for the special forms of R (n), to
find the exact solution is shown in the table.

Form of R (n) General form to be assumed

Z, here z is constant A

Zr, here z is constant Zr

P (r), a polynomial of degree n A0 rn+A1 rn-1+⋯..An

Zr. P (r), here P(r) is a polynomial of the nth degree in r. Z is a [A0 rn+A1 rn-1+⋯..An].Zr
constant.
Example1: Find the particular solution of the difference equation a r+2-
3ar+1+2ar=Zr ........equation (i)

Where Z is some constant.

Solution: The general form of solution is = A. Zr

Now putting this solution on L.H.S of equation (i), we get

= A Zr+2-3AZr+1+2AZr=(Z2-3Z+2) A Zr.........equation (ii)

Equating equation (ii) with R.H.S of equation (i), we get

(Z2-3Z+2)A=1

A= (Z≠1, Z≠2)

Therefore, the particular solution is

Example2: Find the particular solution of the difference equation a r+2-

5ar+1+6ar=5r .............equation (i)

Solution: Let us assume the general form of the solution= A. 5r.

Now to find the value of A, put this solution on L.H.S of the equation (i), then this
becomes
= A. 5r+2-5.A5r+1+6.A5r
= 25A. 5r-25A.5r+6A.5r
r
= 6A.5 ............equation (ii)

Equating equation (ii) to R.H.S of equation (i), we get

A=

Therefore, the particular solution of the difference equation is = .5r.

Example3: Find the particular solution of the difference equation

ar+ 2+ar+1+ar=r.2r..........equation (i)

Solution: Let us assume the general form of the solution = (A0+A1r). 2^r

Now, put these solutions

in the L.H.S of the equation (i), we get
= 2r+2 [A0+A1 (r+2)]+2r+1 [A0+A1 (r+1)]+2r (A0+A1 r)
= 4. 2r (A0+A1 r+2A1 )+2.2r (A0+A1 r+A1 )+2r (A0+A1 r)
r r
= r. 2 (7A1 )+2 (7A0+10A1)............equation (ii)

Equating equation (ii) with R.H.S of equation (i), we get

7A1=1 ∴ A 1=

7A0+10A1=0 ∴ A 0=
Therefore, the particular solution is

2. E and ∆ operator Method:

Definition of Operator E: The operator of E on f(x) means that give an increment to

the value of x in the function. The operation of E is, put (x+h) in the function wherever
there is x. Here h is increment quantity. So Ef(x) = f(x+h)

Here, E is operated on f(x), therefore, E is a symbol known as shift operator.

Definition of Operator∆: The operation ∆ is an operation of two steps.

Firstly, x in the function is incremented by a constant and then former is subtracted from
the later i.e.,
∆f(x)=f(x+h)-f(x)

Theorem1: Prove that E ≅1+∆.

Proof: The operation of ∆ on f(x) is of two steps. First, increment the value of x in the
function. So, whenever, there is x in f(x) put x+h (here h is constant increment), which
means operation of E on f(x) i.e.,
f (x+h)=Ef(x).

Second, subtract the original function from the value obtained in the first step, hence
∆f(x)=Ef(x)-1f(x)=(E-1)f(x)

So, the operation of ∆ on f(x) is equivalent to the operation of (E-1) on f(x).

E ≅1+∆.
Therefore, we have

Theorem2: Show that En f(x)=f(x+nh).

Proof: We know that E f(x) =f (x+h)

Now En f(x)=E.E.E.E.........n times f(x)

= En-1 [E f(x)] = En-1 f(x+h)
= n-2
E [E f(x+h)] = En-2 f(x+2h)
......................
......................
= E f[x+ (n-1) h] = f(x+nh).

Theorem3: Show that E Cf(x) = CE f(x)

Proof: We know that E C f(x) = C f(x+h) = CE f(x+h). Hence Proved.

There is no effect of the operation of E on any constant. Therefore, the operation of E on

any constant will be equal to constant itself.

By E and ∆ operator method, we will find the solution of

C0 yn+r+C1 yn+r-1+C2 yn+r-2+⋯+Cn yn=R (n)..............equation (i)

Equation (i) can be written as

C0 Er yn+C1 Er-1 yn+C2 Er-2 yn+⋯+Cn yn=R (n)
 (C0 Er+C1 Er-1+C2 Er-2+⋯+Cn) yn=R (n)
r r-1 r-2
Putting C0 E +C1 E +C2 E +⋯+Cn=P(E)

So P (E) yn=R (n)

∴ yn= ................equation (ii)

To find the particular solution of (ii) for different forms of R (n), we have the following
cases.

Case1: When R (n) is some constant A.

We know that, the operation of E on any constant will be equal to the constant itself i.e.,
EA=A
Therefore, P (E) A = (C0 Er+C1 Er-1+C2 Er-2+⋯+Cn)A
= (C0+C1+C2+⋯+Cn)A
= P (1) A

Therefore, using equation (ii), the particular solution of (i) is

yn = ,P(1)≠0

P (1) is obtained by putting E = 1 in P (E).

Case2: When R (n) is of the form A. Zn, where A and Z are constants

We have, P (E) (A. Zn)={C0 Er+C1 Er-1+⋯+ Cn} (A.Zn)

r+n
=A{C0 Z +C1 Z r+n-1
+⋯+Cn Zn}
= A{C0 Z +C1 Z +⋯+Cn }. Zn
r r-1

=AP(Z).Zn

To get, P (Z) put E=Z in P (E)

Therefore, , provided P (Z) ≠ 0

Thus, yn = , P (Z) ≠ 0

If A = 1, then yn=

When P (Z) = 0 then for equation

(i) (E-Z) yn= A. Zn

For this, the particular solution becomes A. Zn=A. n Zn-1

(ii) (E-Z)2 yn= A. Zn

For this, the particular solution becomes

(iii) (E-Z)3 yn= A. Zn

For this, the particular solution becomes and so on.

Case3: When R (n) be a polynomial of degree m is n.

We know that E≅1+∆

So, P (E) =P (1+∆)

Which can be expanded in ascending power of ∆ as far as upto ∆ m

⇒ =(b0+b1 ∆+b2 ∆+⋯.+bm ∆m+⋯)

⇒ .R(n)=( b0+b1 ∆+b2 ∆+⋯.+bm ∆m+⋯).R(n)

= b0 R(n)+b1 ∆ R(n)+⋯+bm ∆m R(n)

All other higher terms will be zero because R (n) is a polynomial of degree m.

Thus, the particular solution of equation (i), in this case will be

yn=b0 R(n)+b1 ∆ R(n)+⋯.+bm ∆m R(n).

Case4: When R (n) is of the form R(n).Z n,where R(n) is a polynomial of degree m and Z is
some constant

We have Er[Zn R(n)]=Zr+n R (n+r)=Zr.Zn.Er.R(n)=Zn (ZE)rR(n)

Similarly, we have

[Zn R(n)]=Zn .(R(n))= Zn [P(Z+Z∆)]-1.R(n)

Thus, the particular solution of equation (i), in this case will be

yn=Zn [P(Z+Z∆)]-1.R(n)

Example1: Find the particular solution of the difference equation

2ar+1-ar=12.

Solution: The above equation can be written as

(2E-1) ar=12

The particular solution is given by

ar = .12

Put E=1, in the equation. The particular solution is a r=12

Example2: Find the particular solution of the difference equation a r-4ar-1+4ar-2=2r.

Solution: The above equation can be written as

(E2-4E+4) ar=2r

Therefore, P (E) = E2-4E+4 = (E-2)2

Thus, the particular solution is given by

Total Solution

The total solution or the general solution of a non-homogeneous linear difference

equation with constant coefficients is the sum of the homogeneous solution and a
particular solution. If no initial conditions are given, obtain n linear equations in n
unknowns and solve them, if possible to get total solutions.

If y(h) denotes the homogeneous solution of the recurrence relation and y (p) indicates the
particular solution of the recurrence relation then, the total solution or the general
solution y of the recurrence relation is given by
y =y(h)+y(p).

Example: Solve the difference equation

ar-4ar-1+4ar-2=3r+2r...........equation (i)

Solution: The homogeneous solution of this equation is obtained by putting R.H.S equal
to zero i.e.,
ar-4ar-1+4ar-2=0

The homogeneous solution is ar(h)= (C1+C2 r).2r

The equation (i) can be written as (E2-4E+4) ar=3r+2r

The particular solution is given as

Generating Functions

Generating function is a method to solve the recurrence relations.

Let us consider, the sequence a 0, a1, a2....ar of real numbers. For some interval of real
numbers containing zero values at t is given, the function G(t) is defined by the series
G(t)= a0, a1t+a2 t2+⋯+ar tr+............equation (i)

This function G(t) is called the generating function of the sequence a r.

Now, for the constant sequence 1, 1, 1, 1.....the generating function is

It can be expressed as

G(t) =(1-t)-1=1+t+t2 +t3+t4+⋯[By binomial expansion]

Comparing, this with equation (i), we get

a0=1,a1=1,a2=1 and so on.

For, the constant sequence 1,2,3,4,5,..the generating function is

G(t) = because it can be expressed as

G(t) =(1-t)-2=1+2t+3t2 +4t3+⋯+(r+1) tr

Comparing, this with equation (i), we get

a0=1,a1=2,a2=3,a3=4 and so on.

The generating function of Z r,(Z≠0 and Z is a constant)is given by

G(t)= 1+Zt+Z2 t2+Z3 t3+⋯+Zr tr

G(t)= [Assume |Zt|<1]

So, G(t)= generates Zr,Z≠0

Also,If a(1)r has the generating function G1(t) and a(2)r has the generating function G2(t),
then λ1 a(1)r+λ2 a(2)r has the generating function λ 1 G1(t)+ λ2 G2(t). Here λ1 and λ2 are
constants.

Application Areas:

Generating functions can be used for the following purposes -

o For solving recurrence relations

o For proving some of the combinatorial identities

o For finding asymptotic formulae for terms of sequences

Example: Solve the recurrence relation ar+2-3ar+1+2ar=0

By the method of generating functions with the initial conditions a 0=2 and a1=3.

Solution: Let us assume that

Multiply equation (i) by tr and summing from r = 0 to ∞, we have

(a2+a3 t+a4 t2+⋯)-3(a1+a2 t+a3 t2+⋯)+2(a0+a1 t+a2 t2+⋯)=0

[∴ G(t)=a0+a1 t+a2 t2+⋯]
 +2G(t)=0............equation (ii)

Now, put a0=2 and a1=3 in equation (ii) and solving, we get

Put t=1 on both sides of equation (iii) to find A. Hence

-1=- A ∴A=1

Put t= on both sides of equation (iii) to find B. Hence

= B ∴B=1

Thus G (t) = .Hence,ar=1+2r