91Ó°ÊÓ

Determine whether each of these sets is countable or un- countable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set. a) integers not divisible by 3 b) integers divisible by 5 but not by 7 c) the real numbers with decimal representations consisting of all 1 \(\mathrm{s}\) d) the real numbers with decimal representations of all1s or 9 \(\mathrm{s}\)

Find the domain and range of these functions. Note that in each case, to find the domain, determine the set of elements assigned values by the function. a) the function that assigns to each bit string the number of ones in the string minus the number of zeros in the string b) the function that assigns to each bit string twice the number of zeros in that string c) the function that assigns the number of bits left over when a bit string is split into bytes (which are blocks of 8 bits) d) the function that assigns to each positive integer the largest perfect square not exceeding this integer

List the first 10 terms of each of these sequences. a) the sequence that begins with 2 and in which each successive term is 3 more than the preceding term b) the sequence that lists each positive integer three times, in increasing order c) the sequence that lists the odd positive integers in in- creasing order, listing each odd integer twice d) the sequence whose nth term is \(n !-2^{n}\) e) the sequence that begins with 3, where each succeeding term is twice the preceding term f ) the sequence whose first term is 2, second term is 4, and each succeeding term is the sum of the two preceding terms g) the sequence whose nth term is the number of bits in the binary expansion of the number n (defined in Section 4.2) h) the sequence where the nth term is the number of letters in the English word for the index n

List the first 10 terms of each of these sequences. a) the sequence obtained by starting with 10 and obtaining each term by subtracting 3 from the previous term b) the sequence whose \(n\) th term is the sum of the first \(n\) positive integers c) the sequence whose \(n\) th term is \(3^{n}-2^{n}\) d) the sequence whose \(n\) th term is \(\lfloor\sqrt{n}\rfloor\) e) the sequence whose first two terms are 1 and 5 and each succeeding term is the sum of the two previous terms f) the sequence whose \(n\) th term is the largest integer whose binary expansion (defined in Section 4.2) has \(n\) bits (Write your answer in decimal notation.) g) the sequence whose terms are constructed sequentially as follows: start with 1 , then add \(1,\) then multiply by \(1,\) then add \(2,\) then multiply by \(2,\) and so on h) the sequence whose \(n\) th term is the largest integer \(k\) such that \(k ! \leq n\)

Find the domain and range of these functions. a) the function that assigns to each pair of positive integers the first integer of the pair b) the function that assigns to each positive integer its largest decimal digit c) the function that assigns to a bit string the number of ones minus the number of zeros in the string d) the function that assigns to each positive integer the largest integer not exceeding the square root of the integer e) the function that assigns to a bit string the longest string of ones in the string

Find the domain and range of these functions. a) the function that assigns to each pair of positive integers the maximum of these two integers b) the function that assigns to each positive integer the number of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 that do not appear as decimal digits of the integer c) the function that assigns to a bit string the number of times the block 11 appears d) the function that assigns to a bit string the numerical position of the first 1 in the string and that assigns the value 0 to a bit string consisting of all 0s

Suppose that Hilbert's Grand Hotel is fully occupied on the day the hotel expands to a second building which also contains a countably infinite number of rooms. Show that the current guests can be spread out to fill every room of the two buildings of the hotel.

Suppose that \(A=\\{2,4,6\\}, B=\\{2,6\\}, C=\\{4,6\\},\) and \(D=\\{4,6,8\\} .\) Determine which of these sets are subsets of which other of these sets.

For each of the following sets, determine whether 2 is an element of that set. $$ \begin{array}{l}{\text { a) }\\{x \in \mathbf{R} | x \text { is an integer greater than } 1\\}} \\ {\text { b) }\\{x \in \mathbf{R} | x \text { is the square of an integer }\\}} \\ {\text { c) }\\{2,\\{2\\}\\}} \\ {\text { e) }\\{\\{2\\},\\{2,\\{2\\}\\}\\}} & {\text { f) }\\{\\{2\\},\\{\\{2\\}\\}\\}}\end{array} $$

Find the first five terms of the sequence defined by each of these recurrence relations and initial conditions. a) \(a_{n}=6 a_{n-1}, a_{0}=2\) b) \(a_{n}=a_{n-1}^{2}, a_{1}=2\) c) \(a_{n}=a_{n-1}+3 a_{n-2}, a_{0}=1, a_{1}=2\) d) \(a_{n}=n a_{n-1}+n^{2} a_{n-2}, a_{0}=1, a_{1}=1\) e) \(a_{n}=a_{n-1}+a_{n-3}, a_{0}=1, a_{1}=2, a_{2}=0\)