Mathematics 243, section 3 – Algebraic Structures Solutions for Problem Set 4 due: October 5, 2012

‘A’ Section

1. Consider the following relations defined on the set ℤ. In each case, say whether the relation is reflexive, symmetric, transitive. Justify your answers.

a. xRy if and only if (−1)^{x} = (−1)^{y}

Solution: We see

(−1)^{x} = \begin{cases}+1 & if x is even \\ −1 & if x is odd \end{cases}

Hence xRx is true for all x, so R is reflexive. Similarly, if xRy then x, y are both even or both odd. So yRx follows, and R is symmetric. Finally R is transitive since xRy and yRz imply x, y, z are either all even or all odd.

b. xRy if and only if x · y ≥ 0

Solution: xRx is true for all x ∈ ℤ, since x^{2} ≥ 0. So R is reflexive. Similarly, R is symmetric since multiplication in ℤ is commutative, so xy = yx and if xy ≥ 0, yx ≥ 0 too. R is not transitive since for instance (1)R(0) is true and (0)R(−1) is true, but (1)R(−1) is not true.

c. xRy if and only if |x − y| ≤ 2

Solution: This is similar to b in the sense that this relation is reflexive since |x−x| = 0 ≤ 2 for all x, and symmetric since |x − y| = |y − x| for all x, y ∈ ℤ. But it is not transitive, since for example (−2)R(0) is true since |(−2) − 0| = 2 ≤ 2 and (0)R(2) is true since |0 − 2| = 2 ≤ 2, but (−2)R(2) is not true since | − 2 − 2| = 4.

d. xRy if and only if x has the same number of base 10 digits as y, ignoring signs of x, y.

Solution: This is reflexive – every x has the same number of base 10 digits as itself. Similarly, it is symmetric since if x has the same number of digits as y, then y has the same number of digits as x. It is also transitive, since if x and y have the same number of digits and y and z have the same number of digits, then so do x and z.

e. xRy if and only if the sum of the base 10 digits of x is the same as the sum of the base 10 digits of y, ignoring signs of x, y.

Solution: This is reflexive, symmetric, and transitive as in part d (just replace “number of digits” by “sum of digits” everywhere).

2. Which of the relations in question 1 are equivalence relations? For those that are, say exactly which integers make up the equivalence class [11] using correct set notation.

Solution: From the answers to question 1, the relation in a is an equivalence relation and

[11] = {m ∈ ℤ | m is odd}

The relation in d is also an equivalence relation. The equivalence class of [11] consists of all positive or negative integers that have the exactly two digits in their base 10 forms:

[11] = {±10, ±11, ±12, …, ±99}.

Finally, the relation in part e is also an equivalence relation. The class of 11 consists of all numbers whose digits add up to 2:

[11] = {±2, ±20, ±200, …, ±11, ±101, ±110, …}

(Note: there can be any number of 0 digits in these.)

3. Let R be the relation on ℤ defined by xRy if and only if 4x − 15y is a multiple of 11. Show that R is an equivalence relation and describe all of the equivalence classes for R.

Solution: For all integers x, xRx is true since 4x − 15x = 11 · (−x) is a multiple of 11. Hence R is reflexive. If xRy, then 4x − 15y = 11k for some integer k. But then 4y − 15x = −(4x − 15y) − 11x − 11y = 11(−k − x − y) is a multiple of 11, so yRx follows. Hence R is symmetric. Finally, if xRy and yRz then 4x−15y = 11k and 4y −15z = 11ℓ for some integers k, ℓ. But then 4x − 15y + 4y − 15z = 11(k + ℓ), so 4x − 15z = 11(k + ℓ + y) is also a multiple of 11. It follows that xRz is true, so R is transitive. This shows that R is an equivalence relation.

The equivalence class of any x ∈ ℤ is the set

[x] = {y | xRy} = {y | 4x − 15y = 11k, for some integer k}

It can be seen that there are only 11 different classes:

[0] = {…, −22, −11, 0, 11, 22, …}
[1] = {…, −21, −10, 1, 12, 23, …}
⋮
[10] = {…, −12, −1, 10, 21, 32, …}

4. Decide whether each of the following statements is true. For those that are true, give a short proof using the postulates for ℤ given in §2.1 of the text. For those that are false, give a counterexample.

a. If xy = xz for integers x, y, z, then y = z.

Solution: This is false: let x = 0, y = 1, z = 2. b. If x < y, then x^{2} < y^{2}.

Solution: This is also false: Let x = −3 and y = 2. Then x < y, but x^{2} > y^{2}.

c. If z − x < z − y, then y < x.

Solution: This is true. If z − y > z − x, then (z − y) − (z − x) ∈ ℤ^{+}. But that says x − y ∈ ℤ^{+}, so by the definition of the order relation x > y.

‘B’ Section

1. In class we showed that the distinct equivalence classes of an equivalence relation R on a set A give a partition of A. Conversely, suppose

A = ⋃_{λ∈L} A_{λ}

is a partition of A. Show that the relation R on A defined by aRa′ if and only if a, a′ are both elements of the same subset A_{λ} is an equivalence relation.

Solution: Let a ∈ A. Then a is contained in only one of the A_{λ}, since they form partition. That implies aRa is true, and R is reflexive. Next, suppose xRy. That means that x and y are in the same set in the partition, so it follows that y and x are also in the same set. Hence yRx is also true and R is symmetric. Finally, if xRy and yRz are both true then x, y, z are all in the same set in the partition so xRz is also true. This shows R is transitive too, hence an equivalence relation.

2. In both parts of this problem, you will be working in ℤ, using the postulates from §2.1

a. Show that if x · y = 0, then x = 0 or y = 0. (Hint: Argue by contraposition. By the trichotomy postulate 4, if x ≠ 0, then x ∈ ℤ^{+} or −x ∈ ℤ^{+}, and the same is true for y.)

Solution: We want to show that if x ≠ 0 and y ≠ 0, then xy ≠ 0. By postulate 4 in the book’s numbering, if x ≠ 0, then x ∈ ℤ^{+} or −x ∈ ℤ^{+}. Similarly, y ∈ ℤ^{+} or −y ∈ ℤ^{+}. There are four possible combinations of statements that can be true here. If x ∈ ℤ^{+} and y ∈ ℤ^{+}, then xy ∈ ℤ^{+} by postulate 4b. If −x ∈ ℤ^{+} and y ∈ ℤ^{+}, then (−x)y ∈ ℤ^{+} by postulate 4b. But (−x)y = −(xy) ∈ ℤ^{+} by Theorem 2.2, and then xy ≠ 0. Similarly, x ∈ ℤ^{+} and −y ∈ ℤ^{+}, then x(−y) ∈ ℤ^{+} by postulate 4b. But x(−y) = (−y)x = −(yx) ∈ ℤ^{+} by Theorem 2.2, and then yx = xy ≠ 0. Finally, −x ∈ ℤ^{+} and −y ∈ ℤ^{+}, then (−x)(−y) ∈ ℤ^{+} by postulate 4b. But (−x)(−y) = xy ∈ ℤ^{+} by Exercise 5 in this section of the book (proof follows same idea as the proof (−1)(−1) = 1 done in class) and then xy ≠ 0.

b. From part a, deduce the cancellation law in ℤ: If x · y = x · z and x ≠ 0, then y = z.

Solution: If x · y = x · z, then x · (y − z) = 0. We are assuming x ≠ 0, so part a implies y − z = 0, and hence y = z.

3. Prove by mathematical induction: a. For all n ∈ ℤ^{+},

1^{2} + 2^{2} + ⋯ + n^{2} = \frac{n(n + 1)(2n + 1)}{6}.

Solution: The base case here is n = 1. The formula is true in that case because 1^{2} = 1 = \frac{1·2·3}{6}. Now assume the formula is true for k ∈ ℤ, and consider the case n = k + 1. We have, using the induction hypothesis and some algebra:

1^{2} + 2^{2} + ⋯ + (k + 1)^{2} = (1^{2} + 2^{2} + ⋯ + k^{2}) + (k + 1)^{2}

= \frac{k(k + 1)(2k + 1)}{6} + (k + 1)^{2}

= \frac{(k + 1)(2k^{2} + k + 6(k + 1))}{6}

= \frac{(k + 1)(2k^{2} + 7k + 6)}{6}

= \frac{(k + 1)(k + 2)(2k + 3)}{6},

which is what we wanted to show since

\frac{(k + 1)(k + 2)(2k + 3)}{6} = \frac{(k + 1)((k + 1) + 1)(2(k + 1) + 1)}{6}.

b. For all n ∈ ℤ^{+},

\frac{1}{1 · 2} + \frac{1}{2 · 3} + ⋯ + \frac{1}{n(n + 1)} = \frac{n}{n + 1}

Solution: The base case here is n = 1. The formula is true in that case because \frac{1}{1·2} = \frac{1}{2} = \frac{1}{1+1}. Now assume the formula is true for k ∈ ℤ, and consider the case n = k + 1. We have, using the induction hypothesis and some algebra:

\frac{1}{1 · 2} + \frac{1}{2 · 3} + ⋯ + \frac{1}{(k + 1)(k + 2)} = (\frac{1}{1 · 2} + \frac{1}{2 · 3} + ⋯ + \frac{1}{k(k + 1)}) + \frac{1}{(k + 1)(k + 2)}

= \frac{k}{k + 1} + \frac{1}{(k + 1)(k + 2)}

= \frac{k(k + 2) + 1}{(k + 1)(k + 2)}

= \frac{k^{2} + 2k + 1}{(k + 1)(k + 2)}

= \frac{(k + 1)^{2}}{(k + 1)(k + 2)}

= \frac{k + 1}{k + 2},

which is what we wanted to show since

\frac{k + 1}{k + 2} = \frac{k + 1}{(k + 1) + 1}.

c. For all n ≥ 2, n^{3} > 1 + 2n. Solution: The base case is n = 2, and the inequality is true in that case since 8 > 5. Now assume k^{3} > 1+2k and consider (k+1)^{3} = k^{3}+3k^{2}+3k+1 By the induction hypothesis, we see (k + 1)^{3} > 1 + 2k + 3k^{2} + 3k + 1 > 1 + 2(k + 1), since 3k^{2} + 3k + 1 > 3k + 1 > 2 for all k ≥ 2.

d. If |A| = n, then |P(A)| = 2^{n}. (Hint: For the induction step, let A = {a_{1}, …, a_{k}, a_{k+1}}. Every subset of A is of one of two types – the ones containing a_{k+1} and the ones not containing a_{k+1}. Count the number of subsets of each type by using the induction hypothesis.) Solution: When n = 0, A = ∅ has exactly 1 subset, namely ∅. Therefore |P(A)| = 1 = 2^{0}. So the base case is established. Now assume that |P(A)| = 2^{k} whenever |A| = k and consider A = {a_{1}, …, a_{k}, a_{k+1}}. Following the hint, note that

P(A) = S_{1} ∪ S_{2}

where S_{1} = {T ⊆ A | a_{k+1} ∈ T } and S_{2} = {T ⊆ A | a_{k+1} ∉ T }. By their definitions, S_{1} ∩ S_{2} = ∅, so

|P(A)| = |S_{1}| + |S_{2}|.

The subsets in S_{2} are in one-to-one correspondence with the subsets of {a_{1}, …, a_{k}}. Hence |S_{2}| = 2^{k} by the induction hypothesis. Every subset T in S_{1} contains a_{k+1}, so it can be written as T = T′ ∪ {a_{k+1}}, where T′ is a subset of {a_{1}, …, a_{k}}. Distinct T′’s give distinct T ’s so there are exactly as many elements of S_{1} as subsets of {a_{1}, …, a_{k}}. By the induction hypothesis again, that number is 2^{k}. Hence

|P(A)| = |S_{1}| + |S_{2}| = 2^{k} + 2^{k} = 2 · 2^{k} = 2^{k+1}.

Therefore |P(A)| = 2^{n} for all n ≥ 1 by induction.

4. The binomial coefficients are the numbers

\binom{n}{ℓ} = \frac{n!}{ℓ!(n − ℓ)!}

(where 0! = 1 by convention).

a. Show using the definition that for all ℓ with 1 ≤ ℓ ≤ n,

\binom{n}{ℓ} + \binom{n}{ℓ − 1} = \binom{n + 1}{ℓ}

Solution: We have

\binom{n}{ℓ} + \binom{n}{ℓ − 1} = \frac{n!}{ℓ!(n − ℓ)!} + \frac{n!}{(ℓ − 1)!(n − ℓ + 1)!}

The common denominator for these two fractions is ℓ!(n − ℓ + 1)!, so adding we have

\frac{n!}{ℓ!(n − ℓ)!} + \frac{n!}{(ℓ − 1)!(n − ℓ + 1)!} = \frac{n!(n − ℓ + 1 + ℓ)}{ℓ!(n + 1 − ℓ)!} = \frac{(n + 1)!}{ℓ!(n + 1 − ℓ)!} = \binom{n + 1}{ℓ}.

b. (The Binomial Theorem) Show by induction that for all n ≥ 1.

(a + b)^{n} = ∑_{ℓ=0}^{n} \binom{n}{ℓ}a^{ℓ}b^{n−ℓ}

(that is, the numbers \binom{n}{k} are exactly the coefficients of the various terms a^{k}b^{n−k} appearing in the expansion of (a + b)^{n}).

Solution: The base case n = 1 follows since \binom{1}{0} = 1 = \binom{1}{1}, and (a + b)^{1} = a + b = \binom{1}{0}b + \binom{1}{1}a. Now assume the theorem has been proved for n = k and consider the case n = k + 1. We have by the induction hypothesis,

(a + b)^{k+1} = (a + b)^{k}(a + b)

= (∑_{ℓ=0}^{k} \binom{k}{ℓ}a^{ℓ}b^{k−ℓ}) (a + b).

Expand the product on the last line using the distributive law and collect like terms. The coefficients of a^{k+1} and b^{k+1} are both equal to 1 by inspection. These match the formula to be proved since \binom{k+1}{k+1} = \binom{k+1}{0} = 1. Now assume 1 ≤ ℓ ≤ k. The a^{ℓ}b^{k+1−ℓ} term comes from

b · (a^{ℓ}b^{k−ℓ} term in first factor ) + a · (a^{ℓ−1}b^{k−(ℓ−1)} term in first factor ) .

From above (by the induction hypothesis), the coefficient of this term is

\binom{k}{ℓ} + \binom{k}{ℓ − 1} = \binom{k + 1}{ℓ},

where the right side comes by applying part a of this question. Therefore

(a + b)^{k+1} = ∑_{ℓ=0}^{k+1} \binom{k + 1}{ℓ}a^{ℓ}b^{k+1−ℓ},

and the result follows by induction.