I need a top grade for this Graduate Level Discrete Maths.
Assignment 3 CS-GY 6003 INET Spring 2022 Due date: 11:55pm on April 15th 2022 on Gradescope. Instructions: Write or type out your solutions and hand in on Gradescope before the deadline. Justify your answers! Question 1: Counting . (a) 5 points Use a combinatorial argument to prove each of: (4n)! 22n · n! · n! = ( 4n 2n ) (2n− 1)2(2n− 3)2(2n− 5)2 . . . (1) (b) 4 points Use pascal’s triangle to prove( n + 1 r + 1 ) = n∑ k=r ( k r ) (c) 3 points Use Pascal’s identify to prove that: 22n = 2 [( 2n 0 ) + ( 2n 1 ) + ( 2n 2 ) + ( 2n 3 ) + . . . + ( 2n n− 1 )] + ( 2n n ) Question 2: Number Theory . (a) 4 points Let p = 4567 and q = 113. Pick a public key e where 86 ≤ e ≤ 94. Encode the message m = 100 and show how it is successfully decoded. (b) 3 points Suppose that in mod m we determine that the inverse of x is y. Explain why xk has an inverse in mod m for any k ≥ 1. What is the inverse of x3? (c) 5 points Solve the following for x in mod 397. Show your work without using a calculator. 203963 + x ≡ 2402 mod 397 (d) 5 points Use CRT to find a value of 0 ≤ x < 3393000="" that="" satisfies="" the="" following="" congruences:="" 2x="" ≡="" 15="" mod="" 29="" 19x="" ≡="" 100="" mod="" 1000="" x="" ≡="" 52="" mod="" 117="" (e)="" 5="" points="" use="" crt="" to="" solve="" the="" following="" for="" 0="" ≤="" x="">< 899="" .="" you="" must="" find="" all="" 4="" distinct="" solutions="" in="" that="" range.="" x2="" ≡="" 33="" mod="" 29="" x2="" ≡="" 66="" mod="" 31="" 1="" (f)="" 5="" points="" determine="" integers="" s="" and="" t="" such="" that="" 5744s="3260t" mod="" 4="" (g)="" 6="" points="" for="" each="" of="" the="" following,="" solve="" for="" x="" or="" prove="" that="" there="" is="" no="" solution:="" •="" 6x="" +="" 5="" ≡="" 20="" mod="" 91="" •="" 13x="" +="" 2="" ≡="" 20="" mod="" 91="" •="" 7x="" +="" 2="" ≡="" 23="" mod="" 91="" (h)="" 6="" points="" •="" update="" the="" solution="" to="" problem="" 14="" in="" set="" 11="" so="" that="" power(x,a,n)="" returns="" the="" value="" of="" xa="" mod="" n,="" where="" 0="" ≤="" a="">< n is an integer. • write a procedure fastexp(x,a,p) which determines the value of xa mod p where p ≥ 2 is a prime number. your procedure can assume that a ≥ 0 and n ≥ 1, which are both integers. your solution must use fermat’s last theorem, and may call power(x,a,n) from above. question 3: recurrence relations: . (a) 6 points • let f (n), n ≥ 1 be the fibonacci sequence defined in class. used the closed-form solution of the fibonacci sequence to find f (15). does this give you the exact same value as if you compute f (15) using the recurrence? explain why or why not. • define a sequence g(n) , n ≥ 1 as follows: let g(1) = 5 and g(2) = 8, and g(n) = g(n− 1) + g(n− 2) for n ≥ 3. what is the closed-form solution for g(n)? justify your answer. . (b) 6 points a child is building a tower out of a total of n blocks. let r of those blocks be red, and the remaining blocks are blue. the child builds a tower using all of the blocks. suppose that the tower is built with no adjacent red blocks. let b(n, r) be the number of ways to build such a tower. write a recursive definition for b(n, r), where n ≥ 0, and 0 ≤ r ≤ n. include your base cases. what is the solution to this recurrence? use your recurrence to solve for b(6, 2) and b(7, 4), and verify they are correct using your solution to the recurrence. (c) 5 points solve the following recurrence and prove your result is correct using induction: a0 = 1 a1 = 1 an = 4an−2 + 1 for n ≥ 2 (d) 4 points solve the following recurrence: an = 5an−2 − 4an−4 for n ≥ 4 a0 = 0, a1 = 1, a2 = 1, a3 = 1 (e) 5 points suppose we are given a rod of length n. we can cut rod into pieces in such a way that each piece length is a natural number of size at least 1. there are many ways to cut the rod. for example, if n = 5, we could cut it into pieces of size 1, 2, 2 or 4, 1 etc. write a recursive definition for p (n, k) which is the number of ways to cut a rod of length n where the maximum size of the pieces is k. your definition 2 is for n ≥ 1 and k ≥ 1. you do not need to solve the recurrence. use your recurrence to solve for p (7, 7) and p (7, 2). (f) 5 points a child is building a tower out of red, black, and green blocks. the red and black blocks have size 1 and the green block has size 2. a tower of height n is built using a sequence of the colored blocks, with the condition that no red blocks are adjacent. write a recursive definition t (n), n ≥ 1, for the number of possible towers of height n. you do not need to solve the recurrence. question 4: recursive procedures . (a) 6 points recall that in week 6 we considered the problem of distributing n identical items into k unlabelled groups. in this problem, you must write a recursive procedure called numberpartitions(n, k) that returns the number of ways of distributing n identical pennies into k piles, where each pile has at least 1 penny. the piles are not labelled, so the only thing that matters is the number of coins in each pile. your procedure must function properly for n ≥ 1 and 1 ≤ k ≤ n. use your procedure to verify the output for n = 8 and k = 4. (b) 6 points consider a making a postage of n cents using stamps of size 2, 3 and 4. suppose we must use at least one of each stamp denomination. write a recursive procedure called printpostage(n) that prints out a set of stamps that create a postage of size n. you must determine the correct base case and ensure that your recursive procedure handles that correctly. if no postage is possible, your procedure must print “no postage”. your procedure must handle all inputs of n ≥ 0. for example: findpostage(25) outputs stamps 4, 4, 4, 4, 4, 3, 2. there are other options possible, but just one correct option must be printed. (c) 6 points recall problem 4(c) from assignment 2. consider a new version of this problem where the bills have denominations 1, 5, 52, 53, . . .. as in the previous assignment, you owe your friend a debt of n dollars. you must transfer a set of bills between you and your friend in such a way that the debt is repaid. in this case, a bill denomination may be used at most two times. write a recursive procedure called printbills(n) that returns a list of the necessary bills, for n ≥ 0. the list should include positive numbers for bills you give your friend, and negative numbers for bills your friend gives you. for example, if n = 21, the output list should be [52,−5, 1]. for n = 32, the output list should be [25, 5, 1, 1]. *note: this is not a course on data-structures. so you may assume that you can create an empty list with the pseudo-code “x = list()” and use the following operations: -add elements to the list using x.add(25) -update/access element at index i using x[i] -determine the length using x.length(). 3 n="" is="" an="" integer.="" •="" write="" a="" procedure="" fastexp(x,a,p)="" which="" determines="" the="" value="" of="" xa="" mod="" p="" where="" p="" ≥="" 2="" is="" a="" prime="" number.="" your="" procedure="" can="" assume="" that="" a="" ≥="" 0="" and="" n="" ≥="" 1,="" which="" are="" both="" integers.="" your="" solution="" must="" use="" fermat’s="" last="" theorem,="" and="" may="" call="" power(x,a,n)="" from="" above.="" question="" 3:="" recurrence="" relations:="" .="" (a)="" 6="" points="" •="" let="" f="" (n),="" n="" ≥="" 1="" be="" the="" fibonacci="" sequence="" defined="" in="" class.="" used="" the="" closed-form="" solution="" of="" the="" fibonacci="" sequence="" to="" find="" f="" (15).="" does="" this="" give="" you="" the="" exact="" same="" value="" as="" if="" you="" compute="" f="" (15)="" using="" the="" recurrence?="" explain="" why="" or="" why="" not.="" •="" define="" a="" sequence="" g(n)="" ,="" n="" ≥="" 1="" as="" follows:="" let="" g(1)="5" and="" g(2)="8," and="" g(n)="g(n−" 1)="" +="" g(n−="" 2)="" for="" n="" ≥="" 3.="" what="" is="" the="" closed-form="" solution="" for="" g(n)?="" justify="" your="" answer.="" .="" (b)="" 6="" points="" a="" child="" is="" building="" a="" tower="" out="" of="" a="" total="" of="" n="" blocks.="" let="" r="" of="" those="" blocks="" be="" red,="" and="" the="" remaining="" blocks="" are="" blue.="" the="" child="" builds="" a="" tower="" using="" all="" of="" the="" blocks.="" suppose="" that="" the="" tower="" is="" built="" with="" no="" adjacent="" red="" blocks.="" let="" b(n,="" r)="" be="" the="" number="" of="" ways="" to="" build="" such="" a="" tower.="" write="" a="" recursive="" definition="" for="" b(n,="" r),="" where="" n="" ≥="" 0,="" and="" 0="" ≤="" r="" ≤="" n.="" include="" your="" base="" cases.="" what="" is="" the="" solution="" to="" this="" recurrence?="" use="" your="" recurrence="" to="" solve="" for="" b(6,="" 2)="" and="" b(7,="" 4),="" and="" verify="" they="" are="" correct="" using="" your="" solution="" to="" the="" recurrence.="" (c)="" 5="" points="" solve="" the="" following="" recurrence="" and="" prove="" your="" result="" is="" correct="" using="" induction:="" a0="1" a1="1" an="4an−2" +="" 1="" for="" n="" ≥="" 2="" (d)="" 4="" points="" solve="" the="" following="" recurrence:="" an="5an−2" −="" 4an−4="" for="" n="" ≥="" 4="" a0="0," a1="1," a2="1," a3="1" (e)="" 5="" points="" suppose="" we="" are="" given="" a="" rod="" of="" length="" n.="" we="" can="" cut="" rod="" into="" pieces="" in="" such="" a="" way="" that="" each="" piece="" length="" is="" a="" natural="" number="" of="" size="" at="" least="" 1.="" there="" are="" many="" ways="" to="" cut="" the="" rod.="" for="" example,="" if="" n="5," we="" could="" cut="" it="" into="" pieces="" of="" size="" 1,="" 2,="" 2="" or="" 4,="" 1="" etc.="" write="" a="" recursive="" definition="" for="" p="" (n,="" k)="" which="" is="" the="" number="" of="" ways="" to="" cut="" a="" rod="" of="" length="" n="" where="" the="" maximum="" size="" of="" the="" pieces="" is="" k.="" your="" definition="" 2="" is="" for="" n="" ≥="" 1="" and="" k="" ≥="" 1.="" you="" do="" not="" need="" to="" solve="" the="" recurrence.="" use="" your="" recurrence="" to="" solve="" for="" p="" (7,="" 7)="" and="" p="" (7,="" 2).="" (f)="" 5="" points="" a="" child="" is="" building="" a="" tower="" out="" of="" red,="" black,="" and="" green="" blocks.="" the="" red="" and="" black="" blocks="" have="" size="" 1="" and="" the="" green="" block="" has="" size="" 2.="" a="" tower="" of="" height="" n="" is="" built="" using="" a="" sequence="" of="" the="" colored="" blocks,="" with="" the="" condition="" that="" no="" red="" blocks="" are="" adjacent.="" write="" a="" recursive="" definition="" t="" (n),="" n="" ≥="" 1,="" for="" the="" number="" of="" possible="" towers="" of="" height="" n.="" you="" do="" not="" need="" to="" solve="" the="" recurrence.="" question="" 4:="" recursive="" procedures="" .="" (a)="" 6="" points="" recall="" that="" in="" week="" 6="" we="" considered="" the="" problem="" of="" distributing="" n="" identical="" items="" into="" k="" unlabelled="" groups.="" in="" this="" problem,="" you="" must="" write="" a="" recursive="" procedure="" called="" numberpartitions(n,="" k)="" that="" returns="" the="" number="" of="" ways="" of="" distributing="" n="" identical="" pennies="" into="" k="" piles,="" where="" each="" pile="" has="" at="" least="" 1="" penny.="" the="" piles="" are="" not="" labelled,="" so="" the="" only="" thing="" that="" matters="" is="" the="" number="" of="" coins="" in="" each="" pile.="" your="" procedure="" must="" function="" properly="" for="" n="" ≥="" 1="" and="" 1="" ≤="" k="" ≤="" n.="" use="" your="" procedure="" to="" verify="" the="" output="" for="" n="8" and="" k="4." (b)="" 6="" points="" consider="" a="" making="" a="" postage="" of="" n="" cents="" using="" stamps="" of="" size="" 2,="" 3="" and="" 4.="" suppose="" we="" must="" use="" at="" least="" one="" of="" each="" stamp="" denomination.="" write="" a="" recursive="" procedure="" called="" printpostage(n)="" that="" prints="" out="" a="" set="" of="" stamps="" that="" create="" a="" postage="" of="" size="" n.="" you="" must="" determine="" the="" correct="" base="" case="" and="" ensure="" that="" your="" recursive="" procedure="" handles="" that="" correctly.="" if="" no="" postage="" is="" possible,="" your="" procedure="" must="" print="" “no="" postage”.="" your="" procedure="" must="" handle="" all="" inputs="" of="" n="" ≥="" 0.="" for="" example:="" findpostage(25)="" outputs="" stamps="" 4,="" 4,="" 4,="" 4,="" 4,="" 3,="" 2.="" there="" are="" other="" options="" possible,="" but="" just="" one="" correct="" option="" must="" be="" printed.="" (c)="" 6="" points="" recall="" problem="" 4(c)="" from="" assignment="" 2.="" consider="" a="" new="" version="" of="" this="" problem="" where="" the="" bills="" have="" denominations="" 1,="" 5,="" 52,="" 53,="" .="" .="" ..="" as="" in="" the="" previous="" assignment,="" you="" owe="" your="" friend="" a="" debt="" of="" n="" dollars.="" you="" must="" transfer="" a="" set="" of="" bills="" between="" you="" and="" your="" friend="" in="" such="" a="" way="" that="" the="" debt="" is="" repaid.="" in="" this="" case,="" a="" bill="" denomination="" may="" be="" used="" at="" most="" two="" times.="" write="" a="" recursive="" procedure="" called="" printbills(n)="" that="" returns="" a="" list="" of="" the="" necessary="" bills,="" for="" n="" ≥="" 0.="" the="" list="" should="" include="" positive="" numbers="" for="" bills="" you="" give="" your="" friend,="" and="" negative="" numbers="" for="" bills="" your="" friend="" gives="" you.="" for="" example,="" if="" n="21," the="" output="" list="" should="" be="" [52,−5,="" 1].="" for="" n="32," the="" output="" list="" should="" be="" [25,="" 5,="" 1,="" 1].="" *note:="" this="" is="" not="" a="" course="" on="" data-structures.="" so="" you="" may="" assume="" that="" you="" can="" create="" an="" empty="" list="" with="" the="" pseudo-code="" “x="list()”" and="" use="" the="" following="" operations:="" -add="" elements="" to="" the="" list="" using="" x.add(25)="" -update/access="" element="" at="" index="" i="" using="" x[i]="" -determine="" the="" length="" using="" x.length().="">