MCA 3rd sem /MCS-033/Solved Assignment/ Advanced Discrete Mathematics /2017-2018 New

A.1.

A recursive definition of a sequence specifies

·        1) Initial conditions

·          2) Recurrence relation

Example:

a0=0 and a1=3   à      Initial conditions

an = 2an-1 - an-2         à      Recurrence relation

an = 3n                à      Solution

Linear recurrence: Each term of a sequence is a linear function of earlier terms in the sequence. For example:

a0 = 1     a1 = 6      a2 = 10   

an = an-1 + 2an-2 + 3an-3

a3 = a0 + 2a1 + 3a2

= 1 + 2(6) + 3(10) = 43

Linear recurrences

 1. Linear homogeneous recurrences

 2. Linear non-homogeneous recurrences

A linear homogenous recurrence relation of degree k with constant coefficients is a recurrence relation of the form a_n = c₁a_n-1 + c₂a_n-2 + … + c_ka_n-k, where c1, c2, …, ck are real numbers, and ck0.

 a_n is expressed in terms of the previous k terms of the sequence, so its degree is k. This recurrence includes k initial conditions. a₀ = C₀ a₁ = C₁ … a_k = C_k

A linear non-homogenous recurrence relation with constant coefficients is a recurrence relation of the form a_n = c₁a_n-1 + c₂a_n-2 + … + c_ka_n-k+ f(n), where c1, c2, …, ck are real numbers, and f(n) is a function depending only on n. The recurrence relation a_n = c₁a_n-1 + c₂a_n-2 + … + c_ka_n-k, is called the associated homogeneous recurrence relation. This recurrence includes k initial conditions. a₀ = C₀ a₁ = C₁ … a_k = C_k

A.2.

·         Homogeneous--- Order 1 and Degree1

·         Homogeneous---- Order 1 and  Degree 0(No Degree)

·         Non-Homogeneous ----Order 2 and Degree 2

·         Non-Homogeneous---- Order 1 and Degree1

·         Homogeneous---  No order and 1 Degree

A.3.

(i) a_n = a_n-1 +7

Solution:--  Here a₁ = 3 is given

When n = 2,

A₂ = a_2-1 +7

  A₂ = a₁+7

A₂ = 10

(ii)  a_n = 2ⁿ a_n-1 , n>0

Solution:--  Here a₀ = 1 is given

When n = 1,

A₁ = 2ⁿ a_1-1

  A₂ =2²  a₀

A₂ = 4*1

A₂ = 4

(iii)  a_n = 6  a_n-1 - 8  a_n-2  , n>0

Solution:--  Here a₁ = 0 and a₀ = 1 is given

When n = 2,

A₂ = 6 a_2-1 - 8  a_2-2  

  A₂ = 6 a₁ - 8  a₀

A₂ = 6 *0 - 8  *1

A₂ = -8

 A.4.

A.5.

According to formula, 
An = P( 1 +r/100)ⁿ
Where A is total amount after n years , r is the rate. P is the amount initially

An =10, 000( 1 + 10/100)ⁿ
=10,000( 1 +0.1)ⁿ
=10,000(1.1)ⁿ

An =10,000(1.1)ⁿ

now, put n = 1 
A1 =10, 000(1.1), 
put n =2 ,
A2 =10,000(1.1)²

in the same way , 
A3 =10, 00(1.1)³ 

you can see that 
A2/A1 = A3/A2 

so, {An} is in Geometric progression .

now, 
amount payable after 5years 

A5 =10,000(1.1)^5 
=16, 105.1 Rs 

A.6.

A.7.

Finding Hamiltonian paths or circuit is a problem similar to the determination of an Eulerian path or an Eulerian circuits is to determine a path or a circuit that passes through each vertex in a graph once and only once. Sir William Hamiltonian invented the game “All around the world” in which the player is asked to determine a route along the dodecahedron that will pass through each angular point once and only once.

Hamilton’s A Voyage Round the World Puzzle In 1857, Irish mathematician Sir William Rowan Hamilton, invented a puzzle A Voyage round the world. It consisted of a wodden dodecahedron, with a peg at each vertex of the dodecahedron, and string. The twenty vertices of the dodecahedron were labeled with different cities in the world.

The object of the puzzle was to start at a city and travel along the edges of the dodecahedron, visiting each of the other 19 cities exactly once, and end up at the first city.

The solution of Hamilton’s puzzle is shown below with dark lines.

Hamilton’s paths: A path in the graph is said to be Hamiltonian path if it traverses each of the vertices once and only once. Path in fig(3.6.20) with dark lines is an Hamiltonian path.

A.8.

(i) Dirac’s

T                 Theorem 1 (Dirac's Theorem): If G=(V(G),E(G)) is connected graph on n-vertices  so that for        every x,y∈V(G), where x≠y, and deg(x)+deg(y)≥n for all x,y∈V(G), then G is a Hamiltonian graph.

Let's verify Dirac's theorem by testing to see if the following graph is Hamiltonian:

A.8.(ii)

Ore's Theorem

Ore's theorem is a vast improvement to Dirac's theorem:

Theorem 2 (Ore's Theorem): If G=(V(G),E(G)) is connected graph on n-vertices where n≥3] so that for [[x,y∈V(G), where x≠y, and deg(x)+deg(y)≥n for each pair of non-adjacent vertices x and y then G is a Hamiltonian graph.

Recall that two vertices are said to be adjacent if they are connected by an edge. Two vertices x and y are said to be adjacent if {x,y}∈E(G). Thus, non-adjacent vertices x and y are vertices such that {x,y}∉E(G).

Let's see if this theorem is accurate by testing the graph from earlier, let's call it G. This graph is on 6 vertices and is clearly Hamiltonian. Let's verify this with Ore's theorem. The only pair of non-adjacent vertices are c and f, since {c,f}∉E(G). For G to be Hamiltonian, it must follow that:

(1)

deg(c)+deg(f)≥64+4≥68≥6

Thus according to Ore's theorem, the graph G is Hamiltonian.

A.8.(iii)

A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once (Skiena 1990, p. 196). A graph possessing a Hamiltonian cycle is said to be a Hamiltonian graph. By convention, the singleton graph  is considered to be Hamiltonian even though it does not posses a Hamiltonian cycle, while the connected graph on two nodes  is not.

SO , both the Graph is Hamilton Circuit because these grapghs contains a cycle containing all the Vertices.

A.9.

A.10

The argument given is the total number of subsets for a set of nnelements. Combinations, on the other hand, count the number of subsets of a given size.

For example, consider the set {1, 2, 3}{1, 2, 3}. There are 23=823=8 total subsets (of all sizes), which are

{∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}{∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

The subsets are symmetric in inclusion/exclusion (and this is why you only have two boxes: the first box represents inclusion and the second exclusion), for example the set {2}{2} has a complement, namely {1, 3}{1, 3} where the first set is obtained by keeping 22 while the second set is obtained by throwing away 22.

Combinations count the subsets of a particular size (nn choose rr counts the number of rr-element subsets of an nn-element set). In our running example consider how many subsets of size 22 there are:

{{1, 2}, {1, 3}, {2, 3}}{{1, 2}, {1, 3}, {2, 3}}

for a total of (32)(32). The symmetry noted from before is also reflected in the fact that the binomial coefficients are symmetric

(nr)=(nn−r)(nr)=(nn−r)

which represents the fact that for every rr-element subset that you keep, there's corresponding n−rn−r-element subset that you've thrown away.

Of course the two concepts are intimately related. The total number of subsets is the sum of the number of subsets of every size.

2n=∑ r=0n (nr)2n=∑r=0n(nr)

This is in essense what the familiar binomial theorem states.

A.11(i)

(ii)

(iii)