[PDF] Sample Problems in Discrete Mathematics

P(n) :8kn(k >10;n >10); k2 Then,

Base case:forn= 11,

112<1121112

=)9<11012 =556 = 9 +16

Notice that the base of the induction proof start withn= 11, rather than withn= 0. Such a shift happens

often, and it does not change the principle, since this is nothing more than the matter of notations. One can

dene a propertyQ(m) byQ(m) =P(n11), and considerQform0: Induction step.Suppose, givenn11,Pholds true for all integers upn:Then

P(n) =)n2 =)(n+ 1)21<(n+1)2(n+1)2n1+112 =)(n+ 1)2<(n+1)2(n+1)2n1+112 + 1 =)(n+ 1)2<(n+1)2(n+1)12 2n12 + 1 =)(n+ 1)2<(n+1)2(n+1)12 (sincen >10)

The last inequality isP(n+ 1).

Problem 2For every integern1,nX

i=1pi >2npn=3:

Proof:We prove it by induction onn.

Base.Forn= 1, the left part is 1 and the right part is 2/3: 1>2=3. Inductive step.Suppose the statement is correct for somen1; we prove that it is correct forn+ 1. Thus,

Given:Pn

i=1pi >2npn=3;Prove:Pn+1 i=1pi >2(n+ 1)pn+ 1=3. n+1X i=1pi= (nX i=1pi) +pn+ 1 (1) Using the given inequality, we evaluate the right part of (1) nX i=1pi) +pn+ 12npn=3 +pn+ 1:(2) The following sequence of equivalent inequalities completes the proof:

2npn=3 +pn+ 12(n+ 1)pn+ 1=3 (3)

2npn+ 3pn+ 12(n+ 1)pn+ 1 (4)

2npn(2n1)pn+ 1 (5)

4n2n(2n1)2(n+ 1) (6)

4n3(4n24n+ 1)(n+ 1) = 4n33n+ 1 (7)

0 3n+ 1:(8)

The last inequality holds true for anyn >0.

2

Problem 3For every integern0,

n X i=0i

2=n(n+ 1)(2n+ 1)6

Prove.

Problem 4Prove that every integer greater than 1 is a product of prime numbers.

Proof:We will use strong induction. Base Case: 2 is a product of prime numbers, since 2 itself is a prime.

Inductive Step: Letnbe an arbitrary integer greater than 1. The Inductive Hypothesis is that for all integers

ksuch that 1< k < n, we have thatkcan be written as a product of primes. Then, eithernis a prime itself (in which case it is a product of prime numbers), orncan be written asn=n1n2with bothn1and n

2being integers greater than 1 and less thann. Thus, the Inductive Hypothesis applies to bothn1andn2,

and so each can be written as a product of prime numbers. Thus,ncan be written as a product of prime numbers as well. Problem 5What is wrong with the following classic \proof" that all horses have the same color? LetP(n)be the proposition that for any set ofnhorses, all horses in this set have the same color.

Base Case:P(1)is clearly true.

Inductive Step: The Inductive Hypothesis is thatP(n)holds; we will show that this impliesP(n+1). Let Abe an arbitrary set ofn+ 1horses. Consider the rstnhorses inA, and the lastnhorses inA. Both of

these are sets ofnhorses, and so the inductive hypothesis holds for them, telling us that both the rstnand

the lastnhorses ofAhave the same color. Since the set of the rstnand the lastnhorses overlap, then alln+ 1horses ofAmust have the same color, thus provingP(n+ 1).

Problem 6Prove by induction that

F

1+F3+:::+F2n1=F2n;

whereFidenotes theithFibonacci number.

2 Order of Functions

See Chapter 2 of the textbook, and the exercises therein.

Problem 7Compare the following pairs of functions in terms of order of growth. In each case, determine

iff(n) =O(g(n));f(n) = (g(n));f(n) = (g(n)). Prove your answers. f(n)g(n)(1)(lgn)an b(herea;b >0) (2)2nlog2n10n! (3)pn(log 2n)5 (4) n2log

2n(nlog2n)4

(5)log2nlog

2(66n)

(6)1000(log2n)0:999(log

2n)1:001

(7)n2n(log2n)15

3 Graph Theory

See also Chapter 3 of the textbook and the exercises therein. 3 Problem 8Here is an example of Structural Induction in trees. Consider a rooted treeT= (V;E), where

nodes are labeled with positive integers: each nodev2Vis labeled with an integerav. Assume thatTobeys

theheap property,i.e., ifwis a child ofv, thenaw< av. Prove that the root noderhas the largest label of

all nodes in the tree. Proof:LetTvbe the subtree ofTrooted atv. We will prove the propositionP(v) which states thatvhas

the largest label inTv. Base Case: Ifvis a leaf, thenTvconsists of a single nodev, and soP(v) is trivially

true. Inductive Step: Assume thatP(w) is true for all childrenwofv. By the heap property,aw< av, and

by the inductive hypothesis,awis the largest label inTw. Therefore,avis the largest label inTv, as desired.

We have now shown thatP(v) holds for all nodesv2V. Therefore,P(r) holds, and sorhas the largest label of all nodes in the tree.

Problem 9

By analyzing the algorithm for Breadth-First-Search (BFS), show that in the case of a connected, undirected

graphG, its every edge is either a tree edge (belongs to the BFS tree), or a cross edge (connects two vertices,

neither is a descendant of the other in the BFS tree.) Problem 10Find an example of a directed graph and a DFS-forest such that vertexvis not a descendant ofu, but graphGhas a path fromutovanddis[u]< dis[v](heredis[u]is the distance from the root).

Problem 11

Describe an algorithm (in words, not a code), which for a given connected undirected graphG, directs its

edges in such a way that the following two conditions are satised:

1. the resulting directed graph contains a rooted tree all of whose edges are directed away from the root;

2. every edge not in the tree above forms a directed cycle with some edges of the tree.

What is the complexity of your algorithm? Explain. Problem 12Show how to tell if graph is bipartite (in linear time).

4 Additional Problems in Discrete Math and Logic

Problem 13How many eight digit numbers are there that contain a 5 and a 6? Explain. Problem 14How many nine digit numbers are there that contain exactly two 5's?

Problem 15What are the coecients of the terms1x

,1x

2in the expansion of(x+1x

)n, where(n >2)?

Explain.

Problem 16Prove that for everyn1and everym1, the number of functions fromf1;2;:::;ngto f1;2;:::;mgismn. Problem 17Prove the following identities.IdempotencyA[A=A;A\A=A

CommutativityA[B=B[A;A\B=B\A

Distributivity(A[B)\C= (A\C)[(B\C)(A\B)[C= (A[C)\(B[C) DeMorgan's LawsU(B[C) = (UB)\(UC)U(B\C) = (UB)[(UC)4

Problem 18(Converse) Consider the following two statements: \100 percent of convicted felons consumed

bread during their childhood." and "People who consume bread as a child are likely to become felons." Does

the rst statement logically imply the second?

Problem 19(Contrapositive) Consider the following two statements: \100 percent of convicted felons con-

sumed bread during their childhood." and "People who do not consume bread as a child do not become felons."

Does the rst statement logically imply the second? 5quotesdbs_dbs17.pdfusesText_23