B tech. Discrete mathematics (I. T & Comp. Science Engg.) Syllabus

Example : Fibonacci sequence is also an example of a linear homogeneous recurrence relation of degree 2.

^{Example: The recurrence relation a}_n ^{ an-1 not linear (due to}  an-

square term), whereas the relation H_n = 2H_n–1 + 1 is not homogeneous (due to constant 1).

The basic approach for solving a linear homogeneous recurrence relation to look for the solution of the form a_n = rⁿ, where r is constant. Note that, rⁿ is a solution to the linear homogeneous recurrence relation of

degree k, if and only if;

rⁿ  ^c1

_rn 1 _

c_{2 r}^{n 2} _{… } c_k

r^nk . When both the sides of the

equation are

divided by r^n–k and right side is subtracted from the left side, we

obtain an equation, known as characteristic equation of the recurrence relation as

follows:

1 2 k 1 k
r ^k  c r ^k1  c r^k2 … c r  c

 0 .

The solutions of the equation are called as characteristic roots of the recurrence relation.

In this subsection, we shall focus on solving linear homogeneous recurrence relation of degree 2 that is: a_n = c₁a_n–1 + c₂a_n–2.

The characteristic equation of this relation is r² – c₁r – c₂ = 0. This is a quadratic equation and has two roots. Two cases arise.

1. 
   ^{Roots are distinct, say s}1 ^{and s}2^{. Then, it can be shown that}
   

a  usⁿ  vsⁿ is a solution to the recurrence relation, with

n 1 2

a  us  vs and a  us ²  vs ² .

1 1 2 2 1 2

2. 
   
   n
   Roots are equal, say s. Then it can be shown that a_n solution to the
   

recurrence relation is a_n= (u  vn)sⁿ

We shall use above results to solve some problems

^{Example : Solve the recurrence relation bn + 3bn–1 + 2bn–2 = 0, with b}1 ^{= –2 and}

b₂ = 4.

Solution: The characteristic equation to the given recurrence relation is x²

+ 3x + 2 = 0. Roots of this equation are s₁ = – 2 and s₂ = – 1. Hence the solution to the relation is:


.
b_n = u(–1)ⁿ + v(–2)ⁿ b₁ = –2 = –u –2v and b₂ = 4 = u + 4v. Solving these two equations simultaneously, we get, u = 0 and v = 1. Thus, explicit solution to the given recurrence relation is b_n = (–2)ⁿ

Method for solving linear non-homogeneous recurrence relations with constant coefficients:
The method is similar to the solution differential equation by method of undermined co-efficient.

GENERATING FUNCTION:

Let a₀ , a₁ ,...a_n be a sequence, and then the corresponding generating function is given by:

A(x) = a₀ x  a x  ...  a x


1


n

0 1 n

For Example, if 1, 1, 1,…. be a sequence then the corresponding generating function is given by:

A(x) = 1 x  x²  1/(1 x)


From a given sequence we can find the corresponding generating function and vice versa.
Unit II

INTRODUCTION TO RELATIONS AND GRAPH ^THEORY
OBJECTIVES:
After going through this unit, you will be able to know:

• 
  Definition of Relation.
  
• 
  Representation of Relations
  
• 
  Types of Relations
  
• 
  Equivalence of relations
  
• 
  Relations and Partition
  
• 
  Definition and examples of partial order relation
  
• 
  Representation of posets using Hasse diagram
  
• 
  Closure of relations.
  
• 
  Introduction to graphs
  
• 
  Graph terminology
  
• 
  Graph isomorphism
  
• 
  Connectivity
  
• 
  Euler and Hamilton paths
  
• 
  Planar graphs
  
• 
  Graph colouring
  
• 
  Introduction to trees
  

INTRODUCTION :

Relationships between elements of sets occur in many contexts. We deal with many relationships such as student’s name and roll no., teacher and her specialization, a person and a relative (brother – sister, mother – child etc.). In this section, we will discuss mathematical approach to the relation. These have wide applications in Computer science (e.g. relational algebra)

RELATIONS:
Relationship between elements of sets is represented using a mathematical structure called relation. The most intuitive way to describe the relationship is to represent in the form of ordered pair. In this section, we study the basic terminology and diagrammatic representation of relation.

Definition :

Let A and B be two sets. A binary relation from A to B is a subset of A  B.

Note : If A, B and C are three sets, then a subset of ABC is known as ternary relation. Continuing this way a subset of A₁A₂...A_n is known as n – ary relation.

Note: Unless or otherwise specified in this chapter a relation is a binary relation.

Let A and B be two sets. Suppose R is a relation from A to B (i.e. R is a subset of A  B). Then, R is a set of ordered pairs where each first element comes from A and each second element from B. Thus, we denote it with an ordered pair (a, b), where a  A and b  B. We also denote the relationship with a R b, which is read as a related to b. The domain of R is the set of all first elements in the ordered pair and the range of R is the set of all second elements in the ordered pair.
Example 1: Let A = { 1, 2, 3, 4 } and B = { x, y, z }. Let R = {(1, x), (2, x), (3, y), (3, z)}.

Then R is a relation from A to B.

Example 2: Suppose we say that two countries are adjacent if they have some part of their boundaries common. Then, “is adjacent to”, is a relation R on the countries on the earth. Thus, we have, (India, Nepal)  R, but (Japan, Sri Lanka)  R.

Example 3: A familiar relation on the set Z of integers is “m divides n”. Thus, we have, (6, 30)  R, but (5, 18)  R.

Example 4: Let A be any set. Then A  A and  are subsets of A  A and hence they are relations from A to A. These are known as universal relation and empty relation, respectively.

Note : As relation is a set, it follows all the algebraic operations on relations that we have discussed earlier.

Definition : Let R be any relation from a set A to set B. The inverse of R, denoted by R^–1, is the relation from B to A which consists of those ordered pairs, when reversed, belong to R. That is:

R^–1 = {(b, a) : (a, b)  R}
Example 5:

Inverse relation of the relation in example 1 is, R^–1 = {(x,), (x, 2), (y, 3), (z, 3)}.