3 Problem 3. (2 Marks) We will call sequence a symbol of the form = (a0, a1, . . . , an, . . .) where n, an R. The symbol an will be called general term of the sequence . An example of such sequence is = (3, 1, 4, 1, 5, 2, 6, 5, 9, . . . , dn, . . .) where dn is the n-th digit in the decimal representation of . Two sequences = (a0, a1, . . . , an, . . .) and = (b0, b1, . . . , bn, . . .) will be considered equal if the following holds: n, an = bn. In this case, we write = . Define the sum of two sequences = (a0, a1, . . . , an, . . .) and = (b0, b1, . . . , bn, . . .) to be a new sequence = (c0, c1, . . . , cn, . . .) with general term cn = an + bn for all natural numbers n. Assume we want to prove the following statement: (S1) For all pairs of sequences , , + = + . Given our definitions, proving this statement, suffices to prove the following statement: (S2) For all pairs of sequences , , the predicate P(,)(n) : an + bn = bn + an holds for all n N. If possible, provide a proof by induction (simple or complete) for (S2). If this is not possible, write a concise explanation (no more than two-three lines) why not.

Problem 4. (5 Marks) In this problem we will continue to work with sequences = (a0, a1, . . . , an, . . .) where n, an Z, that is sequences of integers. We will let Z = {(a0, a1, . . . , an, . . .)|n, an Z} be the set of all integer sequences. Lets define two operations on this set: Addition: (a0, a1, . . . , an, . . .) + (b0, b1, . . . , bn, . . .) = (a0 + b0, a1 + b1, . . . , an + bn, . . .). Its intuitively clear the additive inverse of = (a0, a1, . . . , an, . . .) is (a0, a1, . . . , an, . . .) (denoted by ) and the role of the zero is played by the sequence (0, 0, . . . , 0, . . .). You may take for granted that addition of sequences enjoys the usual properties that the addition of integers enjoys. Multiplication: (a0, a1, . . . , an, . . .)(b0, b1, . . . , bn, . . .) = (a0b0, a0b1 +a1b0, . . . ,Xn j=0 aj bnj , . . .). Multiplication also enjoys usual properties that mutiplication of intergers enjoys. In particular, the role of the unit is played by special sequence u = (1, 0, . . . , 0, . . .). Please note (just like integers!) we cant really define the inverse of a sequence (like for example, the inverse of 2, which in real numbers would be 1/2, is not actually an integer, so we say 2 cannot be inverted in the set of integers). Lets define two special integer sequences: x = (0, 1, 0, . . . , 0, . . .) and t = (2, 0, . . . , 0, . . .). Also define two subsets of Z: Set T = {z Z|f, g Z, z = t f + x g} where x, t are special sequences defined above. Set S will be defined structurally: (1) x S and t S, t and x are the special sequences from above (2) If f Z and g S then f g S (3) If f, g S then f + g S. Prove that S = T.

Problem 5. (2 Marks) Consider the following proof by complete induction: for any nonzero real number q, the following predicate holds for all natural numbers n: P(n) : q n = 1. Proof Base Case: P(0) : q 0 = 1 is true for any q 6= 0. Inductive Hypothesis: Assume for all 0 k < n it is true that q k = 1. Inductive case: Write q n = q n1q n1 qn2 using properties of exponents, because n = n 1 + n 1 (n 2). Note that both n 1 < n and n 2 < n so we can apply inductive hypothesis q n1 = q n2 = 1, hence q n = 1. Explain in two or three lines what is wrong with this proof.