## Question

2. Use Problem 1 to prove the following result: Suppose that x1 + x2 + ... + xn = k where xi ∈ Z and xi ≥ 1 for each i. Then the given equation has C (k − 1, n − 1) solutions.

3. Suppose that you have four puppies: Alfie, Sophie, Aristotle, and Ada. Suppose that you have twelve identical toys in the closet. In how many ways can the toys be distributed among the puppies if each puppy must receive at least one toy?

4. Let S be a subset of the set of ordered pairs of positive integers. We define S recursively as follows:

(a) Base: (0, 0) ∈ S.

(b) Recursive Step: If (a,b) ∈ S then (a,b+1) ∈ S, (a+1,b+1) ∈ S, and (a+2,b+1) ∈ S.

List the elements of S produced by the first four applications of the recursive definition. Use structural induction to show that a ≤ 2b whenever (a, b) ∈ S.

5. Let S = {(x,y) ∈ N2 :(2−x)(2+y)>2(y−x)} where N is the set of natural numbers {1,2,3,4,...}. Prove that S = T where T = {(1,1),(1,2),(1,3),(2,1),(3,1)}.

6. Let S = {x ∈ R: x(x−1)(x−2)(x−3)<0}. Let T be the interval(0,1) and U be the interval (2,3). Obtain and prove a simple set equality relating the sets S,T and U.

7. Let A be a nonempty set. Suppose that f : A → A is a function. Show that if f(f(x)) is one-to-one then f(x) is one-to-one.

8. Suppose that f : R → R is a function that satisfies f(xy) = xf(y) + yf(x) for all x,y ∈ R. Prove that f(1)=0 and that f(un)=nun−1 f(u)

for all n∈N and u∈R. (Hint: Let u∈R and use induction on n).

9. Use mathematical induction to prove that 5n + 5 < 5n+1 for all n ∈ N.

10. Let A be a set of size 2n where n is a positive integer. Let x ∈ A. Count the n element subsets of A that contain x and the n element subsets of A that do not contain x. Use this to show that C(2n, n) = 2C(2n − 1, n − 1).

11. Show, using a combinatorial argument, that C(2n, 2) = 2C(n, 2) + n2.

12. Using mathematical induction show that ¬(p1 ∧ p2 ∧ ... ∧ pn) ⇔ ¬p1 ∨ ... ∨ ¬pn.

13. Let G be a simple graph with n vertices. Suppose the degree of each vertex, denoted deg(v), satisfies 1 ≤ deg(v) ≤ n − 1 for each v in the vertex set of G. Show that there are at least two vertices of G that must have the same degree.

14. Let kn + 1 balls be placed into n ≥ 1 boxes, and let M be the largest number of balls that fall into a single box. What is the smallest possible value of M. Assume that k is a positive integer.

15. Let p1, p2, p3, ..., pn denote n people.

(a) How many ways are there to arrange k of these people?

(b) How many ways are there to arrange k of these people in a line if person p1 refuses to be next to person p2 in line?

(c) How many ways are there to arrange k of these people in a line if person p1 refuses to be in the same line with person p2?

16. How many ways are there to arrange the letters mamremmvwxyz?

17. A certain club has five male and seven female members. How many ways are there to form a seven person committee consisting of three men and four women?

18. Let R be a relation on the set of real numbers R. R is defined as follows(x,y) ∈ R ⇔ x−y ∈ Z, where Z is the set of integers. Prove R is an equivalence relation. Describe the equivalence class [1]. Describe the equivalence Show [1] ∩ [ 1 ] = ∅.

19. Let G and H be isomorphic graphs. Remember that this means that there exists a one-to-one onto function f : VG → VH that preserves adjacency. This means that if v1 and v2 are adjacent vertices in G then f(v1) and f(v2) are adjacent vertices in H. Show that there exists a one-to- one onto map g : EG → EH. Hint: Think of an edge as the pair (v1,v2). Note that since the graph is undirected then (v1,v2) and (v2,v1) denote the same edge in G.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.