Chapter 1

Calculate the following series: (a) \(\sum_{i=1}^{3}(2+3 i)\) (c) \(\sum_{j=0}^{n} 2^{j}\) for \(n=1,2,3,4\) (b) \(\sum_{i=-2}^{1} i^{2}\) (d) \(\sum_{k=1}^{n}(2 k-1)\) for \(n=1,2,3,4\)

Find the binary representation of each of the following positive integers by working through the algorithm by hand. You can check your answer using the sage cell above. (a) 31 (c) 10 (b) 32 (d) 100

Let \(A=\\{0,2,3\\}, B=\\{2,3\\}, C=\\{1,4\\},\) and let the universal set be \(U=\\{0,1,2,3,4\\} .\) List the elements of (a) \(A \times B\) (e) \(A \times A^{c}\) (b) \(B \times A\) (f) \(B^{2}\) (c) \(A \times B \times C\) (g) \(B^{3}\) (d) \(U \times \emptyset\) (h) \(B \times \mathcal{P}(B)\)

Let \(A=\\{0,2,3\\}, B=\\{2,3\\}, C=\\{1,5,9\\},\) and let the universal set be \(U=\\{0,1,2, \ldots, 9\\} .\) Determine: (a) \(A \cap B\) (e) \(A-B\) (i) \(A \cap C\) (b) \(A \cup B\) (f) \(B-A\) (j) \(A \oplus B\) (c) \(B \cup A\) (g) \(A^{c}\) (d) \(A \cup C\) (h) \(C^{c}\)

List four elements of each of the following sets: (a) \(\\{k \in \mathbb{P} \mid k-1\) is a multiple of 7\(\\}\) (b) \(\\{x \mid x\) is a fruit and its skin is normally eaten \(\\}\) (c) \(\left\\{x \in \mathbb{Q} \mid \frac{1}{x} \in \mathbb{Z}\right\\}\) (d) \(\\{2 n \mid n \in \mathbb{Z}, n<0\\}\) (e) \(\\{s \mid s=1+2+\cdots+n\) for some \(n \in \mathbb{P}\\}\)

Calculate the following series: (a) \(\sum_{k=1}^{3} k^{n}\) for \(n=1,2,3,4\) (b) \(\sum_{i=1}^{5} 20\) (c) \(\sum_{j=0}^{3}\left(n^{j}+1\right)\) for \(n=1,2,3,4\) (d) \(\sum_{k=-n}^{n} k\) for \(n=1,2,3,4\)

Find the binary representation of each of the following positive integers by working through the algorithm by hand. You can check your answer using the sage cell above. (a) 64 (c) 28 (b) 67 (d) 256

Suppose that you are about to flip a coin and then roll a die. Let \(A=\) \(\\{H E A D S, T A I L S\\}\) and \(B=\\{1,2,3,4,5,6\\} .\) (a) What is \(|A \times B| ?\) (b) How could you interpret the set \(A \times B\) ?

List all elements of the following sets: (a) \(\left\\{\frac{1}{n} \mid n \in\\{3,4,5,6\\}\right\\}\) (b) \(\\{\alpha \in\) the alphabet \(\mid \alpha\) precedes \(\mathrm{F}\\}\) (c) \(\\{x \in \mathbb{Z} \mid x=x+1\\}\) (d) \(\left\\{n^{2} \mid n=-2,-1,0,1,2\right\\}\) (e) \(\\{n \in \mathbb{P} \mid n\) is a factor of 24\(\\}\)

(a) Express the formula \(\sum_{i=1}^{n} \frac{1}{i(i+1)}=\frac{n}{n+1}\) without using summation notation. (b) Verify this formula for \(n=3\). (c) Repeat parts (a) and (b) for \(\sum_{i=1}^{n} i^{3}=\frac{n^{2}(n+1)^{2}}{4}\)

What positive integers have the following binary representations? (a) 10010 (c) 101010 (b) 10011 (d) 10011110000

List all two-element sets in \(\mathcal{P}(\\{a, b, c, d\\})\)

Let \(U=\\{1,2,3, \ldots, 9\\} .\) Give examples of sets \(A, B,\) and \(C\) for which: (a) \(A \cap(B \cap C)=(A \cap B) \cap C\) (d) \(A \cup A^{c}=U\) (b) \(A \cap(B \cup C)=(A \cap B) \cup(A \cap C)\) (e) \(A \subseteq A \cup B\) (c) \((A \cup B)^{c}=A^{c} \cap B^{c}\) (f) \(A \cap B \subseteq A\)

Describe the following sets using set-builder notation. (a) \(\\{5,7,9, \ldots, 77,79\\}\) (b) the rational numbers that are strictly between -1 and 1 (c) the even integers (d) \(\\{-18,-9,0,9,18,27, \ldots\\}\)

Verify the following properties for \(n=3\). (a) \(\sum_{i=1}^{n}\left(a_{i}+b_{i}\right)=\sum_{i=1}^{n} a_{i}+\sum_{i=1}^{n} b_{i}\) (b) \(c\left(\sum_{i=1}^{n} a_{i}\right)=\sum_{i=1}^{n} c a_{i}\)

What positive integers have the following binary representations? (a) 100001 (c) 1000000000 (b) 1001001 (d) 1001110000

List all three-element sets in \(\mathcal{P}(\\{a, b, c, d\\})\).

Let \(U=\\{1,2,3, \ldots, 9\\} .\) Give examples to illustrate the following facts: (a) If \(A \subseteq B\) and \(B \subseteq C,\) then \(A \subseteq C\). (b) There are sets \(A\) and \(B\) such that \(A-B \neq B-A\) (c) If \(U=A \cup B\) and \(A \cap B=\emptyset\), it always follows that \(A=U-B\).

Use set-builder notation to describe the following sets: (a) \\{1,2,3,4,5,6,7\\} (b) \\{1,10,100,1000,10000\\} (c) \(\\{1,1 / 2,1 / 3,1 / 4,1 / 5, \ldots\\}\) (d) \\{0\\}

Rewrite the following without summation sign for \(n=3 .\) It is not necessary that you understand or expand the notation \(\left(\begin{array}{c}n \\\ k\end{array}\right)\) at this point. \((x+y)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l}n \\ k\end{array}\right) x^{n-k} y^{k}\)

The number of bits in the binary representations of integers increases by one as the numbers double. Using this fact, determine how many bits the binary representations of the following decimal numbers have without actually doing the full conversion. (a) 2017 (b) 4000 (c) 4500 (d) \(2^{50}\)

How many singleton (one-element) sets are there in \(\mathcal{P}(A)\) if \(|A|=n\) ?

What can you say about \(A\) if \(U=\\{1,2,3,4,5\\}, B=\\{2,3\\},\) and \((\) separately) (a) \(A \cup B=\\{1,2,3,4\\}\) (b) \(A \cap B=\\{2\\}\) (c) \(A \oplus B=\\{3,4,5\\}\)

Let \(A=\\{0,2,3\\}, B=\\{2,3\\},\) and \(C=\\{1,5,9\\} .\) Determine which of the following statements are true. Give reasons for your answers. (a) \(3 \in A\) (e) \(A \subseteq B\) (b) \\{3\\}\(\in A\) (f) \(\emptyset \subseteq C\) (c) \\{3\\}\(\subseteq A\) (g) \(\emptyset \in A\) (d) \(B \subseteq A\) (h) \(A \subseteq A\)

(a) Draw the Venn diagram for \(\bigcap_{i=1}^{3} A_{i}\). (b) Express in "expanded format": \(A \cup\left(\bigcap_{i=1}^{n} B_{i}\right)=\prod_{i=1}^{n}\left(A \cup B_{n}\right)\).

Let \(m\) be a positive integer with \(n\) -bit binary representation: \(a_{n-1} a_{n-2} \cdots a_{1} a_{0}\) with \(a_{n-1}=1\) What are the smallest and largest values that \(m\) could have?

A person has four coins in his pocket: a penny, a nickel, a dime, and a quarter. How many different sums of money can he take out if he removes 3 coins at a time?

Suppose that \(U\) is an infinite universal set, and \(A\) and \(B\) are infinite subsets of \(U\). Answer the following questions with a brief explanation. (a) Must \(A^{c}\) be finite? (b) Must \(A \cup B\) be infinite? (c) Must \(A \cap B\) be infinite?

For any positive integer \(k,\) let \(A_{k}=\\{x \in \mathbb{Q}: k-1

If a positive integer is a multiple of 100 , we can identify this fact from its decimal representation, since it will end with two zeros. What can you say about a positive integer if its binary representation ends with two zeros? What if it ends in \(k\) zeros?

Let \(A=\\{+,-\\}\) and \(B=\\{00,01,10,11\\}\). (a) List the elements of \(A \times B\) (b) How many elements do \(A^{4}\) and \((A \times B)^{3}\) have?

For any positive integer \(k,\) let \(A_{k}=\\{x \in \mathbb{Q}: 0

Can a multiple of ten be easily identified from its binary representation?

Let \(A=\\{\bullet, \square, \otimes\\}\) and \(B=\\{\square, \ominus, \bullet\\} .\) (a) List the elements of \(A \times B\) and \(B \times A\). The parentheses and comma in an ordered pair are not necessary in cases such as this where the elements of each set are individual symbols. (b) Identify the intersection of \(A \times B\) and \(B \times A\) for the case above, and then guess at a general rule for the intersection of \(A \times B\) and \(B \times A\), where \(A\) and \(B\) are any two sets.

The symbol II is used for the product of numbers in the same way that \(\Sigma\) is used for sums. For example, \(\prod_{i=1}^{5} x_{i}=x_{1} x_{2} x_{3} x_{4} x_{5} .\) Evaluate the following: (a) \(\prod_{i=1}^{3} i^{2}\) (b) \(\prod_{i=1}^{3}(2 i+1)\)

Let \(A\) and \(B\) be nonempty sets. When are \(A \times B\) and \(B \times A\) equal?

Evaluate (a) \(\prod_{k=0}^{3} 2^{k}\) (b) \(\prod_{k=1}^{100} \frac{k}{k+1}\)