Solved: We say that a function is computable if there is a

Find these terms of the sequence {an}, where an = 2 (_3) n + 5n.a) ao d) as

What is the term as of the sequence {an} if an equals

What are the terms ao, aI , a2 , and a 3 ofthe sequence {an }, where an equals a) 2 n + l? c) Lnj2J ? b) (n + It+l ? d) Lnj2J + fnj21?

What are the terms ao, aI , a2 , and a 3 ofthe sequence {an }, where an equals a) (-2t? c) 7 + 4 n ? b) 3? d) 2 n + (-2t?

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 increasing order, listing each odd integer twice d) the sequence whose nth term is n! - 2n e) the sequence that begins with 3, where each succeeding term is twice the preceding term t) the sequence whose first two terms are 1 and each succeeding term is the sum ofthe two preceding terms (This is the famous Fibonacci sequence, which we will study later in this text.) g) the sequence whose nth term is the number of bits in the binary expansion of the number n (defined in Section 3.6) 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 nth term is the sum of the first n positive integers c) the sequence whose nth term is 3 n - 2n d) the sequence whose nth term is L.Ji1J e) the sequence whose first two terms are 1 and 2 and each succeeding term is the sum of the two previous terms t) the sequence whose nth term is the largest integer whose binary expansion (defined in Section 3.6) 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 nth term is the largest integer k such that k! n

Find at least three different sequences beginning with the terms 1 , 2,4 whose terms are generated by a simple formula or rule.

Find at least three different sequences beginning with the terms 3, 5, 7 whose terms are generated by a simple formula or rule.

For each of these lists ofintegers, provide a simple formula or rule that generates the terms of an integer sequence that begins with the given list. Assuming that your formula or rule is correct, determine the next three terms of the sequence. a) 1, 0, 1 , 1 , 0, 0, 1, 1 , 1, 0, 0, 0, 1, .. . b) 1 , 2, 2, 3 , 4, 4, 5 , 6, 6, 7, 8, 8, .. . c) 1 , 0, 2, 0, 4, 0, 8, 0, 1 6, 0, .. . d) 3 , 6, 1 2, 24, 48, 96, 1 92, .. . e) 15, 8, 1 , -6, - l 3 , -20, -27, .. . t) 3, 5, 8, 12, 1 7, 23 , 30, 38, 47, .. . g) 2, 1 6, 54, 128, 250, 432, 686, .. . h) 2, 3 , 7, 25 , 12 1 , 72 1 , 504 1 , 4032 1, ...

For each of these lists of integers, provide a simple formula or rule that generates the terms of an integer sequence that begins with the given list. Assuming that your formula or rule is correct, determine the next three terms of the sequence. a) 3 , 6, 1 1 , 1 8 , 27, 38, 51, 66, 83 , 1 02, .. . b) 7, 1 1 , 15, 19, 23 , 27, 3 1 , 35, 39, 43 , .. . c) 1 , 1 0, 11, 1 00, 101, 1 10, Ill , 1 000, 1 001, 10 10, 101 1 , ... d) 1 , 2, 2, 2, 3 , 3 , 3, 3 , 3 , 5, 5, 5, 5, 5, 5, 5, ... e) 0, 2, 8, 26, 80, 242, 728, 2186, 6560, 1 9682, ... t) 1 , 3, 15, 105, 945 , 1 0395 , l 35135, 2027025, 34459425, ... g) 1 , 0, 0, 1 , 1 , 1 , 0, 0, 0, 0, 1 , 1 , 1 , 1 , 1 , ..

Show that if an denotes the nth positive integer that is not a perfect square, then an = n + {.Ji1}' where {x } denotes the integer closest to the real number x.

Let an be the nth term of the sequence 1 , 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, ... , constructed by including the integer k exactly k times. Show that an = Lffn+ 1J

What are the values of these sums? 5 4 a) L(k+ l) b) L (-2)j k = 1 j = O 10 8 c) L 3 d) L (2j+1 - 2j ) ; = 1 j = O

What are the values of these sums, where S = { I , 3, 5 , 7}? a) L } j ES c) L (Ij}) d) L 1 j ES j ES

What is the value of each of these sums of terms of a geometric progression? 8 8 a) L 3 2j b) L 2 j j = O j = 1 8 8 c) L (-3)j d) L 2 (-3)j j = 2 j =O

Find the value of each of these sums. 8 a) L(I +(-IY) j = O 8 b) L (3j - 2j) j = Oc) L (2 . 3 j + 3 . 2 j ) j = o 8 d) L (2j+1 - 2j ) j=O

Compute each of these double sums. 2 3 a) L L (i + j) i =lj=1 3 2 c) L L i i = l j=O 2 3 b) L L (2i + 3j) i =Oj=O 2 3 d) L L ij i = Oj=1

Compute each of these double sums. 3 2 3 2 a) L L (i - j) b) L L (3i + 2j) i =lj=1 3 2 i =Oj=O 2 3 c) L L j d) L L i 2l i =1 j =O i =Oj=O

5how that L = I (aj - ajI)=an - aO, where ao, aI , ... , an is a sequence of real numbers. This type of sum is called telescoping.

Use the identity l /(k(k + 1 = 1/ k - l /(k + 1) and Exercise 19 to compute L = I l /(k(k + 1 .

Sum both sides of the identity k2 - (k - 1)2 = 2k - 1 from k = 1 to k = n and use Exercise 19 to find a) a formula for L = I (2k - 1) (the sum of the first n odd natural numbers). b) a formula for L = I k.

Use the technique given in Exercise 1 9, together with the result of Exercise 21 b, to derive the formula for L = I k2 given in Table 2. (Hint: Take ak = k3 in the telescoping sum in Exercise 1 9.)

Find L lOok. (Use Table 2.)

Find L99k 3 . (Use Table 2.)

Find a formula for L;= o L .J7(j , when m is a positive integer.

Find a formula for L; = 0 L Jk j, when m is a positive integer.

What are the values of the following products? a) n:o i b) n= 5 i ) n lOo ( _ I)i d) n lo c 2 1=1 1=1

Express n! using product notation.

Find L = o j !.

Find n = o j !.

Determine whether each of these sets is countable or uncountable. For those that are countable, exhibit a one-toone correspondence between the set of natural numbers and that set. a) the negative integers b) the even integers c) the real numbers between 0 and ! d) integers that are multiples of 7

Determine whether each of these sets is countable or uncountable. For those that are countable, exhibit a one-toone correspondence between the set of natural numbers and that set. a) the integers greater than 10 b) the odd negative integers c) the real numbers between 0 and 2 d) integers that are multiples of 10

Determine whether each of these sets is countable or uncountable. For those that are countable, exhibit a one-toone correspondence between the set of natural numbers and that set. a) all bit strings not containing the bit 0 b) all positive rational numbers that cannot be written with denominators less than 4 c) the real numbers not containing 0 in their decimal representation d) the real numbers containing only a finite number of 1 s in their decimal representation

Determine whether each of these sets is countable or uncountable. For those that are countable, exhibit a one-toone correspondence between the set of natural numbers 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 s d) the real numbers with decimal representations of all Is or 9s

If A is an uncountable set and B is a countable set, must A - B be uncountable?

Show that a subset of a countable set is also countable.

Show that if A and B are sets, A is uncountable, and A S; B, then B is uncountable.

Show that if A and B are sets with the same cardinality, then the power set of A and the power set of B have the same cardinality.

Show that if A and B are sets with the same cardinality and C and D are sets with the same cardinality, then A x C and B x D have the same cardinality.

Show that the union oftwo countable sets is countable.

Show that the union of a countable number of countable sets is countable.

Show that the set Z+ x Z+ is countable.

Show that the set of all finite bit strings is countable.

Show that the set of real numbers that are solutions of quadratic equations ax2 + bx + c = 0, where a, b, and c are integers, is countable.

Show that the set of all computer programs in a particular programming language is countable. [Hint: A computer program written in a programming language can be thought of as a string of symbols from a finite alphabet.]

Show that the set of functions from the positive integers to the set {O, 1 , 2, 3 , 4, 5, 6, 7, 8, 9} is uncountable. [Hint: First set up a one-to-one correspondence between the set of real numbers between 0 and I and a subset of these functions. Do this by associating to the real number 0.d1d2 dn . the function I with I(n) = dn.]

We say that a function is computable if there is a computer program that finds the values of this function. Use Exercises 45 and 46 to show that there are functions that are not computable.

Show that if S is a set, then there does not exist an onto function I from S to peS), the power set of S. [Hint: Suppose such a function I existed. Let T = (s E Sis f/. I(s)} and show that no element s can exist for which I(s) = T.]