October 16^th Foundation Exam

Solutions for Discrete Structures

Discrete Part I. Choose one question.

Proof: We prove this identity by using induction on n ³ 1.

Consider n = 1. The summation on the LHS is:

The formula on the RHS is:

Thus, LHS = RHS, so the Basis Step is proved.

Consider n = p. Assume the identity is true for n = p, for some p ³ 1; that is, assume

Consider n = p + 1. We need to prove the identity is true for n = p + 1; that is, we need to prove

Note that

So the LHS = RHS of the Induction Step.

Therefore, the identity of the problem is true for all n ³ 1.

2. Let g: A ® A be a bijective function. That is, g is both one-to-one and onto. For n ³ 2, define gⁿ = g o g o … o g , where g is composed with itself n times. Prove that for n ³ 2, (1) gⁿ is a bijective function from A to A; and (2) (gⁿ)^–1 = (g^–1)ⁿ.

Proof: We prove both (1) and (2) using induction on n ³ 2.

(Basis Step)

Consider n = 2. Since g: A ® A is a bijection, g² = g o g is a bijection, by the theorem that says the compostion of two bijections is a bijection.

Also, (g²)^–1 = (g o g)^–1, by the definition of g²

Thus, the Basis Step is proved.

(Induction Hypothesis)

Consider n = k. Assume g^k is a bijection, and (g^k)^–1 = (g^–1)^k, for some k ³ 2.

(Induction Step)

Consider n = k + 1. We need to prove (1) g^{k +1} is a bijection; and (2) (g^{k +1})^–1 = (g^–1)^{k +1}.

Note that g^{k +1} = g^k o g, by the definition of g^{k +1}, so g^{k +1} is a bijection because g^k is a bijection by the Induction Hypothesis, and its composition with g is also a bijection.

Further,

(g^{k +1})^–1 = (g^k o g)^–1, by the definition of g^{k +1}

Thus, the Induction Step is proved.

Therefore, we have proved that (1) gⁿ is a bijective function from A to A; and (2) (gⁿ)^–1 = (g^–1)ⁿ, for all n ³ 2.

Discrete Part II. Choose one question.

3. Let A = {a, b} denote a set of two symbols. Let S be a set of strings over A, satisfying the following property:

If u Î S and |u| > 0, then there exists a string v Î S such that u = avb.

Prove by induction that S Ì {aⁿbⁿ | n ³ 0}.

Proof: In order to prove S Ì {aⁿbⁿ | n ³ 0}, we need to prove that: if w Î S, then w Î {aⁿbⁿ | n ³ 0}.

We prove this statement by using induction on |w|, the length of string w.

(Basis Step)

Consider |w| = 0. In this case, w = l , the null string (you may use the symbol e.)

Since l = a⁰ b⁰, so w = l = a⁰ b⁰ Î {aⁿbⁿ | n ³ 0}. The Basis Step is proved.

(Induction Hypothesis)

Assume if w Î S, then w Î {aⁿbⁿ | n ³ 0} for all strings w with length |w| £ k, for some k ³ 0.

(Induction Step)

Consider the case if w Î S, and |w| = k + 1.

Note that |w| > 0, so there exists a string v Î S such that w = avb, by the property of S specified in the assumption. Since |v| = |w| - 2 = k + 1 - 2 = k - 1 £ k, so v Î {aⁿbⁿ | n ³ 0} by the Induction Hypothesis. That is,

v = a^mb^m, for some m ³ 0.

Thus,

w = avb = a(a^mb^m)b = a^{m +1}b^{m +1} Î {aⁿbⁿ | n ³ 0}.

So the Induction Step is proved.

Therefore, we have proved that

if w Î S, then w Î {aⁿbⁿ | n ³ 0} for strings w of any length |w| ³ 0.

That is, we have proved S Ì {aⁿbⁿ | n ³ 0}.

4. Let A = {a, b} denote a set of two symbols. Define the following two sets of strings over A:

Prove that C Ç D = {aⁿbⁿ | n ³ 0}.

Proof: To prove C Ç D = {aⁿbⁿ | n ³ 0}, we prove

(1)   C Ç D Ì {aⁿbⁿ | n ³ 0}; and
(2)   {aⁿbⁿ | n ³ 0}Ì C Ç D, by the definition of set equality.

To prove (1), let string w Î C Ç D. Thus, w Î C and w Î D. Since {a}* = {aⁿ | n ³ 0} and {b}* = {bⁿ | n ³ 0}, w Î C = {a}*{b}* implies w = a^mb^p, for some m, p ³ 0. Also, since w Î D, m = p because the number of occurrences of symbol a in w must be equal to the number of occurrences of symbol b in w. Therefore, w = a^mb^m Î {aⁿbⁿ | n ³ 0}, so (1) is proved.

To prove (2), let string w Î {aⁿbⁿ | n ³ 0}. Thus, w = a^mb^m, for some m ³ 0. Therefore, w Î C ={a}*{b}*, because a^m Î {a}* and b^m Î {b}*. Also, w Î D because the number of occurrences of symbol a in w = m = the number of occurrences of symbol b in w. Thus, w Î C Ç D, so (2) is proved.