Chapter 2: Mathematical Preliminaries ~ 69
(c) R = {(L 1), (2, 2), (3, 3), (4, 4)}
(d) R = {(1, 2), (2. 3), (3, 1), (4, 4)}
2.11 If R is an equivalence relation on S, what can you say about R+. R*?
2.12 Letf:{a, b} * ----:> {a, b} * be given by f(x) = ax for every x E {a, b}*.
Show that f is one-to-one but not onto.
2.13 Let g: {a, b}* ----:> {a, b}* be given by g(x) = x
T . Show that g is
one-to-one and onto.
2.14 Give an example of (a) a tree \vith six vertices and (b) a binary tree
with seven vertices.
2.15 For the tree T given in Fig. 2.18, ansv,er the following questions:
(a) Is T a binary tree?
(b) Which vertices are the leaves of T?
(c) How many internal vertices are in T?
(d) \Vnat is the height of T?
(e) Wnat is the left-to-right ordering of leaves?
(f) Which vertex is the father of 5?
(g) Which vertices are the sons of 3?
Fig. 2.18 The tree for Exercise 2.15.
2.16 In a get-together. show that the number of persons who know an odd
number of persons is even,
[Hi/){: Use a graph.]
2.17 If X is a finite set show that !2
X
I = ?!Xj
2.18 Prove the following by the principle of induction:
(a) i k 2 = n(n + li 2n + 1)
k=l
(b)
11
1
I -k-(k-+-l)
k=l
n
(17 + 1)
(c) 10
211 - 1 is divisible by 11 for all II > 1.