Math2020 Homework Due Last Week of Semester:Due Wed Dec 2: 4.2 ex 4, 6, 10, 14, 20, 32Due Fri Dec 4: 5.3 ex 2, 4, 8, 22, 24Math2020 Quiz on Monday November 30Compute the value of53. (Or computenrfor any small values of n and r.)Math2020 Final Exam GuideThe final exam is on Friday, December 11, 10am - noon.The final exam will have 8 questions, as follows:(1) A question on constructing a truth table for some proposition, e.g. forp ∨ (q ⊕ r), or some other proposition(2) A question taken from guide to test 2(3) A question taken from guide to test 3(4) A question taken from guide to test 3(5) A question on proof by induction. The question will be to prove one of thefollowing using induction. You will have to clearly show the base case andthe induction step(a)Pni=1i =12n(n + 1)(b)Pni=1i2=16n(n + 1)(2n + 1)(c)Pni=1i3=14n2(n + 1)2(d)Pni=1(2i − 1) = n2(e)Pni=1(2i − 1)2=13n(2n − 1)(2n + 1)(f)Pni=0ri=1−rn+11−r(g)Pni=11(2i−1)(2i+1)=n2n+1(h)Pni=1i(i + 1)(i + 2)(i + 3) =15n(n + 1)(n + 2)(n + 3)(n + 4)(i)Pni=1i2i−1= 1 + (n − 1)2n(j)Pni=1(3i + 1)2=12n(6n2+ 15n + 11)(6) Another question on induction. You will have to prove one of the follow-ing using induction. You will have to clearly show the base case and theinduction step.(a) For the Fibonacci numbers fn, we havePni=1fi= fn+2− 1(b) For the Fibonacci numbers fn, we havePn−1i=0f2i+1= f2n(c) For the Fibonacci numbers fn, we havePni=1f2i= f2n+1− 1(d) For the Fibonacci numbers fn, we havePni=1ifi= nfn+2− fn+3+ 2(e) Prove by induction that xn− 1 is divisible by x − 1 for n ≥ 1.(f) Prove by induction that n! > 2nfor n > 4.(g) Prove by induction that 34n− 1 is divisible by 80 for n ≥ 1.(h) Prove by induction that n3− n is always divisible by 3 for n ≥ 1.(i) Prove using induction thatnk+nk+1=n+1k+1for n ≥ 1, 0 ≤ k ≤ n.(j) Prove using induction that the nth derivative of xexis xex+ nex. Youmay assume the product rule for derivatives, and you may assumeformulas for the derivative of x and of ex.(7) A question on counting, showing knowledge of P (n, r), C(n, r) =nrandalso showing you know how to determine which to use and when otherformulas must be used. The question will be similar to one of the following,and may include more than one of the following parts:(a) How many ways are there to select three different pieces of fruit froma bowl of 5 different fruits?12(b) You go to the supermarket to buy three peices of fruit, which may ormay not all be the same. The supermarket sells 5 different kinds offruit. How many different possibilities are there for what you comehome with?(c) You are painting the windows frames on the front of a house. Thereare three windows and 5 choices of colors. How many different wayscould you paint them, if there is no requirement that they have to bedifferent colors from each other?(d) You are painting the windows frames on the front of a house. Thereare three windows and 5 choices of colors. How many different wayscould you paint them, if there is a requirement that they all have tobe different colors from each other?(e) You have 5 pieces of fruit which you are lining up on your kitchencounter. Your fruits are: 2 (identical) apples, 2 (identical) bananas,and 1 orange. How many different ways can you line them up?(f) You have 5 pieces of fruit which you are lining up on your kitchencounter. Your fruits are: 2 (identical) apples and 3 (identical) bananas.How many different ways can you line them up?(g) You have 5 pieces of fruit of which you are lining up three on yourkitchen counter (you will eat the remaining 2). Your fruits are: 2(identical) apples, 2 (identical) bananas, and 1 orange. How manydifferent ways can you line three of them them up?(h) You go to the cinema with three friends. If you all sit in four adjacentseats, how many different ways can you sit together?(i) You go to the cinema with three friends. Two of them must sit inadjacent seats to each other, but noone else cares about seating. Howmany ways can you sit together in four adjacent seats?(j) You go to the cinema with three friends. Two of them will not sit nextto each other. How many ways are there for you all to sit together infour adjacent seats?(8) Either a question on proof using the Pigeonhole principle, or a questionabout binomial coefficients. Similar to:(a) Prove that the number of ways of choosing r objects from n distinctobjects isn!r!(n−r)!(b) Prove thatnk+nk+1=n+1k+1for n ≥ 1 and 0 ≤ k ≤ n. Do not useinduction; instead, explain how each choice of k + 1 things from n + 1things corresponds either to a choice of k from n or of k + 1 from n.(c) State and prove the binomial theorem.(d) State the binomial theorem. Assuming the binomial theorem, provethatPni=0ni= 2n(e) Use the pigeon hole principle to show that if you have a set of 11numbers, then at least two have the same last decimal digit.(f) A candy machine has red, blue, green candies, given out at random.How many candies do you have to buy to be sure to get 5 of the samecolor?(g) If 5 integers are choosen from {1, 2, 3, 4, 5, 6, 7, 8} show that there mustbe a pair with sum equal to