CMSC 250 Homework #9 Fall 20050201 & 0202Due Wed Nov 2 at the beginning of your discussion section.You must write the solutions to the problems single-sided on your own lined paper,with all sheets stapled together, and with all answers written in sequential order oryou will lose points.1. For each of the following statements, either use induction to prove that the statement is true,or give a counterexample with justification to show that it is false.(a) Suppose that the following recurrence relation holdsa1= 1, a2= 0, ∀i ∈ Z≥2, ai= 4ai−1− 4ai−2Prove that ∀n ∈ Z+, an= 2n(1 −n2)Base Case (n = 1, n = 2)n = 1: an= a1= 1 21(1 −12) = 2(12) = 1n = 2: an= a2= 0 22(1 −22) = 2(0) = 0IH(n = i, ∀i ∈ Z, 1 ≤ i ≤ k − 1)ai= 2i(1 −i2)IS(i = k)show: ak= 2k(1 −k2)proof:ak= 4 ak−1− 4ak−2= 4(2k−1(1 −k−12)) − 4(2k−2(1 −k−22))= 4(2k−2(2 − (k − 1)) − 4(2k−3(2 − (k − 2)))= 4(2k−3(2(3 − k) − (4 − k)))= 4(2k−3(2 − k))= 2k−1(2 − k)= 2k(1 −k2)(b) Suppose that the following recurrence relation holdsb1= 4 , b2= 12, ∀i ∈ Z≥2, bi= bi−2+ bi−1Prove that ∀n ∈ Z≥1, 4|bnBase Case (n = 1, n = 2)n = 1 bn= b1= 4 4|4n = 2 bn= b2= 12 4|12IH(n = m, ∀m ∈ Z, 1 ≤ m < k)4|bmIS(n = k)1show: 4|bkproof:bk= bk−2+ bk−14|bk−2therefore ∃r ∈ Z, bk−2= 4r4|bk−1therefore ∃s ∈ Zmb(k − 2) = 4s by def. of dividesbk= 4 r + 4s by substitutionbk= 4(r + s), r + s ∈ Z by closure of Z4|bkby def. of divides(c) Suppose that the following recurrence relation holdsd1=910, d2=1011, ∀k ∈ Z≥3, dk= dk−1· dk−2Prove that ∀n ∈ Z≥1, dn≤ 1Base Case (n = 1, n = 2)n = 1 dn= d1=9100 <910≤ 1n = 2 dn= d2=10110 <1011≤ 1IH(n = i, ∀i ∈ Z, 1 ≤ i < k)di≤ 1IS(n = k)show: dk≤ 1proof:dk= dk−1dk−2dk−1≤ 1/dk−2by IHdk−1≤ 1 from abovedk−1dk−2≤ dk−2by multiplying both sides by dk−2dk−2≤ 1 from abovedk−1dk−2≤ dk−2≤ 1dk≤ 1 by substitution2. Use set notation to answer each of the following questions:(a) Suppose A and B are sets defined a sA = {x ∈ Z|∀k ∈ Z≥1, x = 4k + 1}B = {x ∈ Z|∀k ∈ Z≥1, x = 3k + 5}i. List 1 0 elements of A ∪ Bii. List 10 elements of A ∩ BNote:A = { 5, 9, 13, 17, 21, 25 , 29, 33, 37, 41... }B = {8, 1 1, 14, 17, 20, 23, 26, 29, 32, 35... }A ∩ B = {x ∈ Z|∀k ∈ Z≥1, x = 12k + 17}(b) For each of the following expressions, use a Venn diagram representing the universe U andthe two subsets of that universe A and B. Shade the part of the diagram that correspondsto the set specified by the expression. Note: Acmeans the complement of A.2i. Acii. Bciii. (A ∪ B)civ. Ac∩ Bcv. Ac∪ Bcvi. (A ∩
View Full Document