Notes on Discrete Mathematics

Department of Computer Science

Professor Goldberg
Textbooks: Introduction to the Theory of Computation
by Michael Sipser
Elements of the Theory of Computation
by H. Lewis and C. Papadimitriou
Discrete Mathematics with Algorithms
by M. Albertson and J. Hutchinson

These notes contain the material from Discrete Mathematics that you need
to know in order to take the course in Computability and Complexity. Try
to solve all problems. Most of them are simple; their purpose is just to
refresh you memory. If you cannot solve many of them, I would strongly
recommend that you take a course in Discrete Mathematics.

1 Logic

Problem 1 Which of the following statements are true?

Dogs have wings only if cats have wings.

Birds have wings only if cats have wings.
If dogs have wings, then birds have wings.
Snakes have legs iff cats have wings.
If frogs have hair or mice have eyes,
then sharks do not have teeth.
If frogs have hair and mice have eyes,
then sharks do not have teeth.

1
Problem 2 Fill in the truth tables:

P ∧ Q P is true P is false P ∨ Q P is true P is false

Q is true Q is true
Q is false Q is false

If Q then P P is true P is false true false

Q is true P
Q is false ¬P

Problem 3 Write the truth table for (p ∧ q) ∨ (q ∨ p).

Problem 4 Assuming that p and r are false, and that q and s are true, find
the truth value of the following propositions:

1. p → q;
2. p → q;
3. p → q;
4. (p → q) ∧ (q → r);
5. (p → q) → r;
6. (p → (q → r).

2 Set theory

Definition 1 A set A = {a0 , a1, . . .}; empty set: ∅; A is a subset of B:

A ⊆ B; x is an element of A: x ∈ A; 2A = {the set of all subsets of A};
Cartesian product of two sets: A × B = {(a, b) : a ∈ A&b ∈ B}.

2
Problem 5 Which of the following statements are true?

∅⊆∅
∅∈∅
∅ ⊆ {∅}
∅ ∈ {∅}
{a, b} ⊆ {a, b, {a, b}}
{a, b} ∈ {a, b, {a, b}}
{a, b} ∈ 2{a,b,{a,b}}
{a, b} ⊆ 2{a,b,{a,b}}

Problem 6 Prove the following identities.

Idempotency A ∪ A = A; A ∩ A = A
Commutativity A ∪ B = B ∪ A; A ∩ B = B ∩ A
Associativity (A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)
Distributivity (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
(A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C)
DeMorgan’s Laws U − (B ∪ C) = (U − B) ∩ (U − C)
U − (B ∩ C) = (U − B) ∪ (U − C)

Problem 7 If X = {1, 2, 3} and Y = {a, b}, then what are X × Y ; Y ×

X; X × X; 2X ?

Definition 2
A partition of a nonempty set A is a subset Π of 2A such that ∅ is not an
element of Π and each element of A is in one and only one set in Π.

Problem 8 Rephrase the definition of a partition in a simpler language.

Enumerate all partitions of Y × Y for Y = {1, 2}.

3
Problem 9
Let S = {1, 2, 3, 4, 5}.
(a) What partition of S has the most (the fewest) members?
(b) List all partitions of S with exactly two (three) members.

Definition 3
Binary relation R is a subset of A × B.
Inverse R−1 of R; if R is a binary relation between A and B then
R−1 ⊆ B × A; (b, a) ∈ R−1 iff (a, b) ∈ R.
Composition QR Q ⊆ A × C and R ⊆ C × B is defined by
(a, b) ∈ QR iff (a, c) ∈ Q and (c, b) ∈ R for some c ∈ C.

Problem 10 Define an n-ary relation.

Definition 4 A binary relation R ⊆ A × A is called

reflexive if (a, a) ∈ R for all a ∈ A.

symmetric if (a, b) ∈ R whenever (b, a) ∈ R;
antisymmetric if (a, b) ∈ R and (b, a) ∈ R, then a = b
transitive if (a, b) and (b, c) imply (a, c);
equivalence if it is reflexive, symmetric, and transitive.
partial order if it is reflexive, antisymmetric, and transitive.
total order if it is a partial order and ∀a, b, either (a, b) ∈ R or (b, a) ∈ R.

4
Definition 5
Function from a set A into a set B is a binary relation R on A and B such
that for each element a ∈ A, ∃ exactly one element b ∈ B with (a, b) ∈ R.
f : A → B; A is the domain of f ; f (A) ⊆ B is the range of f .
A function is one-to-one if for any two distinct elements a and b, f (a) 6= f (b).

onto if each element of B is the image of an element of A under f .

bijection between A and B, if it is one-to-one and onto B.

Definition 6
Let D be a set, n ≥ 0, and R ⊆ Dn+1 be an (n + 1)-ary relation on D. Then
B ⊆ D is said to be closed under R if

∀b1 , . . . , bn ∈ B, (b1, . . . , bn, bn+1) ∈ R implies bn+1 ∈ B.

Let D be a set, n ≥ 0, and f : Dn → D. A subset B ⊆ D is closed under

f if f (b1, . . . , bn) ∈ B for all b1 , . . . , bn ∈ B.

Problem 11 Fix |D| = 5. Construct an example of a relation R ⊆ D3 and

a subset B ⊂ D which is closed under R.

Problem 12
Is a set closed under a function f also closed under an appropriately defined
relation R? How to define R?

Problem 13
Given a set A ⊆ D and a relation R on D, is there a subset B ⊆ D which
contains A and is closed under R?

Problem 14

5
Given a set A ⊆ D and a relation R on D, is there a subset B ⊆ D which
(1) contains A; (2) closed under R; (3) is minimal in some natural sense?

Theorem 1
Let R be a relation on D and let A ⊆ D. Then there is a set B ⊆ D such
that

• A ⊆ B;
• B is closed under R;
• for any C ⊆ D satisfying the previous two conditions,
B ⊆ C.

Definition 7
The set B described in the previous theorem is called the closure of A under
relations R1 , . . . , Rn.

Reflexive, Transitive Closure of a Binary Relation

Definition 8
Let A be a finite set, D = A × A, and R ⊆ D. Let also Q and Q′ be a 3-ary
and unary relation on D, respectively, given by Q = {((a, b), (b, c), (a, c)) :
a, b, c ∈ A} and Q′ = {(a, a) : a ∈ A}. Then the closure of R under Q and Q′
is called the reflexive, transitive closure of R and is denoted R∗.

Theorem 2
The reflexive, transitive closure R∗ of a binary relation R is equal to

R ∪ {(a, b) : ∃ a chain in R from a to b}.

Problem 15
Prove theorem 2.17.

6
3 Principle of Mathematical Induction

Let A be a set of nonnegative integers such that

1. 0 ∈ A;
2. ∀n ∈ N , if {0, . . . , n} ⊆ A, then n + 1 ∈ A.

Then A = N .

Applying Mathematical Induction

The task: Given property P = P (n), prove that it holds for
all integers n ≥ 0.

Basis: show that P (0) is correct;

Induction assume that for some fixed, but arbitrary integer n ≥ 0,

hypothesis: P holds for all integers 0, 1, . . . , n

Induction step: prove that the induction hypothesis, P (n), implies that
P is true of n + 1: P (n) =⇒ P (n + 1)

Conclusion: using the principle of Mathematical Induction

conclude that P (n) is true for arbitrary n ≥ 0.

Problem 16 Prove that for all n > 10

n2 − n
n−2< .
12
Proof: Define property P (n) by
k2 − k
P (n) : ∀k ≤ n (k > 10; n > 10), k − 2 < .
12
7
Then,
Basis: for n = 11,
112 − 11 110 55 1
11 − 2 < =⇒ 9 < = =9+ .
12 12 6 6
Notice that the base of the induction proof start with n = 11, rather than
with n = 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 define a
property Q(m) by Q(m) = P (n − 11), and consider Q for m ≥ 0.
Induction step. Suppose, given n ≥ 11, P holds true for all integers up n.
Then 2
P (n) =⇒ n − 2 < n 12−n
2
=⇒ (n + 1) − 2 − 1 < (n+1) −(n+1)−2n−1+1
12
(n+1)2 −(n+1)
=⇒ (n + 1) − 2 < 12 − 2n12 + 1
(n+1)2 −(n+1)
=⇒ (n + 1) − 2 < 12 (since n > 10)

The last inequality is P (n + 1).

Problem 17 (Ramsey Theorem) Let G be a graph. A clique (resp. in-

dependent set) in G is a subgraph in which any two vertices are adjacent
(respectively, no two are adjacent). Denote R(p, q) the smallest integer N
such that every graph with N vertices either contains a clique of size p, or
an independent set of size q. Prove that
R(p, q) ≤ R(p − 1, q) + R(p, q − 1).
 
2n
Then prove that every graph with n vertices either contains a clique of size
n, or an independent set of size n.

Problem 18 Prove that for all n ≥ 0

1 1 1
1+ + + . . . + n ≤ 1 + n.
2 3 2

Problem 19 A set with an even number of elements is called even. Guess

a formula for the number of even subsets of a set with n elements and prove
the formula by induction.

8
4 Pigeonhole principle

1st form: If n pigeons fly into k pigeonholes and k < n, then some pigeon-
hole contains at least two pigeons.
2nd form: If A and B are nonempty finite sets and |A| > |B|, then for any
function f : A → B, ∃a, b ∈ A, such that f (a) = f (b).
3rd form: Let f be a function from a finite set A to a finite set B, let
|A| = n, |B| = m, and k = ⌈n/m⌉. If k ≥ 1, then there are at least k
values a1 , . . . , ak such that f (a1) = . . . = f (ak ).

Problem 20 Prove that every sequence of n2 + 1 distinct numbers has either

an increasing subsequence of length n+1 or a decreasing subsequence of length
n + 1.

Proof. Consider an arbitrary sequence S = {ai } (i ∈ [1, n2 + 1]) of distinct

numbers and define ti to be the length of the longest increasing subsequence
starting at ai .
If no monotone increasing subsequence S of length n + 1 exists, then
∀i = 1, . . . , n2 + 1, ti ≤ n.
To use the Pigeonhole Principle, we now define function F : [1, n2 +1] → [1, n]
by
F (i) = ti (i = 1, 2, . . . , n2 + 1).

Since the domain A of F is of size n2 + 1 and the range B is of size n, by the

Pigeonhole Principle (3rd form) there are at least ⌈n2 + 1/n⌉ = n + 1 indices
i1 , i2, . . . , in+1 for which F takes the same value. Let
F (i1) = F (i2) = . . . F (in+1) = L.

Claim: for every j = i1, i2, . . . , in+1, aij > aij+1 .

Indeed, suppose aij < aij+1 for some j ∈ {1, 2, . . . , n + 1}. Then every mono-
tone increasing subsequence R starting with aij+1 can be included into a
longer monotone increasing subsequence starting with aij , by simply mak-
ing aij the first member and appending R to it. If R is the longest monotone

9
increasing subsequence starting at ij+1 , its length is L, which yields a length
L + 1 monotone increasing subsequence starting at aij . This contradicts the
conclusion from the Pigeonhole Principle, and thus, proves the claim.
Finally, we see that
ai1 > ai1 > . . . > an+1 ,
which proves the theore.

Problem 21 Prove that any subset A of a set {1, 2, 3, . . . , 2n} which has at
least n+1 elements, contains two numbers such that one of them is a multiple
of the other.

Proof. Define odd(x) to be the largest odd divisor of x. let R be an equiva-

lence defined by
R = {(a, b) : odd(a) = odd(b).}
There are n classes of R in [1, . . . , 2n] and there are n + 1 numbers. By
pigeonhole principle, two of the numbers are in the same class; this implies
that one of them is a multiple of the other.

5 Strings and languages

Terminology:
alphabet Σ: a finite set of symbols; binary alphabet: {0,1};
string over Σ:a finite sequence of symbols from Σ;
empty string e: ;
Σ∗: the set of all strings over an alphabet Σ
length of a string: the number of symbols in the string;
occurrences: COMMITTEE;
position w(i): ranges from 1 to the length of the string;
substring: COMMITTEE —— MIT;
suffix (prefix): COMMITTEE —— TEE (COM);

10
Operations on strings:

Concatenation: MUSH ◦ ROOM → MUSHROOM;

concatenation is associative: (uv)w = u(vw).

Reversal: MUSHROOMR = MOORHSUM;

Statement: For any two strings u and v, (uv)R = v R uR .

Operations on languages:

Complement A = Σ∗ − A;

Union: L ∪ M;

Concatenation: LM = {w : w = uv; u ∈ L, v ∈ M};

Lk = LL . . . L;

Closure (Kleene star) L∗

L∗ = {e} ∪ L ∪ L2 ∪ . . .;

L+ = L ∪ L2 ∪ . . ..

Problem 22 What is ∅∗ ?

Problem 23 What is (L∗)∗?

Problem 24 Is it true that L ⊆ M implies L∗ ⊆ M ∗ ?

Problem 25 Is it true that L ⊆ M implies L+ ⊆ M + ?

Problem 26 Prove that (wR )R = w

Problem 27 Prove that if v is a substring of w, then v R is a substring of

wR .

11
Problem 28 Prove that (wR )R = w

Problem 29 Under what circumstances is L+ = L∗ − {e}?

12
Problem 30 Prove that {a, b}∗ = {a}∗ {{b}{a}∗}∗.

Proof. The inclusion

{a, b}∗ ⊇ {a∗ba∗ }∗ (A)
is obvious since the left part is the set of all strings in a and b.
The non-trivial part of our task is to prove that
{a, b}∗ ⊆ a∗ {ba∗ }∗. (B)

The left part of B consists of all strings in the alphabet {a, b}; every such a
string can be written as ap0 bq0 ap1 bq1 . . . apn−1 bqn−1 , for n ≥ 0 and non-negative
integers p0 , q0, p1, q1, . . ..
The right part of B can be re-written as follows:
a∗ {ba∗ }∗ == {e ∪ a ∪ a2 . . .}{e ∪ L ∪ L2 . . .}∗ = ∪as Lt ,
where s, t ≥ 0 are integers and L = ba∗ = b ∪ ba ∪ ba2 ∪ . . .
Thus, to prove B, we need to find, for every p0 , q0, p1, q1, . . ., integers s and t
such that as Lt contains

ap0 bq0 ap1 bq1 . . . apn−1 bqn−1 .

Claim: s = p0; and t = q0 + q1 + . . . + qn−1 are such integers.

ap0 L(q0 +q1 +...+qn−1)

= ap0 (b ∪ ba ∪ ba2 . . .) . . . (b ∪ ba ∪ ba2 . . .)(b ∪ ba ∪ ba2 . . .)
| {z }
q0 −1

(b ∪ ba ∪ ba2 . . .) . . . (b ∪ ba ∪ ba2 . . .)(b ∪ ba ∪ ba2 . . .)

| {z }
q1 −1
..................
(b ∪ ba ∪ ba2 . . .) . . . (b ∪ ba ∪ ba2 . . .)(b ∪ ba ∪ ba2 . . .).
| {z }
qn−1 −1
The first factor gives ap0 ; each next q0 − 1 factor gives a b; the factor which
follows gives bap1 , and so on: on every line, the factors above the braces
give b each, and the last factor gives the concatenation of b and a in the
corresponding degree.

13
 FINITE REPRESENTATION OF LANGUAGES.

THE CENTRAL ISSUE IN THE THEORY OF COMPUTATION IS THE

REPRESENTATION OF LANGUAGES BY FINITE SPECIFICATIONS

∪ the union operation;

◦ the concatenation operation;

∗
the closure operation;

Regular Language (informal definition): any language that can be obtained

by a finite application of the three operations above to a given finite set of
words.
Regular expression over an alphabet Σ is a string over the alphabet
[
Σ ∪ {ǫ, ), ( , ∅, ,∗ }
such that the following holds

1. ∅, ǫ and each member of Σ is a regular expression.

2. If α and β are regular expressions, then so is (αβ).
S
3. If α and β are regular expressions then so is (α β).
4. If α is a regular expressions then so is α∗.
5. Only an expression which can be obtained by applying (1) through (4)
is regular.

The class of regular languages (sets) over an alphabet Σ is the minimal

collection of sets containing ∅ and the set {a} for every a ∈ Σ, and closed
under the operations of union, concatenation, and Kleene star.
Standard convention. Parentheses in an expression may be omitted.

Problem 31 For each of the sets below, give examples of strings in and not
in the sets (Σ = {a, b})

14
(a) {w : for some u ∈ ΣΣ, w = uuR u}
(b) {w : ww = www}
(c) {w : for some u and v, uvw = wvu}
(d) {w : for some u, www = uu}

Problem 32 Rewrite each of the regular expressions as a simpler expression

representing the same set.

(a) ∅∗ ∪ a∗ ∪ b∗ ∪ (a ∪ b)∗
(b) ((a∗b∗)∗ (b∗a∗ )∗)∗
(c) (a∗b)∗ ∪ (b∗a)∗
(d) (a ∪ b)∗a(a ∪ b)∗

Problem 33 A regular expression is in disjunctive normal form if it is of

the form (α1 ∪ α2 . . . ∪ αn ) for some n ≥ 0, where none of the αi contains
S
an occurrence of . Show that every regular language is represented by an
expression in disjunctive normal form.

6 Principle of Mathematical Induction

Let A be a set of nonnegative integers such that

1. 0 ∈ A;
2. ∀n ∈ N , if {0, . . . , n} ⊆ A, then n + 1 ∈ A.

Then A = N .

Applying Mathematical Induction

15
The task: Given property P = P (n), prove that it holds for
all integers n ≥ 0.

Basis: show that P (0) is correct;

Induction assume that for some fixed, but arbitrary integer n ≥ 0,

hypothesis: P holds for all integers 0, 1, . . . , n

Induction step: prove that the induction hypothesis, P (n), implies that
P is true of n + 1: P (n) =⇒ P (n + 1)

Conclusion: using the principle of Mathematical Induction

conclude that P (n) is true for arbitrary n ≥ 0.

Problem 34 Prove that for all n > 10

n2 − n
n−2< .
12

Proof: Define property P (n) by

k2 − k
P (n) : ∀k ≤ n (k > 10; n > 10), k − 2 < .
12
Then,
Basis: for n = 11,
112 − 11 110 55 1
11 − 2 < =⇒ 9 < = =9+ .
12 12 6 6
Notice that the base of the induction proof start with n = 11, rather than
with n = 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 define a
property Q(m) by Q(m) = P (n − 11), and consider Q for m ≥ 0.

16
Induction step. Suppose, given n ≥ 11, P holds true for all integers up n.
Then 2
P (n) =⇒ n − 2 < n 12−n
2
=⇒ (n + 1) − 2 − 1 < (n+1) −(n+1)−2n−1+1
12
(n+1)2 −(n+1)
=⇒ (n + 1) − 2 < 12 − 2n12 + 1
(n+1)2 −(n+1)
=⇒ (n + 1) − 2 < 12 (since n > 10)

The last inequality is P (n + 1).

Problem 35 (Ramsey Theorem) Let G be a graph. A clique (resp. in-

dependent set) in G is a subgraph in which any two vertices are adjacent
(respectively, no two are adjacent). Denote R(p, q) the smallest integer N
such that every graph with N vertices either contains a clique of size p, or
an independent set of size q. Prove that

R(p, q) ≤ R(p − 1, q) + R(p, q − 1).

 
2n
Then prove that every graph with n vertices either contains a clique of size
n, or an independent set of size n.

Problem 36 Prove that for all n ≥ 0

1 1 1
1+ + + . . . + n ≤ 1 + n.
2 3 2

Problem 37 A set with an even number of elements is called even. Guess

a formula for the number of even subsets of a set with n elements and prove
the formula by induction.

7 Pigeonhole principle

1st form: If n pigeons fly into k pigeonholes and k < n, then some pigeon-
hole contains at least two pigeons.
2nd form: If A and B are nonempty finite sets and |A| > |B|, then for any
function f : A → B, ∃a, b ∈ A, such that f (a) = f (b).

17
3rd form: Let f be a function from a finite set A to a finite set B, let
|A| = n, |B| = m, and k = ⌈n/m⌉. If k ≥ 1, then there are at least k
values a1 , . . . , ak such that f (a1) = . . . = f (ak ).

Problem 38 Prove that every sequence of n2 + 1 distinct numbers has either

an increasing subsequence of length n+1 or a decreasing subsequence of length
n + 1.

Proof. Consider an arbitrary sequence S = {ai } (i ∈ [1, n2 + 1]) of distinct

numbers and define ti to be the length of the longest increasing subsequence
starting at ai .
If no monotone increasing subsequence S of length n + 1 exists, then
∀i = 1, . . . , n2 + 1, ti ≤ n.
To use the Pigeonhole Principle, we now define function F : [1, n2 +1] → [1, n]
by
F (i) = ti (i = 1, 2, . . . , n2 + 1).

Since the domain A of F is of size n2 + 1 and the range B is of size n, by the

Pigeonhole Principle (3rd form) there are at least ⌈n2 + 1/n⌉ = n + 1 indices
i1 , i2, . . . , in+1 for which F takes the same value. Let
F (i1) = F (i2) = . . . F (in+1) = L.

Claim: for every j = i1, i2, . . . , in+1, aij > aij+1 .

Indeed, suppose aij < aij+1 for some j ∈ {1, 2, . . . , n + 1}. Then every mono-
tone increasing subsequence R starting with aij+1 can be included into a
longer monotone increasing subsequence starting with aij , by simply mak-
ing aij the first member and appending R to it. If R is the longest monotone
increasing subsequence starting at ij+1 , its length is L, which yields a length
L + 1 monotone increasing subsequence starting at aij . This contradicts the
conclusion from the Pigeonhole Principle, and thus, proves the claim.
Finally, we see that
ai1 > ai1 > . . . > an+1 ,
which proves the theore.

18
Problem 39 Prove that any subset A of a set {1, 2, 3, . . . , 2n} which has at
least n+1 elements, contains two numbers such that one of them is a multiple
of the other.

Proof. Define odd(x) to be the largest odd divisor of x. let R be an equiva-

lence defined by
R = {(a, b) : odd(a) = odd(b).}
There are n classes of R in [1, . . . , 2n] and there are n + 1 numbers. By
pigeonhole principle, two of the numbers are in the same class; this implies
that one of them is a multiple of the other.

8 Strings and languages

Terminology:
alphabet Σ: a finite set of symbols; binary alphabet: {0,1};
string over Σ:a finite sequence of symbols from Σ;
empty string e: ;
Σ∗: the set of all strings over an alphabet Σ
length of a string: the number of symbols in the string;
occurrences: COMMITTEE;
position w(i): ranges from 1 to the length of the string;
substring: COMMITTEE —— MIT;
suffix (prefix): COMMITTEE —— TEE (COM);

Operations on strings:

Concatenation: MUSH ◦ ROOM → MUSHROOM;

concatenation is associative: (uv)w = u(vw).

Reversal: MUSHROOMR = MOORHSUM;

Statement: For any two strings u and v, (uv)R = v R uR .

19
 Operations on languages:

Complement A = Σ∗ − A;

Union: L ∪ M;

Concatenation: LM = {w : w = uv; u ∈ L, v ∈ M};

Lk = LL . . . L;

Closure (Kleene star) L∗

L∗ = {e} ∪ L ∪ L2 ∪ . . .;

L+ = L ∪ L2 ∪ . . ..

Problem 40 What is ∅∗ ?

Problem 41 What is (L∗)∗?

Problem 42 Is it true that L ⊆ M implies L∗ ⊆ M ∗ ?

Problem 43 Is it true that L ⊆ M implies L+ ⊆ M + ?

Problem 44 Prove that (wR )R = w

Problem 45 Prove that if v is a substring of w, then v R is a substring of

wR .

Problem 46 Under what circumstances is L+ = L∗ − {e}?

Additional Problems in Discrete mathematics.

Problem 47 Let A = {a1 , a2, . . . , ap } (p ≥ 3) and let Nk denote the number

of subsets of A whose size is k (k = 1, 2, . . . , p). Which of the following three
statements is correct:
(a) N2 > Np−2; (b) N2 < Np−2; (c) N2 = Np−2? Explain.

20
Problem 48 How many eight digit numbers are there that contain a 5 and
a 6? Explain.

Problem 49 Prove by induction that

1 + 5 + . . . + (4n − 3) = n(2n − 1).

Problem 50 Find the smallest value of n for which

n
(a) 22 > 1, 000, 000;
(b) (n!)! > 1, 000, 000. Explain.

Problem 51 Describe an algorithm which computes x96 using at most seven

multiplications.

Problem 52 Determine whether the following is true or false:

(a) (n + 1)! = O(n!); (b) n3 = O(500n2); Explain.

Problem 53 What are the coefficients of the terms x1 , 1

x2 in the expansion of
(x + x1 )n, where (n > 2)? Explain.

Problem 54 The Euclidean algorithm is based on the theorem stating that

the last nonzero remainder produced in the set of Euclidean equations equals
gcd(b, c). A corollary to this theorem is: if g = gcd(b, c) , then there are
integers x and y such that g = xb + yc. Write a formal induction proof of
this Corollary.

Problem 55 Find pairs (b, c) such that gcd(b, c) equals (a) b/2; (b) b/3.

Problem 56 Let a, b, t be positive integers. Which of the following state-

ments is correct? Explain.
(a) gcd(a, b) < gcd(at, bt); (b) gcd(a, b) = gcd(at, bt); (c) gcd(a, b) > gcd(at, bt).

Problem 57 Using the Euclidean algorithm, find the greatest common divi-
sor of (1) 1008 and 539; (2) 662 and 414. Show all stages of the algorithm
in both cases.

21
Problem 58 If a, b, x, y are nonzero integers such that ax + by = 3, is
gcd(a, b) = 3? Explain.

Problem 59 Prove by induction that

F1 + F3 + . . . + F2n−1 = F2n,
where Fi denotes the ith Fibonacci number.

Problem 60 Suppose that the sequence Gi is defined by G0 = 0; G1 =

1; Gn = Gn−1 + 2Gn−2. Determine which of the following propositions are
true:

(a) Gn = O(n2 )
(b) Gn = G0 + G1 + . . . Gn−1
(c) Gn < 2n (n = 0, 1, . . .)

Problem 61 Let Σ be an alphabet and L be a language over Σ. Prove that

if L2 ⊆ L, then L+ ⊆ L.
L+ = L ∪ L2 ∪ L3 ∪ . . . .

Problem 62 Prove that for every integer n > 0, 5n − 2n is divisible by 3.

Problem 63 For every integer n ≥ 0,

n
X n(n + 1)(2n + 1)
2
i = .
i=1 6
Prove.

Problem 64 For every integer n ≥ 0,

n
X 1 n
= .
i=1 i(i + 1) n+1
Prove.

Problem 65 For any n ≥ 4, n! > 2n .

22
Problem 66 For any w ∈ {0, 1}∗, if w starts with 0 and ends with 1, then
it contain s a substring 01.

Problem 67 For any integers a and b with 0 ≤ a ≤ b, and every integer

n ≥ 1, bn − an is divisible by b − a.

23
Problem 68 For every integer n ≥ 1,
Xn √ √
i > 2n n/3.
i=1

Proof. We prove it by induction on n.

Base. For n = 1, the left part is 1 and the right part is 2/3: 1 ¿ 2/3.
Inductive step. Suppose the statement is correct for some n ≥ 1; we prove
that it is correct for n + 1. Thus,
√ √ √ √
Given: ni=1 i > 2n n/3; Prove: n+1
P P
i=1 i > 2(n + 1) n + 1/3.

X √
n+1 n
X √ √
i=( i) + n + 1 (1)
i=1 i=1

Using the given inequality, we evaluate the right part of (1)

n √
X √ √ √
( i) + n + 1 ≥ 2n n/3 + n + 1. (2)
i=1

The following sequance of equivalent inequalities completes the proof:

√ √ √
2n n/3 + n + 1 ≥ 2(n + 1) n + 1/3 (3)
√ √ √
2n n + 3 n + 1 ≥ 2(n + 1) n + 1 (4)
√ √
2n n ≥ (2n − 1) n + 1 (5)
4n2n ≥ (2n − 1)2(n + 1) (6)
4n3 ≥ (4n2 − 4n + 1)(n + 1) = 4n3 − 3n + 1 (7)
0 ≥ −3n + 1. (8)
The last inequality holds true for any n > 0.

Problem 69 Prove that for every n ≥ 1 and every m ≥ 1, the number of

functions from {1, 2, . . . , n} to {1, 2, . . . , m} is mn .

Problem 70 The numbers an , for n ≥ 0, are defined recursively as follows:

a0 = −2; a1 = −2; for n ≥ 2, an = 5an−1 − 6an−2.
Show that for every n ≥ 0, an = 2 × 3n − 4 × 2n .

24
Problem 71 Let Σ be an alphabet. Under what conditions two distinct non-
empty strings x, y satisfy xy = yx? Either prove it cannot occur, or describe
precisely the circumstances under which it can.

Problem 72 For a finite set S, |S| denotes the number of elements of S. Is

it always true that for finite languages A and B,

|AB| = |A| × |B|?

Either prove it or find a counterexample.

Problem 73 Let L be a language over an alphabet Σ. Under what circum-

stances L+ = L∗ ?

Problem 74 Give an example of two non-empty languages L1 and L2 that

satisfy the following two conditions:

1. L1 L2 = L2 L; and
2. Neither language is a subset of the other.

Problem 75 Show that for any language L, L∗ = (L+)∗ = (L∗)∗ = (L∗)+.

L+ = L∗ ?

25
9 Order of functions

Notations:
N : (resp. N +) set of natural (resp. positive natural) numbers;

R (resp. R+ ) set of real (resp. positive real) numbers;

Floors and ceilings; ⌊x⌋; ⌈x⌉;
Polynomials: q0 + q1n + . . . + qb nb; exponentials: an ;
b 2 3
limn→∞ ann = 0; ex = 1 + x + x2 + x3! + . . .;
Logarithms: lg n = log2 n, (binary logarithm); ln n = loge n;

Factorials: n! = 1 · 2 · 3 · . . . · n.
√ √
2πn ( ne )n ≤ n! ≤ 2πn ( ne )(n+1/12);
√
n! ≈ 2πn ( ne )n (1 + Θ( n1 ));
Fibonacci numbers: F0 = 0; F1 = 1; Fi = Fi−1 + Fi−2.
√ √
1+ 5 1− 5 φi√
−φ̂i
If φ = 2 ≈ 1.61803 . . . and φ̂ = 2 ≈ −0.61803 . . ., then Fi = 5
.
Frequently occurring complexity functions:
O(n) Linear function; when the size of the input doubles
the amount of work doubles;
N log N often arises when the algorithm breaks up the problem into
small subproblems; when the data doubles, the function
more than doubles, but not by much;
2 3
N (resp. N ) Quadratic (resp. Cubic) order; doubling the data size
quadruples (resp. increases by a factor of 8) the work;
N
2 Exponential order assumed to be impractical.

26
Given two functions f, g : R+ → R+
g = O(f ) ≡ ∃C > 0, n0 > 0
such that g(n) ≤ Cf (n) for all n > n0
Function g(n) does not grow at a faster rate than f (n)

g = Ω(f ) ≡ ∃C > 0, n0 > 0

such that g(n) ≥ Cf (n) for all n > n0
Function g(n) grows at least as fast as f (n) does

g = Θ(f ) ≡ (g = O(f )) & (g = Ω(f ))

g(n) and f (n) grow at the same rate

f (n) = o(g(n)) ≡ ∀c > 0, ∃n1 > 0

such that ∀n > n1, 0 < f (n) < cg(n);
equivalently, limn→∞ fg(n)
(n)
= 0.
f (n) is growing asymptotically slower than g(n).

g(n) = ω(f (n)) iff f (n) = o(g(n)).

g(n) is growing asymptotically faster than f (n).

27
Problem 76
Which of the statements below is correct and which is false?

1. n2 = O(n3 );
2. n3 = O(n2 );
3. 2n+3 = O(2n );
4. (n + 1)! = O(n!);
5. if f (n) = O(n) then [f (n)]2 = O(n2 );
6. if f (n) = O(n) then 2f (n) = O(2n );
7. if f (n) = O(g(n)) and g(n) = O(h(n)) then f (n) = O(h(n));
8. there are two functions f (n) and g(n) such that
f (n) 6= O(g(n)) and g(n) 6= O(f (n)).

28
Problem 77
Prove that

1. f (n) = Θ(g(n)) and g(n) = Θ(h(n)) imply f (n) = Θ(h(n));

2. f (n) = Θ(g(n)) and g(n) = O(h(n)) imply f (n) = O(h(n)) ;
3. f (n) = Ω(g(n)) and g(n) = Ω(h(n)) imply f (n) = Ω(h(n));
4. f (n) = o(g(n)) and g(n) = o(h(n)) imply f (n) = o(h(n)) ;
5. f (n) = ω(g(n)) and g(n) = ω(h(n)) imply f (n) = ω(h(n));
6. f (n) = O(g(n)) iff g(n) = Ω(f (n));
7. ex = 1 + x + Θ(x2) when x → 0;
8. (n + a)b = Ω(nb) (a and b are constants);
9. Is 2n+1 = O(2n )? Is 22n = O(2n )?
10. n! = o(nn ); n! = ω(2n); lg(n!) = Ω(n lg n).

29
Problem 78
Prove by induction that ith Fibonacci number satisfies the equality
i √
Fi = (φi − φ )/ 5,
√ √
1+ 5 1− 5
where φ = 2 (the golden ratio) and φ = 2 (the conjugate) of φ.

Problem 79
Prove by induction that ∀i > 0, Fi ≤ φi .

Problem 80
Show that quicksort’s best running time is Θ(n log n).

Problem 81
Construct a linear algorithm for sorting n non-negative integers of size ≤ Cn
for some constant C.

30