Math 55: Discrete Mathematics

1 Math 55: Discrete MathematicsUC Berkeley, Fall 2011 Homework # 5, due Wednesday, February (n)be the statement that13+ 23+ +n3= (n(n+ 1)/2)2forthe positive ) What is the statementP(1)?b) Show thatP(1)is ) What is the induction hypothesis?d) What do you need to prove in the inductive step?e) Complete the inductive ) Explain why these steps show that this formula is true for allpositive )P(1) is the statement 13= ((1(1 + 1)/2) ) This is true because both sides of the equation evaluate to ) The induction hypothesis is the statementP(k) for some positiveintegerk, that is, the statement 13+ 23+ +k3= (k(k+ 1)/2) ) Assuming thatP(k) holds, we need to show thatP(k+ 1) holds,that is, we need to derive the equation 13+23+ +k3+(k+1)3=((k+ 1)(k+ 2)/2)2from the equation in (c).

2 E) We add (k+ 1)3to both the left hand side and the right handside of the equation in (c). This shows that the left hand sidein (d) is equal to (k(k+ 1)/2)2+ (k+ 1)3. By expanding andfactoring, we find that this expression equals ((k+ 1)(k+ 2)/2) we have shown that the left hand side of the equation in(d) equals the right hand side of the equation in (d).f) We have carried out both the basis step and the inductive principle of mathematical induction now ensures thatP(n)is true for all positive that1 1! + 2 2! + +n n! = (n+ 1)! 1whenevernis apositive use mathematical induction. In fhe basis step, forn= 1, theequation states that 1 1! = (1 + 1)! 1, and this is true because bothsides of the equation evaluate to 1.

3 For the inductive step, we assumethat 1 1! + 2 2! + +k k! = (k+ 1)! 1 for some positive integerk. We add (k+ 1)(k+ 1)! to the left hand side to find that1 1! + 2 2! + + (k+ 1) (k+ 1)! = (k+ 1)! 1 + (k+ 1)(k+ 1)!The right hand side equals (k+ 1)!(k+ 2) 1 = (k+ 2)! 1. Thisestablishes the desired equation also fork+ 1, and we are done by theprinciple of mathematical ) Find a formula for11 2+12 3+ +1n(n+ 1)by examining the values of this expression for small values ) Prove the formula you conjectured in part (a).(a) By evaluating the sum forn= 1,2,3,4,5, .., we are led to conjec-ture that the following equation holds for all positive integersn:11 2+12 3+ +1n(n+ 1)=nn+ 1.(1)(b) We use mathematical induction. The basis step isn= 1.

4 Hereboth sides of the equation are equal to 1/2, so the claim the inductive step, we assume that (1) is true forn=k. Weadd1(k+1)(k+2)to both sides of this equation. Then the right handside becomeskk+ 1+1(k+ 1)(k+ 2)=k(k+ 2) + 1(k+ 1)(k+ 2)=k+ 1k+ the left hand side of (1) forn=k+ 1 equals the right handside of (1) forn=k+ 1. This completes the proof by thatn!< nnfor all integersn 2, using the six suggested (n) be the propositional functionn!< ) The statementP(2) says that 2! = 2 is less than 22= ) This statement is true because 4 is larger than ) The inductive hypothesis states thatP(k) holds for some integerk ) We need to prove thatk!< kkimplies (k+ 1)!<(k+ 1)k+ ) Given thatk!< kkholds, easily seen inequalities imply(k+ 1)!

5 =k! (k+ 1)< kk(k+ 1)<(k+ 1)k (k+ 1) = (k+ 1)k+ ) We have carried out both the basis step and the inductive principle of mathematical induction now ensures thatP(n)is true for all integersn that3dividesn3+ 2nwhenevernis a positive use mathematical induction. Forn= 1, the assertion says that 3divides 13+ 2 1, which is indeed the case, so the basis step is fine. Forthe inductive step, we assume that 3 dividesk3+ 2kfor some positiveintegerk. Hence there exists an integerlsuch that 3l=k3+ 2k. Acomputation shows(k+ 1)3+ 2(k+ 1) = (k3+ 2k) + 3(k2+k+ 1).The right hand is divisible by 3. This is evident for the second sum-mand, and it is the induction hypothesis for the first summand. Hencewe have proved that 3 divides (k+ 1)3+ 2(k+ 1).

6 This complete theinductive step, and hence the assertion mathematical induction to show that given a set ofn+ 1positiveintegers, none exceeding2n, there is at least one integer in this setthat divides another integer in the (n) be the following propositional function: given a set ofn+ 1positive integers, none exceeding 2n, there is at least one integer inthis set that divides another integer in the set. The propositionP(1)is true because there is only one set of 1 + 1 positive integers noneexceeding 2 1. This set is{1,2}and it contains an integer, namely 1,that divides the other integer, namely 2. This verifies the basis stepin our proof by mathematical the inductive step we assume thatP(k) is true for some positiveintegerk.

7 To proveP(k+ 1), we consider a setSofk+ 2 positive3integers none exceeding 2k+ 2. IfS {2k+ 1,2k+ 2}has cardinality0 or 1 then we apply the induction hypothesis toS\{2k+ 1,2k+ 2}to conclude that this set contains a dividing pair of we are left with the case that 2k+ 1 and 2k+ 2 are both inSandS\{2k+ 1,2k+ 2}consists ofkpositive integers of size at most2kthat pairwise don t divide each other. Ifk+ 1 is inSthen we aredone becausek+ 1 divides 2k+ 2. Suppose therefore thatk+ 16 we replaceSby the setS = (S\{2k+ 2}) {k+ 1}. The newsetS is covered by the previous case, so it contains a divisible pair. Ifthat pair does not involvek+ 1 then it is also inS. If it involvesk+ 1then this means that somel S\{k+ 1}dividesl. Thatlmust alsodivide 2k+ 2 and henceScontains a divisible pair.

8 This completesthe inductive step and hence the (n)be the statement that a postage ofncents can be formedusing just4-cent stamps and7-cent stamps. Prove thatP(n)is trueforn 18, using the six suggested prove this using strong induction. The basis step is to check thatP(18),P(19),P(20) andP(21) hold. This seen from the identities18 = 4 + 7 + 7,19 = 4 + 4 + 4 + 7,20 = 4 + 4 + 4 + 4 + 4,21 = 7 + 7 + the inductive step, we assume thatP(j) holds for all integersjwith 18 j kwherek 21. To realizek+ 1 cents, we first realizek 3 cents using 4-cent stamps and 7-cent stamps. This is possible bythe inductive hypothesis, sincek 3 18. Now add one more 4-centstamp to realizek+ 1 cents. This completes the induction step and ithence proves the that a chocolate bar consists ofnsquares arranged in a rect-angular pattern.

9 The entire bar, or a smaller rectangular piece of thebar, can be broken along a vertical or a horizontal line separating thesquares. Assuming that only one piece can be broken at a time, de-termine how many breaks you must successively make to break the barintonseparate squares use strong induction to prove your claim that the number of needed breaks isn 1. We shall provethis for all positive integersnusing strong induction. The basis stepn= 1 is clear. In that case we don t need to break the chocolateat all, we can just eat it. Suppose now thatn 2 and assume theassertion is true for all rectangular chocolate bars with fewer thann4squares. Then we break the chocolate into two pieces of sizemandn mwhere 1 m < n.

10 By the induction hypotheses, the barwithmpieces requiresm 1 breaks and the bar withn msquaresrequiresn m 1 breaks. Thus the original cholocate bar requires1 + (m 1) + (n m 1) breaks. This number equalsn 1, as thatP(n)is a propositional function. Determine for whichnonnegative integersnthe statementP(n)must be true ifa)P(0)is true; for all nonnegative integersn, ifP(n)is true thenP(n+ 2)is )P(0)is true; for all nonnegative integersn, ifP(n)is true thenP(n+ 3)is )P(0)andP(1)are true; for all non-negative integersn, ifP(n)andP(n+ 1)are true thenP(n+ 2)is )P(0)is true; for all non-negative integersn, ifP(n)is true thenP(n+ 2)andP(n+ 3)are ) The statementP(n) is true for all nonnegative integersnthatare ) The statementP(n) is true for all nonnegative integersnthatare divisible by ) The statementP(n) is true for all nonnegative ) The statementP(n) is true for all nonnegative integersnwithn6= 1, since every suchnis expressible as a sum of 2 s and 3 (2),f(3),f(4), andf(5)iffis defined recursively byf(0) =f(1) = 1and forn= 1,2.