Sample Problems in Discrete Mathematics: 1 Using Mathematical Induction

Sample Problems in Discrete Mathematics
This handout lists some sample problems that you should be able to solve as a pre-requisite to Computer
Algorithms. Try to solve all of them. You should also read Chapters 2 and 3 of the textbook, and look at
the Exercises at the end of these chapters. If you are unfamiliar with some of these topics, or cannot solve
many of these problems, then you should take a Discrete Math course before taking Computer Algorithms.
Using Mathematical Induction
The task:
Given property P = P (n), prove that it holds for

all integers n 0.
Base Case:
show that P (0) is correct;
Induction
hypothesis:
assume that for some fixed, but arbitrary integer n 0,

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.
Variants of induction:
(although they are really all the same thing)
Strong Induction:
The induction step is instead: P (0) P (1) . . . P (n) = P (n + 1)
Structural Induction:
We are given a set S with a well-ordering on the elements of this set.

For example, the set S could be all the nodes in a tree, and the ordering
is that v w if v is below w in the tree.
The Base Case is now to show P (w) for all w S which have no element
preceding it (i.e., such that there is no v w).
The Inductive Step is now to show that for any w S, we have that
(P (v) for all v w) = P (w).
Problem 1 Prove that for all n > 10

n2<
n2 n
.
12
Proof: Define property P (n) by

P (n) :
k n (k > 10; n > 10), k 2 <
k2 k
.
12
Then,
Base case: for n = 11,
110
55
1
112 11
= 9 <
=
=9+ .
12
12
6
6
11 2 <
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
P (n)
n
n 2 < n 12
2
(n + 1) 2 1 < (n+1) (n+1)2n1+1
12
2
(n + 1) 2 < (n+1) (n+1)2n1+1
+1
12
(n+1)2 (n+1)
2n
(n + 1) 2 <
12 + 1
12
(n+1)2 (n+1)
(n + 1) 2 <
(since n > 10)
12
=
=
=
=
=
The last inequality is P (n + 1).
Problem 2 For every integer n 1,

n
X
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,
Pn
Pn+1
Given:
Prove:
i > 2(n + 1) n + 1/3.
i=1 i > 2n n/3;
i=1
n+1
X
n
X
i=(
i) + n + 1
i=1
(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 sequence of equivalent inequalities completes the proof:
2n n/3 + n + 1 2(n + 1) n + 1/3
2n n + 3 n + 1 2(n + 1) n + 1
2n n (2n 1) n + 1
4n2 n
(3)
(4)
(5)
(2n 1)2 (n + 1)
(4n 4n + 1)(n + 1) = 4n 3n + 1
(7)
3n + 1.
(8)
4n
(6)
The last inequality holds true for any n > 0.

2
Problem 3 For every integer n 0,

n
X
i=0
i2 =
n(n + 1)(2n + 1)
.
6
Prove.
Problem 4 Prove 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: Let n be an arbitrary integer greater than 1. The Inductive Hypothesis is that for all integers
k such that 1 < k < n, we have that k can be written as a product of primes. Then, either n is a prime
itself (in which case it is a product of prime numbers), or n can be written as n = n1 n2 with both n1 and
n2 being integers greater than 1 and less than n. Thus, the Inductive Hypothesis applies to both n1 and n2 ,
and so each can be written as a product of prime numbers. Thus, n can be written as a product of prime
numbers as well.

Problem 5 What is wrong with the following classic proof that all horses have the same color?
Let P (n) be the proposition that for any set of n horses, all horses in this set have the same color.
Base Case: P (1) is clearly true.
Inductive Step: The Inductive Hypothesis is that P (n) holds; we will show that this implies P (n + 1). Let
A be an arbitrary set of n + 1 horses. Consider the first n horses in A, and the last n horses in A. Both of
these are sets of n horses, and so the inductive hypothesis holds for them, telling us that both the first n and
the last n horses of A have the same color. Since the set of the first n and the last n horses overlap, then
all n + 1 horses of A must have the same color, thus proving P (n + 1).
Problem 6 Prove by induction that
F1 + F3 + . . . + F2n1 = F2n ,
where Fi denotes the ith Fibonacci number.
Order of Functions
See Chapter 2 of the textbook, and the exercises therein.

Problem 7 Compare the following pairs of functions in terms of order of growth. In each case, determine
if f (n) = O(g(n)), f (n) = (g(n)), f (n) = (g(n)). Prove your answers.
(1)
(2)
(3)
(4)
(5)
(6)
(7)
f (n)
(lg n)a
2n log2 n
n
n2
log2 n
log2 n
1000(log2 n)0.999
n2
g(n)
nb
(here a, b > 0)
10n!
(log2 n)5
(nlog2 n)4
log2 (66n)
(log2 n)1.001
n(log2 n)15
Graph Theory
See also Chapter 3 of the textbook and the exercises therein.

Problem 8 Here is an example of Structural Induction in trees. Consider a rooted tree T = (V, E), where
nodes are labeled with positive integers: each node v V is labeled with an integer av . Assume that T obeys
the heap property, i.e., if w is a child of v, then aw < av . Prove that the root node r has the largest label of
all nodes in the tree.
Proof: Let Tv be the subtree of T rooted at v. We will prove the proposition P (v) which states that v has
the largest label in Tv . Base Case: If v is a leaf, then Tv consists of a single node v, and so P (v) is trivially
true. Inductive Step: Assume that P (w) is true for all children w of v. By the heap property, aw < av , and
by the inductive hypothesis, aw is the largest label in Tw . Therefore, av is the largest label in Tv , as desired.
We have now shown that P (v) holds for all nodes v V . Therefore, P (r) holds, and so r has 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
graph G, 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 10 Find an example of a directed graph and a DFS-forest such that vertex v is not a descendant
of u, but graph G has a path from u to v and dis[u] < dis[v] (here dis[u] is the distance from the root).
Problem 11
Describe an algorithm (in words, not a code), which for a given connected undirected graph G, directs its
edges in such a way that the following two conditions are satisfied:
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 12 Show how to tell if graph is bipartite (in linear time).
Additional Problems in Discrete Math and Logic
Problem 13 How many eight digit numbers are there that contain a 5 and a 6? Explain.
Problem 14 How many nine digit numbers are there that contain exactly two 5s?
Problem 15 What are the coefficients of the terms
Explain.
1
1
x , x2
in the expansion of (x + x1 )n , where (n > 2)?
Problem 16 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 17 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)
DeMorgans Laws
U (B C) = (U B) (U C)
U (B C) = (U B) (U C)
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 first statement logically imply the second?
Problem 19 (Contrapositive) Consider the following two statements: 100 percent of convicted felons consumed bread during their childhood. and People who do not consume bread as a child do not become felons.
Does the first statement logically imply the second?

Sample Problems in Discrete Mathematics: 1 Using Mathematical Induction

Uploaded by

Copyright:

Available Formats

Sample Problems in Discrete Mathematics: 1 Using Mathematical Induction

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Sample Problems in Discrete Mathematics: 1 Using Mathematical Induction

Uploaded by

Copyright:

Available Formats

Sample Problems in Discrete Mathematics

Using Mathematical Induction

Given property P = P (n), prove that it holds for

show that P (0) is correct;

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

prove that the induction hypothesis, P (n), implies that

using the principle of Mathematical Induction

(although they are really all the same thing)

The induction step is instead: P (0) P (1) . . . P (n) = P (n + 1)

We are given a set S with a well-ordering on the elements of this set.

Problem 1 Prove that for all n > 10

Proof: Define property P (n) by

k n (k > 10; n > 10), k 2 <

The last inequality is P (n + 1).

Problem 2 For every integer n 1,

Proof: We prove it by induction on n.

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

The following sequence of equivalent inequalities completes the proof:

2n n/3 + n + 1 2(n + 1) n + 1/3

The last inequality holds true for any n > 0.

Problem 3 For every integer n 0,

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

See also Chapter 3 of the textbook and the exercises therein.

Additional Problems in Discrete Math and Logic

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

You might also like