Math 55: Discrete Mathematics

1 Math 55: Discrete MathematicsUC Berkeley, Spring 2012 Homework # 9, due Wednesday, April many ways are there to pay a bill of17pesos using a currencywith coins of values of1peso,2pesos,5pesos, and10pesos, and withbills with values of5pesos and10pesos?Letandenote the number of ways to pay a bill ofnpesos. Thenan= 0 forn <0, anda0= 1, and we have the recurrence relationan=an 1+an 2+ 2 an 5+ 2 an 10forn recurrence relation gives the following sequence:n1 2 3 45678an1 2 3 5 10 17 31 548 9 10 11 12 131415161754 95 171 302 539 955 1694 3011 5343 9494 Hence there are 9494 ways to pay a bill of 17 ) Find a recurrence relation for the number of bit strings of lengthnthat contain three ) What are initial conditions?

2 C) How many bit strings of length seven contain three consecutive0s?Letandenote the number of such strings of ) Consider a string of lengthn 3 that contains three consecutive0s. Such a string either ends with 1, or with 10, or with 100, orwith 000. In the first case, there arean 1possibilities. In thesecond case, there arean 2possibilities. In the third case, therearean 3possibilities. And, in the fourth case, there are 2n 3possibilities. Hence the recurrence relation isan=an 1+an 2+an 3+ 2n 3forn ) The initial conditions area0=a1=a2= 0. Note thata3= ) The recurrence gives the sequence of positive integers0,0,0,1,3,8,20,47,107,238,520,11 21,2391,..Hence there area7= 47 bit strings of length seven that containthree consecutive ) Find a recurrence relation for the number of ways to climbnstairs if the person climbing the stairs can take one stair or twostairs at a ) What are the initial conditions?

3 C) In how many ways can this person climb a flight of eight stairs?LetSndenote the number of ways of climbing the ) Letn 3. The last step either was a single step, for which thereareSn 1possibilities, or a double step, for which there areSn 2possibilities. The recurrence isSn=Sn 1+Sn 2forn ) We haveS1= 1 andS2= 2. You can take two stairs eitherdirectly or by taking stair at a ) The recurrence gives the Fibonacci sequence1,2,3,5,8,13,21,34,55,..Hence there areS8= 34 ways to climb a flight of eight bus driver pays all tolls, using only nickels and dimes, by throwingone coin at a time into the mechanical toll ) Find the recurrence relation for the number of different ways thebus driver can pay a toll ofncents (where the order in which thecoins are used matters).

4 B) In how many ways can the driver pay a toll of45cents?Letcndenote the number of ways of ) Consider the coin that was paid last. That coin either is a nickel,for which there arecn 5possibilities, or it is a dime, for whichthere arecn 10possibilities. Hence the recurrence relation iscn=cn 5+cn 10forn 11. Also, the initial conditions arec1=c2=c3=c4=c6=c7=c8=c9= 0,c5= 1, andc10= ) This recurrence generates the interspersed Fibonacci sequence0,0,0,0,1,0,0,0,0,2,0,0,0,0,3,0, 0,0,0,5,0,0,0,0,8,0,0,0,0,13,0,0,0,0,21, 0,0,0,0,34,0,0,0,0,55,..Hence there arec45= 55 ways for the bus driver to pay ) Write out all the ways the productx0 x1 x2 x3 x4can beparenthesized to determine the order of ) Use the recurrence relation developed in Example 5 to calculateCn, the number of ways to parenthesize the product of five num-bers.

5 Verify that you listed the correct number of ways in part (a).c) Check your result in part (b) by findingC4, using the closed for-mula forCnin the solution of Example ) There are 14 ways to parenthesize a product of five factors:(((x0 x1) x2) x3) x4,((x0 (x1 x2)) x3) x4,((x0 x1) (x2 x3)) x4,(x0 ((x1 x2) x3)) x4,(x0 (x1 (x2 x3))) x4,(x0 x1 x2) (x3 x4),(x0 x1 x2) (x3 x4),(x0 x1) ((x2 x3) x4),(x0 x1) (x2 (x3 x4)), x0 (((x1 x2) x3) x4),x0 ((x1 (x2 x3)) x4), x0 ((x1 x2) (x3 x4)),x0 (x1 ((x2 x3) x4)), x0 (x1 (x2 (x3 x4))).b) From the recurrence on page 507 we getC4=C0 C3+C1 C2+C2 C1+C3 C0= 1 5+1 2+2 1+5 1 = ) The closed formula for the Catalan numbers isCn=(2nn)/(n+1).

6 Substitutingn= 4, we confirmC4 (84)/5 = 70/5 = which of these are linear homogeneous recurrence relationswith constant coefficients. Also, find the degree of those that )an= 3an 2b)an= 3c)an=a2n 1d)an=an 1+an 3e)an=an 1/n3f )an=an 1+an 2+n+ 3g)an= 4an 2+ 5an 4+ 9an 7a) This is a linear homogeneous recurrence relation with constantcoefficients of degree ) This recurrence is not ) This recurrence is not ) This is a linear homogeneous recurrence relation with constantcoefficients of degree ) This recurrence does not have constant ) This recurrence is not ) This is a linear homogeneous recurrence relation with constantcoefficients of degree model for the number of lobsters caught per year is based on theassumption that the number of lobsters caught in a year is the averageof the number caught in the previous two ) Find a recurrence relation for{Ln}whereLnis the number oflobsters caught in yearn, under the assumption of this ) FindLnif100,000lobsters were caught in year1and200,000lobsters were caught in ) SinceLnis the average ofLn 1andLn 2, the recurrence isLn=12Ln 1+12Ln ) The characteristic polynomialx2 x/2 1/2 =12(2x+ 1)(x 1)has the roots 1 and 1/2.

7 Hence there exist real constantsc1andc2such thatLn= 1+ 2( 1/2)n. The initial conditions implythe linear relations 1+ 2= 100000 and 1 2/2 = 200000. Thesolution is 1= 500000/3 and 2= 200000/3, and we concludecn=5000003+200000 ( 1/2) second term converges to zero. Thus, the steady state sce-nario is that 166,667 lobsters will be caught every Lucas numbers satisfy the recurrence relationLn=Ln 1+Ln 2,and the initial conditionsL0= 2andL1= ) Show thatLn=fn 1+fn+1forn= 2,3,..,wherefnis thenthFibonacci ) Find an explicit formula for the Lucas ) We define a new sequence{Mn}by settingM0= 2 andMn=fn 1+fn+1forn 1. ThenM1=f0+f2= 1 andM2=f1+f3= 1 + 2 = 3. The two sequences{Mn}and{Ln}satisfythe same recurrence, and they satisfy the same initial they must be ) The roots of the characteristic polynomial are given by the goldenratio, and we findLn=(1 + 52)n+(1 52)nforn= 0,1,2,3.

8 The recurrence relationan= 6an 1 12an 2+ 8an 3witha0= 5,a1= 4anda2= characteristic polynomial equalsx3 6x2+ 12x 8 = (x 2)3. Weknow from Theorem 4 on page 519 thatan= 12n+ 2n2n+ 3n22nfor some constants 1, 2, 3. By substitutingn= 0,1,2 into thisequation, we obtain the linear system 1= 5,2 1+ 2 2+ 2 3= 4 and 4 1+ 8 2+ 16 3= solution is 1= 5 ,c2= 1/2,c3= 13/2, and thereforean= 5 2n+n 2n 1+ 13 n2 2n 1forn= 0,1,2,3,.. that there are two goats on an island initially. The numberof goats on the island doubles every year by natural reproduction, andsome goats are either added or removed each ) Construct a recurrence relation for number of goats on the islandat the start of thenth year, assuming that during each year anextra100goats are put on the ) Solve the recurrence relation from part (a) to find the number ofgoats on the island at the start of thenth ) Construct a recurrence relation for number of goats on the islandat the start of thenth year, assuming thatngoats are removedduring thenth year for eachn ) Solve the recurrence relation in part (c)

9 To find the number ofgoats on the island at the start of thenth ) LetGndenote the number of goats on the island at the start of thenth year. The recurrence isGn= 2Gn 1+ 100 forn= 1,2,..b) A particular solution to his inhomogenous linear recurrence is100 (2n 1). By Theorem 5 on page 521, the solution must havethe formGn= 100(2n 1) + 2n. SinceG0= 2, we see that = 2, and hence the number of goats equalsGn= 100(2n 1) + 2n+1forn= 0,1,2,3,..c) The recurrence isGn= 2Gn 1 nforn= 1,2,..,d) We observe that the recurrence gives the sequence 2,3,4,5,6,..Using mathematical induction, we easily prove that indeedGn=n+ 2 forn= 0,1,2,3,.. **Find a closed form for the generating function for the sequence{an}wherea)an= 1for alln= 0,1,2.

10 B)an= 2nforn= 1,2,3,4,..anda0= 0c)an=n 1forn= 0,1,2,..d)an= 1/(n+ 1)!for0,1,2,..e)an=(n2)forn= 0,1,2,..,f )an=(10n+1)forn= 0,1,2,..The following generating functions represent the desired sequences:a) 1/(x 1).b) 2x/(1 2x)6c) (2x 1)/(1 x)2d) (ex 1) )x2/(1 x)3f) ((x+ 1)10 1) each of these generating functions, provide a closed formula forthe sequence it )(x2+ 1)3b)(3x 1)3c)1/(1 2x2)d)x2/(1 x)3e)x 1 + (1/(1 3x))f )(1 +x3)/(1 +x)3g)x/(1 +x+x2)h)e3x2 1a)(3n/2)ifnis even, and 0 ifnis oddb) ( 3)n(3n)c) 2n/2ifnis even, and 0 ifnis oddd)(n3)e) 0 forn= 0, 4 forn= 1, and 3nforn ) 1 forn= 0, and ( 1)n 3nforn ) 0 ifn 0 (mod 3), 1 ifn 1 (mod 3), 1 ifn 2 (mod 3).