Category: discrete Mathematics

Discrete Mathematics Tutorial PDF Version Quick Guide Resources Job Search Discussion Discrete Mathematics is a branch of mathematics involving discrete elements that uses algebra and arithmetic. It is increasingly being applied in the practical fields of mathematics and computer science. It is a very good tool for improving reasoning and problem-solving capabilities. This tutorial explains the fundamental concepts of Sets, Relations and Functions, Mathematical Logic, Group theory, Counting Theory, Probability, Mathematical Induction and Recurrence Relations, Graph Theory, Trees and Boolean Algebra. Audience This tutorial has been prepared for students pursuing a degree in any field of computer science and mathematics. It endeavors to help students grasp the essential concepts of discrete mathematics. Prerequisites This tutorial has an ample amount of both theory and mathematics. The readers are expected to have a reasonably good understanding of elementary algebra and arithmetic. Print Page Previous Next Advertisements ”;

Operators & Postulates ”; Previous Next Group Theory is a branch of mathematics and abstract algebra that defines an algebraic structure named as group. Generally, a group comprises of a set of elements and an operation over any two elements on that set to form a third element also in that set. In 1854, Arthur Cayley, the British Mathematician, gave the modern definition of group for the first time − “A set of symbols all of them different, and such that the product of any two of them (no matter in what order), or the product of any one of them into itself, belongs to the set, is said to be a group. These symbols are not in general convertible [commutative], but are associative.” In this chapter, we will know about operators and postulates that form the basics of set theory, group theory and Boolean algebra. Any set of elements in a mathematical system may be defined with a set of operators and a number of postulates. A binary operator defined on a set of elements is a rule that assigns to each pair of elements a unique element from that set. For example, given the set $ A = lbrace 1, 2, 3, 4, 5 rbrace $, we can say $otimes$ is a binary operator for the operation $c = a otimes b$, if it specifies a rule for finding c for the pair of $(a,b)$, such that $a,b,c in A$. The postulates of a mathematical system form the basic assumptions from which rules can be deduced. The postulates are − Closure A set is closed with respect to a binary operator if for every pair of elements in the set, the operator finds a unique element from that set. Example Let $A = lbrace 0, 1, 2, 3, 4, 5, dots rbrace$ This set is closed under binary operator into $(ast)$, because for the operation $c = a ast b$, for any $a, b in A$, the product $c in A$. The set is not closed under binary operator divide $(div)$, because, for the operation $c = a div b$, for any $a, b in A$, the product c may not be in the set A. If $a = 7, b = 2$, then $c = 3.5$. Here $a,b in A$ but $c notin A$. Associative Laws A binary operator $otimes$ on a set A is associative when it holds the following property − $(x otimes y) otimes z = x otimes (y otimes z)$, where $x, y, z in A $ Example Let $A = lbrace 1, 2, 3, 4 rbrace$ The operator plus $( + )$ is associative because for any three elements, $x,y,z in A$, the property $(x + y) + z = x + ( y + z )$ holds. The operator minus $( – )$ is not associative since $$( x – y ) – z ne x – ( y – z )$$ Commutative Laws A binary operator $otimes$ on a set A is commutative when it holds the following property − $x otimes y = y otimes x$, where $x, y in A$ Example Let $A = lbrace 1, 2, 3, 4 rbrace$ The operator plus $( + )$ is commutative because for any two elements, $x,y in A$, the property $x + y = y + x$ holds. The operator minus $( – )$ is not associative since $$x – y ne y – x$$ Distributive Laws Two binary operators $otimes$ and $circledast$ on a set A, are distributive over operator $circledast$ when the following property holds − $x otimes (y circledast z) = (x otimes y) circledast (x otimes z)$, where $x, y, z in A $ Example Let $A = lbrace 1, 2, 3, 4 rbrace$ The operators into $( * )$ and plus $( + )$ are distributive over operator + because for any three elements, $x,y,z in A$, the property $x * ( y + z ) = ( x * y ) + ( x * z )$ holds. However, these operators are not distributive over $*$ since $$x + ( y * z ) ne ( x + y ) * ( x + z )$$ Identity Element A set A has an identity element with respect to a binary operation $otimes$ on A, if there exists an element $e in A$, such that the following property holds − $e otimes x = x otimes e$, where $x in A$ Example Let $Z = lbrace 0, 1, 2, 3, 4, 5, dots rbrace$ The element 1 is an identity element with respect to operation $*$ since for any element $x in Z$, $$1 * x = x * 1$$ On the other hand, there is no identity element for the operation minus $( – )$ Inverse If a set A has an identity element $e$ with respect to a binary operator $otimes $, it is said to have an inverse whenever for every element $x in A$, there exists another element $y in A$, such that the following property holds − $$x otimes y = e$$ Example Let $A = lbrace dots -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, dots rbrace$ Given the operation plus $( + )$ and $e = 0$, the inverse of any element x is $(-x)$ since $x + (x) = 0$ De Morgan”s Law De Morgan’s Laws gives a pair of transformations between union and intersection of two (or more) sets in terms of their complements. The laws are − $$(A cup B)” = A” cap B”$$ $$(A cap B)” = A” cup B”$$ Example Let $A = lbrace 1, 2, 3, 4 rbrace ,B = lbrace 1, 3, 5, 7 rbrace$, and Universal set $U = lbrace 1, 2, 3, dots, 9, 10 rbrace$ $A” = lbrace 5, 6, 7, 8, 9, 10 rbrace$ $B” = lbrace 2, 4, 6, 8, 9, 10 rbrace$ $A cup B = lbrace 1, 2,

Discrete Mathematics – Recurrence Relation ”; Previous Next In this chapter, we will discuss how recursive techniques can derive sequences and be used for solving counting problems. The procedure for finding the terms of a sequence in a recursive manner is called recurrence relation. We study the theory of linear recurrence relations and their solutions. Finally, we introduce generating functions for solving recurrence relations. Definition A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms (Expressing $F_n$ as some combination of $F_i$ with $i < n$). Example − Fibonacci series − $F_n = F_{n-1} + F_{n-2}$, Tower of Hanoi − $F_n = 2F_{n-1} + 1$ Linear Recurrence Relations A linear recurrence equation of degree k or order k is a recurrence equation which is in the format $x_n= A_1 x_{n-1}+ A_2 x_{n-1}+ A_3 x_{n-1}+ dots A_k x_{n-k} $($A_n$ is a constant and $A_k neq 0$) on a sequence of numbers as a first-degree polynomial. These are some examples of linear recurrence equations − Recurrence relations Initial values Solutions Fn = Fn-1 + Fn-2 a1 = a2 = 1 Fibonacci number Fn = Fn-1 + Fn-2 a1 = 1, a2 = 3 Lucas Number Fn = Fn-2 + Fn-3 a1 = a2 = a3 = 1 Padovan sequence Fn = 2Fn-1 + Fn-2 a1 = 0, a2 = 1 Pell number How to solve linear recurrence relation Suppose, a two ordered linear recurrence relation is − $F_n = AF_{n-1} +BF_{n-2}$ where A and B are real numbers. The characteristic equation for the above recurrence relation is − $$x^2 – Ax – B = 0$$ Three cases may occur while finding the roots − Case 1 − If this equation factors as $(x- x_1)(x- x_1) = 0$ and it produces two distinct real roots $x_1$ and $x_2$, then $F_n = ax_1^n+ bx_2^n$ is the solution. [Here, a and b are constants] Case 2 − If this equation factors as $(x- x_1)^2 = 0$ and it produces single real root $x_1$, then $F_n = a x_1^n+ bn x_1^n$ is the solution. Case 3 − If the equation produces two distinct complex roots, $x_1$ and $x_2$ in polar form $x_1 = r angle theta$ and $x_2 = r angle(- theta)$, then $F_n = r^n (a cos(ntheta)+ b sin(ntheta))$ is the solution. Problem 1 Solve the recurrence relation $F_n = 5F_{n-1} – 6F_{n-2}$ where $F_0 = 1$ and $F_1 = 4$ Solution The characteristic equation of the recurrence relation is − $$x^2 – 5x + 6 = 0,$$ So, $(x – 3) (x – 2) = 0$ Hence, the roots are − $x_1 = 3$ and $x_2 = 2$ The roots are real and distinct. So, this is in the form of case 1 Hence, the solution is − $$F_n = ax_1^n + bx_2^n$$ Here, $F_n = a3^n + b2^n (As x_1 = 3 and x_2 = 2)$ Therefore, $1 = F_0 = a3^0 + b2^0 = a+b$ $4 = F_1 = a3^1 + b2^1 = 3a+2b$ Solving these two equations, we get $ a = 2$ and $b = -1$ Hence, the final solution is − $$F_n = 2.3^n + (-1) . 2^n = 2.3^n – 2^n $$ Problem 2 Solve the recurrence relation − $F_n = 10F_{n-1} – 25F_{n-2}$ where $F_0 = 3$ and $F_1 = 17$ Solution The characteristic equation of the recurrence relation is − $$ x^2 – 10x -25 = 0$$ So $(x – 5)^2 = 0$ Hence, there is single real root $x_1 = 5$ As there is single real valued root, this is in the form of case 2 Hence, the solution is − $F_n = ax_1^n + bnx_1^n$ $3 = F_0 = a.5^0 + (b)(0.5)^0 = a$ $17 = F_1 = a.5^1 + b.1.5^1 = 5a+5b$ Solving these two equations, we get $a = 3$ and $b = 2/5$ Hence, the final solution is − $F_n = 3.5^n +( 2/5) .n.2^n $ Problem 3 Solve the recurrence relation $F_n = 2F_{n-1} – 2F_{n-2}$ where $F_0 = 1$ and $F_1 = 3$ Solution The characteristic equation of the recurrence relation is − $$x^2 -2x -2 = 0$$ Hence, the roots are − $x_1 = 1 + i$ and $x_2 = 1 – i$ In polar form, $x_1 = r angle theta$ and $x_2 = r angle(- theta),$ where $r = sqrt 2$ and $theta = frac{pi}{4}$ The roots are imaginary. So, this is in the form of case 3. Hence, the solution is − $F_n = (sqrt 2 )^n (a cos(n .sqcap /4) + b sin(n .sqcap /4))$ $1 = F_0 = (sqrt 2 )^0 (a cos(0 .sqcap /4) + b sin(0 .sqcap /4) ) = a$ $3 = F_1 = (sqrt 2 )^1 (a cos(1 .sqcap /4) + b sin(1 . sqcap /4) ) = sqrt 2 ( a/ sqrt 2 + b/ sqrt 2)$ Solving these two equations we get $a = 1$ and $b = 2$ Hence, the final solution is − $F_n = (sqrt 2 )^n (cos(n .pi /4 ) + 2 sin(n .pi /4 ))$ Non-Homogeneous Recurrence Relation and Particular Solutions A recurrence relation is called non-homogeneous if it is in the form $F_n = AF_{n-1} + BF_{n-2} + f(n)$ where $f(n) ne 0$ Its associated homogeneous recurrence relation is $F_n = AF_{n–1} + BF_{n-2}$ The solution $(a_n)$ of a non-homogeneous recurrence relation has two parts. First part is the solution $(a_h)$ of the associated homogeneous recurrence relation and the second part is the particular solution $(a_t)$. $$a_n=a_h+a_t$$ Solution to the first part is done using the procedures discussed in the previous section. To find the particular solution, we find an appropriate trial solution. Let $f(n) = cx^n$ ; let $x^2 = Ax + B$ be the characteristic equation of the associated homogeneous recurrence relation and let $x_1$ and $x_2$ be its roots. If $x ne x_1$ and $x ne x_2$, then $a_t = Ax^n$ If $x = x_1$, $x ne x_2$, then $a_t = Anx^n$ If