MATH 211 Final With Solution, Spring 2005

MATH 346/Spring 2005 FINAL EXAM NAME: oy “VS Instructions: kK i | a. There are sixteen problems on this test. All of them are re- quired. b. All questions are equally weighted. The Final Exam grade ac- counts for 25% of the total grade of the course, b. Justify your answers for all the problems below in order to get full credit. c. Ifa wrong answer is given without any justification or explana- tion then no credit will be given for that question. (1) Suppose the variable x represents people, and F(x) : x is friendly, T(x): a is tall, A(z) : zis angry. Write the following statements using the above predicates and any needed quantifiers. (a) some tall angry people are friendly eI (b) if a person is friendly, then that person is not angry Wx ( F(X) > 1 Acx)) (2) Let the sequence {a,,} be defined recursively as a, = a3_, +2; ag = 0. Find the term ag of the sequence. —_ ae a,= 042 ; Aga 24+2=l0, a, = lo+t2= 1 oo hk (3) A communication channel can transmit two types of signals. One signal takes one microsecond and the other signal takes two microseconds to be transmitted. How many different messages 1 made of these two types of signals can be transmitted in 50 microseconds if a signal is started right after another is finished? 1) wrte a pecurrence nelation ; a.message can start with either kind ef signal, J it stants with Signet, we have (-1) moe mic seconds , re ws stants with signed 2, we have (n-2) eas, sé An = An-| +Gy-2. J Ao =o; a, ro ae 2) charact. eq. as ote eal ey a y—-\=o (= La VESiC3 dvs pe Ve | 2 | : a =) Atneral solution : %, foeter ; 4) w han n=O: XH +X, = 0 = 9 % = Xj when n=l: butt MTEC XL = Ke SE V5 (2%) =2— X= — _ | iS = ane Uae oh (4) Get the general solution for the inhomogeneous recurrence equa- vs On=t (\2 By tion Gy = 3an—1 + da_—2 + 2”. (i e ” Similar 1 2), solve the homeg. putlem : 7 ‘et Z ) 1) chan, <n a Ir—4“ao 2 Ma Ay Pee md se ape oA EN” Next Sind a partiakar solubon of inhomes. publn Cone of the form ad? “ @:2 png it in mecuin & eq. A 3.¢ oe ae 2", divide. Ais by 2, ke = 6C44c 4 4 = -6c=4— Ci 7% so opera] solathvents 7 % He CY + 2.2 Y) Qy 3 (5) Represent the number 0.71717171--- as a fraction. Hint: use a feometric sum. : Meee Hed sil cee Cay pL ee, ties ae = BODE) = joa loo loo BIA\0° zl . car A “ 99 MSNA Hu geemetii © Sum foes) (6) Determine whether the two propositions p + (q — r) and & ret | > P> (GAP) are equivalent i Pree ——< secre a te = pty emp yn iCiaet) = 4PyG4a rr) = ~P— (4 AT) sé Thuy ane not equivalent : use the aniignmunt PHT 5 427 & aT: the Sicst is To (TaF)EF uk He second is ToT wwe i \. (7) Let f(n) = 5 be a function from N to N. Answer the following two questions by giving either a proof or a counter example. (a) is f one to one? ne: $Coc) = £() = 0 (b) is f onto Yes ai nen an integer ey Consider 2 $(2n) = |= = ml =m (8) How many ways are there to choose 12 cookies if there are 5 varieties, including chocolate chips if at least four chocolate chip cookies must be chosen? Sour of OE dw are dictated c onec lake chips) cach of Ane othr B corkies can be selected form S vanielie Se ‘yy Mo product rte Wee have 5x KS _= 5% wine 8 (9) How many four letter words can be made using the letters {a, be, d,e, f,g,h} if the words must consist of different let- ters? (a word here is just a string of characters, meaning that it need not be meaningful) Z\nce_2wortds ole. diffount ay thes hone Moe Some Qakrbe lout shuffled , Wwe ale Devking ar The Ft way Ter aycan Le objects owt ef 3 ob jects Se we have PCB H)= By = BKK EKS words. (10) Prove that the sum of two even integers is even. Cmsidtt twe ener integvs men, Sma 2 obtvi des ™ &n, we have Me A ¥n-=2k2 Spc Sow integ ws Ki 4 Ke yp Van mew = 2k, + LK 4. = ve @ ki + Ke) ; Lem C2 2 | (n+) le., 14M CS even (11) What is the coefficient of z?y"* in the expansion of (a + y) By He binomial therem Wis AS an ae Lon \ ? ma \9 0, 2, 207 ys (12) How many students must be in class to guarantee that at least five were born on the same day of the week? Th we have 4x4 students , thee in He worst” Case , every Ly ctudeat? were. born onthe samc dog, if we add ome student thin by the _gigen hele pruncyl one dot will have 5S students, so Ancoweris 29, : (13) How many bit strings of length 10 have at least two zeroes in them? This as dvtal— pbitstang with one zee of ne Bereta = g!?_ lot = lo2t =I = \ol%3 4 (14) Use mathematical induction to prove that n! > 2"7! whenever n is a positive integer. I Base Cas€ ¢ n= ' Man 4 | 2 =~ A 4 i St. 5k -\ 7 wd \yp. Suppose jo Some Ki, el 2. ; “ “smd. step we nud te chow hot (ke!) ba But (Ka01 = (ke KIS KPA so(ka\) >2 y by Yh ind hyp. : Ki? Z we (<4%), «4 > a. ae eg ine, K+ | > 2k, ae Se o ws doy the. pand ple { madh. ind, MA Yin3\, Mu! eg! (15) Give a combinatorial proof that (=) = Shes (..) (2) where r does not exceed m and does not exceed n. Oywe Knew (™*") 1s Aw + wey hie chwore. ‘a objects wt of (men). | ii) Think of chaosing gbjecks qm vit w hore we \ave om <4 on cakegnies k on tum aaleim. catejery: Sima (impr < hs the + objects chosen wm include 4 objects brem the first Code gery, whine ee & 4 Phe ROAG SEES ee Hon Cane from the ald. cule - some hove EDF) CDP) t HEN) # COND Now sind Wee Awe methods count Vas w a a (16) Use the method of the generating function to find nr ae to the ie fais the recurrence relation a, = 3a,_,+2” with the initial condition ea 7 Jolows ag = 1. Let Gx) be Ha Serer ating fun ohm of Av, Mak i¢ G (2) = Pe Qn x”, are = Y k-[ & sum fom n=l te oo eo oo eos Dy Ait xn Dy Bilin Zen, Do 2s n=! n=! aa | Gedie 3G) = 1 Se a eee plex (2x eos Ge) oe | 2A Is (l-2x)(\-3x) f ine \~3x = AQ=30 +B80-2%) _ (Aap) BA+28)X (\-2*)C|-3x) (t-2x) C19 x) Ss A+ =1; 3A+28 =o =s5 A= 72k Se “EB +B =! => ~B +l Bas PP ies Fe kts em Cpe ek 5% (72 {—3x of al ~ n = 2 22) 4 3 D2 GO . pa ge eae ae A a a 2G 2) 2" n+ Se On = Soe +