## October 16^{th} Foundation Exam

### Questions for Discrete Structures

### Discrete Part I. Choose one question.

1. Prove by induction on *n* the following summation formula:

2. Let *g*: *A ®
* *A *be a bijective function. That is, *g* is both one-to-one and onto. For *n ³
* 2, define *g*^{n} = *g* o *g* o … o *g* , where *g* is composed with itself *n* times.

Prove that for *n ³ * 2, (1) *g*^{n} is a bijective function from
*A* to *A*; and (2) (*g*^{n})^{–1} = (*g*^{–1})^{n}.

### 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*^{n}b^{n} | *n* ³
0}.

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

*C* = {*a*}*{*b*}* , and

*D* = {*w* | *w* Î
*A**, and the number of occurrences of symbol *a* in *w* = the number of occurrences of symbol *b* in *w*}.

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

Solutions to the Discrete Structures questions.