MATH 211 Final With Solution, Spring 2005

MATH 211/Fall 2005 FINAL EXAM NAME: Instructions: a. There are thirty five questions on this exam. All of them are required. b. Write your name on the front page of the exam as soon as you receive a copy. c. All questions are equally weighted. The Final Exam grade ac- counts for 25% of the total grade of the course. d. Justify your answers for all the problems below in order to get full credit. e. If a wrong answer is given without any justification or explana- tion then no credit will be given for that question. f. Only when the question is preceded by TF, answer by circling T or F when the statement given is true of false respec- tively. . Read the question well before you answer it, so as to make sure that you are answering the same question asked! h. One white page is included in the end for scrap work. isje} (1) Suppose the variable x represents students and y represents courses and F(x) : x is a freshman, B(x) : x is full time student, T(a,y) : x is taking course y. Write the following statement using the above predicates and any needed quantifiers: “Every freshman is a full time student” Vx (Fx) —> B(x)) (2) repeat the previous question with the statement: “there are two freshmen who are taking the exact same courses”. 3x%,dm( LF Arr F(x) Fla) A Vy (Temy) acsy)) (3) Using ¢ for “it is cold” and r for “it is rainy”, write “it is rainy if it is not cold”. 1 “1 CC = (4) Using c for “it is cold” and w for “it is windy”, write “To be windy it is necessary that it be cold”. C sw (5) What is the coefficient of xy” in the expansion of (a + y)?°? OC became A1-t=17% #20. (6) prove that there does not exist three consecutive odd integers (other than 3,5,7) that are all prime. (Hint: use congruence modulo an appropriate integer, then take cases) 2n+), An+3 5 2n+5 Divi de n+) by JI. we hawe S Care’ \)) antl eomed2 => 2n4\| ts net prime Co hy VS 4%) Dane) Sl mod? => Qnxrs =o mod 313 Qn} ic mot prim 3) anel = Dumed2 =5 an45 2244 20 med 1 Sa Int not ae (7) Prove or disprove: if p and qg are primes greater than 2, then y m pq + 1 is never prime. Prove Truc - Since 9 4 yp ate odd ppt Pending Py 1s able odd. se PEA is even, Vente we le “Apl A (8) Use the Euclidean algorithm to find ged(392, 72) 392 = F2x5 4 32 3 (9) Use induction to prove that 1+4+7+10+-+-+(3n—2) = nena) Base Cases ned: Ix(3-9 14, iy Tw. : 2 Ind. Hy pothers Suppor , for Sarna Ky pe4aet Bkc~2) = RGE-V. Ind. Step we will Reeve the ste Sen enit for (+1) , Jen 4B k-2) + (3 (csi) -2) == i(3k-) 4 SiN we 3ki-K 4+ 6K+2_ K+) GK+9 on = 2 ” wa Diobes |) “V the stahement follows by mathemah cal induction (10) Define recursively the set of integers that are not divisible by 4. (include negative and positive values) Base Cove: LES 25, 2€S. Recursive step: 1§ se ote £446 g. =f se @ the = -4 ee Use the following for questions (11) to (14) : A 5-word is any string of five letters from the English alphabet. (11) How many 5-words are there? 26° (12) How many 5-words are there that contain a T? (or more) 5 oF 16 = 29 (13) How many 5-words that begin or end with an A are there? 4 4 : 26 +46 -26 (14) How many 5-words have exactly one vowel? (15) If S = {1,3,5,7, 11, 13} then the cardinality of the power set of S is: é (16) T (®) Determine the truth value of the statement JrVyP(x, y) where P(x,y) means “x + 2y = xy”. (17) T (®) Let A= {x,y}, B= {x,{x}}, then {2} C B-A. (18) (@ F For any integer 7, it is always possible to find an inverse of n — 1 modulo n. (19) T (®) It is possible to find an inverse of 12 modulo 15 while it is impossible to find an inverse of 15 modulo 12. (20) solve the congruence equation 127 = 4 mod 17 By He eh Dledla dl Euclidean A\5ervthm . 5x7 — Fxl2el, so word '2 wou It is -FPzelo: se j2oxZeto wed (F > L2G mdit a x= Itt +6; § =941,42,.. (21) Give an example of a function f : Z > N that is onto but not one to one. f¢2) =| 2|- octane: f ant % then |a\tle|=> fren AF (e). mle: given NEN, QF Zan. Thy f(Z)= Il = \nl an, (22) Write, in clear English, the negation of this statement: “I will go to the play or read a book, but not both”. _ wilh exther age. ag te Hy yi ond wu read a broek Or TL wall de both” a (23) Show that n is even whenever 3n? +8 is even. We need te show: Gn %) is etn ss Nn LS by cont aposition, Suppo on is odd, sp K such Mat we dK. se grad & Lu ev em ‘am 2 ntege ~ 3 (Gi 4k +1) 4 ¥ 2: . =\2K 412K 41 = 206K 4 6K45) 4). This prover hat Sn>+ 3 as odd. (24) Let A and B be two sets such that |A| = 4 and |B] = 7, Find the number of one to one functions from A to B. : , > 2 TO. (25) Write the binomial expansion of (2x + day” at iF z, fm ax(4) =, (22. Z L= z Use the following for questions (26) to (29): A club with 20 women and 17 men needs to form a committee of six members. (26) How many committees are possible? ‘ae ) 4 (27) How many committees are possible if the committee must in- clude three men and three women? () oy 4. chee 3 womin CB ae by alta. predact euille. wre yh (> [7 ) dol AA x —= s) 3 3) A+ 3) 14) See VK IBRVE wba Vo. F500 6x € 7 ) (28) How many committees are possible if the committee must in- clude three men and three women, and Angela must be on the committee? Pngele "4 already imncluted, So we nud gw MAL worn Ss eA * Greer (29) The committee will consist of a president, a vice president, a secretary, a treasurer, and two members at large, AND it must consist of three men and three women, how many such commit- tees can we make? \t he worm &B mm: Ce) CS) ok | A chosen 6 | gPy ow oy Te cheese members with kYlos . The owe 2 aN G aroma cally mem bev) ax: danse + ( sd x 6 xSx tx = 279072000 Use the following for ee ) to (32): The ni Lucas number obeys the recurrence relation /,, = |,-) + l,-2, and the initial conditions /, = 2, l) = 1. (30) Show that 2? +13 +--- +2 =Ujlngi +2 for alls n> 1 ey Snduckion: Gace Cave: nals \* -2° =4; Dyn +72 Ind, hyp \ alin SOL perme inesen eet Ye ee f recs +e : 2 (& ind. hy:) = W(h + Qie+t) 42 = | oe ee by NOW CH of the SI tens Jus ‘ The groof. Gel aw-> by dbx. principle (31) Find the n“" term explicitly (i.e. solve the recurrence relation). of mn hd _ ch wmateta tie 4.9 wk on ( Lice MJ f He Fil enece: eee, as gel (oy a \4V5 & ANS rere Seludim Na Clava)" ai 4 (WEY 2) sng a2 Lat we get tue equation. Solin we ok X= , he ae CG) = = Lays Vbewce (1B, (QBN (ode it!) Dw Det, =4, Z (32) Find the general solution of the inhomogeneous recurrence re- lation: Gy, = Gp—1 + An—2 + 2". h i ms. Qe (l +5) ( | a | Teams ai solu : ay = X = + OX) “i . Sint 2 xx wet me awk of He charachnis He eqn. we Yok fr a park cuban srlution of Hye form ( compare Ah P ae wlhiee S be nat a, watt) ar pluaging, Hho in He necumince equalon We get C= el. ut+2 so ay = AP a? 2 wy), we (EY 2 (33) Explain why the number of binary strings of length n that con- tain 000 as a substring can be modelled by the solution to the recurrence equation ay, = dy—1 + dn—2 + An—3 + 2"%. A binary string, Hat oo 000 ehanti anti V , or ol, or ook col OOO , a ee , On = Gy * Aa * An-2 + oS SA a ) Yhe Lest ont in the number of wags ty comple Me TuUmalnina (n-3) bow F having srenam teed Hat 000 “vs Swclw ced at Fest. Der ee (34) Give the necessary initial conditions in the previous question. hoz 97 A=0;, A71=° (35) Write the characteristic equation for the recurrence relation An = An—3 + 3An—4 + 2An-1. 4 3 , -2%Y.rfr-S3 =06 ( by ali —_—e Solu fm)