Mathematics for Computer Science lecture notes

free lecture notes mathematics for computer science by lehman and leighton and discrete mathematics for computer science lecture notes pdf fee download
Dr.JamesSmith Profile Pic
Dr.JamesSmith,France,Professional
Published Date:11-07-2017
Your Website URL(Optional)
Comment
MathematicsforComputerScience EricLehmanandTomLeighton 20042Contents 1 WhatisaProof? 15 1.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3 LogicalDeductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.4 ExamplesofProofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.4.1 ATautology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.4.2 AProofbyContradiction . . . . . . . . . . . . . . . . . . . . . . . . . 22 2 InductionI 23 2.1 AWarmupPuzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 UsingInduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4 ADivisibilityTheorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.5 AFaultyInductionProof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.6 CourtyardTiling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.7 AnotherFaultyProof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3 InductionII 35 3.1 GoodProofsandBadProofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 APuzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3 Unstacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3.1 StrongInduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3.2 AnalyzingtheGame . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 34 CONTENTS 4 NumberTheoryI 45 4.1 ATheoryoftheIntegers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.2 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.2.1 Turing’sCode(Version1.0) . . . . . . . . . . . . . . . . . . . . . . . . 47 4.2.2 TheDivisionAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.2.3 BreakingTuring’sCode . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.3 ModularArithmetic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.3.1 CongruenceandRemainders . . . . . . . . . . . . . . . . . . . . . . . 51 4.3.2 Factsaboutremandmod . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3.3 Turing’sCode(Version2.0) . . . . . . . . . . . . . . . . . . . . . . . . 54 4.3.4 CancellationModuloaPrime . . . . . . . . . . . . . . . . . . . . . . . 55 4.3.5 MultiplicativeInverses . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.3.6 Fermat’sTheorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.3.7 FindingInverseswithFermat’sTheorem . . . . . . . . . . . . . . . . 58 4.3.8 BreakingTuring’sCode—Again . . . . . . . . . . . . . . . . . . . . . 58 5 NumberTheoryII 61 5.1 DieHard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5.1.1 DeathbyInduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.1.2 AGeneralTheorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.1.3 TheGreatestCommonDivisor . . . . . . . . . . . . . . . . . . . . . . 64 5.1.4 PropertiesoftheGreatestCommonDivisor . . . . . . . . . . . . . . . 65 5.2 TheFundamentalTheoremofArithemtic . . . . . . . . . . . . . . . . . . . . 67 5.3 ArithmeticwithanArbitraryModulus . . . . . . . . . . . . . . . . . . . . . . 68 5.3.1 RelativePrimalityandPhi . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.3.2 GeneralizingtoanArbitraryModulus . . . . . . . . . . . . . . . . . . 70 5.3.3 Euler’sTheorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6 GraphTheory 73 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 6.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.1.2 SexinAmerica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74CONTENTS 5 6.1.3 GraphVariations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.1.4 ApplicationsofGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.1.5 SomeCommonGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.1.6 Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.2 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.2.1 ASimpleConnectivityTheorem . . . . . . . . . . . . . . . . . . . . . 80 6.2.2 DistanceandDiameter . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.2.3 Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.3 AdjacencyMatrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.4.1 SpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.4.2 TreeVariations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7 GraphTheoryII 89 7.1 ColoringGraphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 7.1.1 k-Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.1.2 BipartiteGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.2 PlanarGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 7.2.1 Euler’sFormula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 7.2.2 ClassifyingPolyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 7.3 Hall’sMarriageTheorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.3.1 AFormalStatement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 8 CommunicationNetworks 99 8.1 CompleteBinaryTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 8.1.1 LatencyandDiameter . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 8.1.2 SwitchSize . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 8.1.3 SwitchCount . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 8.1.4 Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 8.2 2-DArray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 8.3 Butterfly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 8.4 Benes˘ Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1066 CONTENTS 9 Relations 111 9.0.1 RelationsonOneSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 9.0.2 RelationsandDirectedGraphs . . . . . . . . . . . . . . . . . . . . . . 112 9.1 PropertiesofRelations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 9.2 EquivalenceRelations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 9.2.1 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 9.3 PartialOrders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 9.3.1 DirectedAcyclicGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . 116 9.3.2 PartialOrdersandTotalOrders . . . . . . . . . . . . . . . . . . . . . . 116 10 Sums,Approximations,andAsymptotics 119 10.1 TheValueofanAnnuity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 10.1.1 TheFutureValueofMoney . . . . . . . . . . . . . . . . . . . . . . . . 119 10.1.2 AGeometricSum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 10.1.3 ReturnoftheAnnuityProblem . . . . . . . . . . . . . . . . . . . . . . 121 10.1.4 InfiniteSums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 10.2 VariantsofGeometricSums . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 10.3 SumsofPowers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 10.4 ApproximatingSums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 10.4.1 IntegrationBounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 10.4.2 Taylor’sTheorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 10.4.3 BacktotheSum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 10.4.4 AnotherIntegrationExample . . . . . . . . . . . . . . . . . . . . . . . 131 11 Sums,Approximations,andAsymptoticsII 133 11.1 BlockStacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 11.1.1 HarmonicNumbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 11.2 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 11.3 AsymptoticNotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138CONTENTS 7 12 RecurrencesI 143 12.1 TheTowersofHanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 12.1.1 FindingaRecurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 12.1.2 ALowerBoundforTowersofHanoi . . . . . . . . . . . . . . . . . . . 145 12.1.3 Guess-and-Verify . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 12.1.4 ThePlug-and-ChugMethod . . . . . . . . . . . . . . . . . . . . . . . 147 12.2 MergeSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 12.2.1 TheAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 12.2.2 FindingaRecurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 12.2.3 SolvingtheRecurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 12.3 MoreRecurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 12.3.1 ASpeedyAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 12.3.2 AVerificationProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 12.3.3 AFalseProof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 12.3.4 AlteringtheNumberofSubproblems . . . . . . . . . . . . . . . . . . 155 12.4 TheAkra-BazziMethod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 12.4.1 SolvingDivideandConquerRecurrences . . . . . . . . . . . . . . . . 156 13 RecurrencesII 159 13.1 AsymptoticNotationandInduction . . . . . . . . . . . . . . . . . . . . . . . 159 13.2 LinearRecurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 13.2.1 GraduateStudentJobProspects . . . . . . . . . . . . . . . . . . . . . 160 13.2.2 FindingaRecurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 13.2.3 SolvingtheRecurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 13.2.4 JobProspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 13.3 GeneralLinearRecurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 13.3.1 AnExample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 13.4 InhomogeneousRecurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 13.4.1 AnExample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 13.4.2 HowtoGuessaParticularSolution . . . . . . . . . . . . . . . . . . . 1698 CONTENTS 14 CountingI 173 14.1 CountingOneThingbyCountingAnother . . . . . . . . . . . . . . . . . . . 174 14.1.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 14.1.2 Bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 14.1.3 TheBijectionRule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 14.1.4 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 14.2 TwoBasicCountingRules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 14.2.1 TheSumRule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 14.2.2 TheProductRule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 14.2.3 PuttingRulesTogether . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 14.3 MoreFunctions: InjectionsandSurjections . . . . . . . . . . . . . . . . . . . 181 14.3.1 ThePigeonholePrinciple . . . . . . . . . . . . . . . . . . . . . . . . . 182 15 CountingII 187 15.1 TheGeneralizedProductRule . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 15.1.1 DefectiveDollars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 15.1.2 AChessProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 15.1.3 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 15.2 TheDivisionRule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 15.2.1 AnotherChessProblem . . . . . . . . . . . . . . . . . . . . . . . . . . 191 15.2.2 KnightsoftheRoundTable . . . . . . . . . . . . . . . . . . . . . . . . 192 15.3 Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 15.3.1 UnionofTwoSets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 15.3.2 UnionofThreeSets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 15.3.3 UnionofnSets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 15.4 TheGrandSchemeforCounting . . . . . . . . . . . . . . . . . . . . . . . . . 197 16 CountingIII 201 16.1 TheBookkeeperRule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 16.1.1 20-MileWalks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 16.1.2 BitSequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 16.1.3 k-elementSubsetsofan n-elementSet . . . . . . . . . . . . . . . . . . 202CONTENTS 9 16.1.4 AnAlternativeDerivation . . . . . . . . . . . . . . . . . . . . . . . . . 203 16.1.5 WordofCaution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 16.2 BinomialTheorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 16.3 PokerHands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 16.3.1 HandswithaFour-of-a-Kind . . . . . . . . . . . . . . . . . . . . . . . 205 16.3.2 HandswithaFullHouse . . . . . . . . . . . . . . . . . . . . . . . . . 205 16.3.3 HandswithTwoPairs . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 16.3.4 HandswithEverySuit . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 16.4 MagicTrick. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 16.4.1 TheSecret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 16.4.2 TheRealSecret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 16.4.3 SameTrickwithFourCards? . . . . . . . . . . . . . . . . . . . . . . . 212 16.5 CombinatorialProof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 16.5.1 Boxing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 16.5.2 CombinatorialProof . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 17 GeneratingFunctions 217 17.1 GeneratingFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 17.2 OperationsonGeneratingFunctions . . . . . . . . . . . . . . . . . . . . . . . 218 17.2.1 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 17.2.2 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 17.2.3 RightShifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 17.2.4 Differentiation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 17.3 TheFibonacciSequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 17.3.1 FindingaGeneratingFunction . . . . . . . . . . . . . . . . . . . . . . 222 17.3.2 FindingaClosedForm . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 17.4 CountingwithGeneratingFunctions . . . . . . . . . . . . . . . . . . . . . . . 225 17.4.1 ChoosingDistinctItemsfromaSet . . . . . . . . . . . . . . . . . . . . 225 17.4.2 BuildingGeneratingFunctionsthatCount . . . . . . . . . . . . . . . 225 17.4.3 ChoosingItemswithRepetition . . . . . . . . . . . . . . . . . . . . . 227 17.5 An“Impossible”CountingProblem . . . . . . . . . . . . . . . . . . . . . . . 22910 CONTENTS 18 IntroductiontoProbability 231 18.1 MontyHall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 18.1.1 TheFour-StepMethod . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 18.1.2 ClarifyingtheProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 18.1.3 Step1: FindtheSampleSpace. . . . . . . . . . . . . . . . . . . . . . . 233 18.1.4 Step2: DefineEventsofInterest . . . . . . . . . . . . . . . . . . . . . 235 18.1.5 Step3: DetermineOutcomeProbabilities . . . . . . . . . . . . . . . . 236 18.1.6 Step4: ComputeEventProbabilities . . . . . . . . . . . . . . . . . . . 239 18.1.7 AnAlternativeInterpretationoftheMontyHallProblem . . . . . . . 240 18.2 StrangeDice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 18.2.1 AnalysisofStrangeDice . . . . . . . . . . . . . . . . . . . . . . . . . . 241 19 ConditionalProbability 245 19.1 TheHaltingProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 19.1.1 SolutiontotheHaltingProblem . . . . . . . . . . . . . . . . . . . . . 246 19.1.2 WhyTreeDiagramsWork . . . . . . . . . . . . . . . . . . . . . . . . . 248 19.2 APosterioriProbabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 19.2.1 ACoinProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 19.2.2 AVariantoftheTwoCoinsProblem . . . . . . . . . . . . . . . . . . . 252 19.3 MedicalTesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 19.4 ConditionalProbabilityPitfalls . . . . . . . . . . . . . . . . . . . . . . . . . . 256 19.4.1 CarnivalDice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 19.4.2 OtherIdentities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 19.4.3 DiscriminationLawsuit . . . . . . . . . . . . . . . . . . . . . . . . . . 258 19.4.4 On-TimeAirlines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 20 Independence 261 20.1 IndependentEvents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 20.1.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 20.1.2 WorkingwithIndependence . . . . . . . . . . . . . . . . . . . . . . . 262 20.1.3 SomeIntuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 20.1.4 AnExperimentwithTwoCoins . . . . . . . . . . . . . . . . . . . . . 263CONTENTS 11 20.1.5 AVariationoftheTwo-CoinExperiment . . . . . . . . . . . . . . . . 264 20.2 MutualIndependence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 20.2.1 DNATesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 20.2.2 PairwiseIndependence . . . . . . . . . . . . . . . . . . . . . . . . . . 268 20.3 TheBirthdayParadox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 20.3.1 TheFour-StepMethod . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 20.3.2 AnAlternativeApproach . . . . . . . . . . . . . . . . . . . . . . . . . 272 20.3.3 AnUpperBound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 20.3.4 ALowerBound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 20.3.5 TheBirthdayPrinciple . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 21 RandomVariables 277 21.1 RandomVariables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 21.1.1 IndicatorRandomVariables . . . . . . . . . . . . . . . . . . . . . . . . 278 21.1.2 RandomVariablesandEvents . . . . . . . . . . . . . . . . . . . . . . 278 21.1.3 ConditionalProbability . . . . . . . . . . . . . . . . . . . . . . . . . . 279 21.1.4 Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280 21.1.5 AnExamplewithDice . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 21.2 ProbabilityDistributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 21.2.1 BernoulliDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 21.2.2 UniformDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 21.2.3 TheNumbersGame . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 21.2.4 BinomialDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 21.2.5 ApproximatingtheCumulativeBinomialDistributionFunction . . . 290 21.3 PhilosophyofPolling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 22 ExpectedValueI 293 22.1 BettingonCoins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 22.2 EquivalentDefinitionsofExpectation . . . . . . . . . . . . . . . . . . . . . . 296 22.2.1 MeanTimetoFailure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 22.2.2 MakingaBabyGirl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 22.3 AnExpectationParadox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29812 CONTENTS 22.4 LinearityofExpectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 22.4.1 ExpectedValueofTwoDice . . . . . . . . . . . . . . . . . . . . . . . . 301 22.4.2 TheHat-CheckProblem . . . . . . . . . . . . . . . . . . . . . . . . . . 302 22.4.3 TheChineseAppetizerProblem . . . . . . . . . . . . . . . . . . . . . 303 23 ExpectedValueII 305 23.1 TheExpectedNumberofEventsthatHappen . . . . . . . . . . . . . . . . . . 305 23.1.1 ACoinProblem—theEasyWay . . . . . . . . . . . . . . . . . . . . . 306 23.1.2 TheHardWay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 23.2 TheCouponCollectorProblem . . . . . . . . . . . . . . . . . . . . . . . . . . 307 23.2.1 ASolutionUsingLinearityofExpectation . . . . . . . . . . . . . . . 307 23.3 ExpectedValueofaProduct . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 23.3.1 TheProductofTwoIndependentDice . . . . . . . . . . . . . . . . . . 309 23.3.2 TheProductofTwoDependentDice . . . . . . . . . . . . . . . . . . . 310 23.3.3 Corollaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 24 WeirdHappenings 315 24.1 TheNewGradingPolicy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 24.1.1 Markov’sInequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 24.1.2 LimitationsoftheMarkovInequality . . . . . . . . . . . . . . . . . . 317 24.2 TheTipoftheTail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 24.2.1 UpperBound: TheUnionBound . . . . . . . . . . . . . . . . . . . . . 318 24.2.2 LowerBound: “Murphy’sLaw” . . . . . . . . . . . . . . . . . . . . . 318 24.2.3 TheBigPicture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 24.3 ChernoffBounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 24.3.1 MITAdmissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 24.3.2 ProvingChernoffBounds . . . . . . . . . . . . . . . . . . . . . . . . . 322 24.4 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 24.4.1 TheFirstCollision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 24.4.2 N RecordsinN Bins . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 24.4.3 AllBinsFull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326CONTENTS 13 25 RandomWalks 327 25.1 ABug’sLife . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 25.1.1 ASimplerProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 25.1.2 ABigIsland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 25.1.3 LifeExpectancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 25.2 TheGambler’sRuin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 25.2.1 FindingaRecurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 25.2.2 SolvingtheRecurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 25.2.3 InterpretingtheSolution . . . . . . . . . . . . . . . . . . . . . . . . . . 337 25.2.4 SomeIntuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 25.3 PasstheBroccoli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33814 CONTENTSChapter1 WhatisaProof? Aproof isamethodofestablishingtruth. Thisisdoneinmanydifferentwaysineveryday life: Jurytrial. Truthisascertainedbytwelvepeopleselectedatrandom. WordofGod. TruthisascertainedbycommunicationwithGod,perhapsviaathirdparty. Experimentalscience. The truth is guessed and the hypothesis is confirmed or refuted byexperiments. Sampling. The truth is obtained by statistical analysis of many bits of evidence. For example,publicopinionisobtainedbypollingonlyarepresentativesample. Innerconviction. “Myprogramisperfect. Iknowthistobetrue.” “Idon‘tseewhynot...” Claim something is true and then shift the burden of proof to anyonewhodisagreeswithyou. Intimidation. Truthisassertedbysomeonewithwhomdisagrementseemsunwise. Mathematics its own notion of “proof”. In mathematics, a proof is a verification of a proposition by a chain of logical deductions from a base set of axioms. Each of the threehighlightedtermsinthisdefinitionisdiscussedinasectionbelow. Thelastsection containssomecompleteexamplesofproofs. 1.1 Propositions Apropositionisastatementthatiseithertrueorfalse. Thisdefinitionsoundsverygeneral and is a little vague, but it does exclude sentences such as, “What’s a surjection, again?” and“Learnlogarithms” Herearesomeexamplesofpropositions.16 WhatisaProof? Proposition1. 2+3=5 Thispropositionhappenstobetrue. 2 Proposition2.∀n∈N n +n+41isaprimenumber. Thispropositionismorecomplicated. Thesymbol∀isread“forall”,andthesymbolN stands for the set of natural numbers,0,1,2,3,.... (There is some disagreement about whether 0 is a natural number; in this course, it is.) So this proposition asserts that the final phrase is true for all natural numbersn. That phrase is actually a proposition in its ownright: 2 “n +n+41isaprimenumber” In fact, this is a special kind of proposition called a predicate, which is a proposition whose truth depends on the value of one or more variables. This predicate is certainly trueformanynaturalnumbersn: 2 n n +n+41 primeorcomposite? 0 41 prime 1 43 prime 2 47 prime 3 53 prime ... ... (allprime) 20 461 prime 39 1601 prime Experimental data like this can be useful in mathematics, but can also be misleading. 2 2 Inthiscase,whenn = 40,wegetn +n+41 = 40 +40+41 = 41· 41,whichisnotprime. SoProposition2isactuallyfalse 4 4 4 4 + Proposition3. a +b +c =d hasnosolutionwhena,b,c,d∈N . + HereN denotes the positive natural numbers,1,2,3,.... In 1769, Euler conjectured thatthispropositionwastrue. Buttheitwasprovenfalse218yearslaterbyNoamElkies at the liberal arts school up Mass Ave. He found the solutiona = 95800,b = 217519,c = 414560,d = 422481. Wecouldwritehisassertionsymbolicallyasfollows: + 4 4 4 4 ∃a,b,c,d∈N a +b +c =d The∃ symbol is read “there exists”. So, in words, the expression above says that there 4 4 4 4 existpositivenaturalnumbersa,b,c,anddsuchthata +b +c =d . 3 3 3 + Proposition4. 313(x +y ) =z hasnosolutionwhenx,y,z∈N .WhatisaProof? 17 This proposition is also false, but the smallest counterexample has more than 1000 digits. This counterexample could never have been found by a brute-force computer search The symbols∀ (“for all”) and∃ (“there exists”) are called quantifiers. A quantifier is always followed by a variable (and perhaps an indication of what values that variable can take on) and then a predicate that typically involves that variable. The predicate may itself involve more quantifiers. Here are a couple examples of statements involving quantifiers: 2 ∃x∈R x − x+1 = 0 + z ∀y∈R ∃z∈R e =y 2 The first statement asserts that the equation x − x + 1 = 0 has a real solution, which is z false. Thesecondstatementsaysthatasz rangesovertherealnumbers,e takesonevery positive,realvalueatleastonce. Proposition 5. In every map, the regions can be colored with 4 colors so that adjacent regions havedifferentcolors. ThispropositionwasconjecturedbyGuthriein1853. Thepropositionwas“proved”in 1879 by Kempe. His argument relied on pictures and— as is often the case with picture- proofs— contained a subtle error, which Heawood found 11 years later. In 1977 Appel and Haken announced a proof that relied on a computer to check an enormous number ofcases. However,manymathematiciansremainedunsatisfiedbecausenohumancould hand-check the computer’s work and also because of doubts about other parts of the argument. In1996,Robertson,Sanders,Seymour,andThomasproducedarigorousproof that still relied on computers. Purported proofs of the Four Color Theorem continue to streamin. Forexample,I.Cahitunveiledhis12-pagesolutioninAugust2004,buthereis his proof of Lemma 4: “Details of this lemma is left to the reader (see Fig. 7).” Don’t try that on your homework Even if this one doesn’t hold up, some day a simple argument maybefound. Proposition6. Everyevenintegergreaterthan2isthesumoftwoprimes. For example, 24 = 11 + 13 and 26 = 13 + 13. This is called the Goldbach Conjecture, after Christian Goldbach who first stated the proposition in 1742. Even today, no one knowswhethertheconjectureistrueorfalse. Everyintegerevercheckedisasumoftwo primes,butjustoneexceptionwoulddisprovetheproposition. 2 Proposition7.∀n∈Z (n≥ 2)⇒ (n ≥ 4) The symbol Z denotes the set of integers,...,− 2,− 1,0,1,2,.... There is predicate nestedinsidethisproposition: 2 (n≥ 2)⇒ (n ≥ 4)18 WhatisaProof? Thisisanexampleofanimplication,apropositionoftheformP⇒Q. Thisexpressionis read“P impliesQ”or“ifP,thenQ”. Thepropositioncorrectlyassertsthatthisparticular implication is true for every integern. In general, the implicationP⇒ Q is true whenP is falseorQistrue. Anotherwayofsayinghowimplicationworksiswithatruthtable: P Q P⇒Q T T T T F F F T T F F T In general, a truth table indicates whether a compound proposition is true or false for everypossibletruthsettingoftheconstituentpropositions. Thesecondlineofthistable, forexample,saysthattheimplicationP⇒QisfalsewhenP istrueandQisfalse. Justnowweusedvariables(P andQ)todenotearbitrarypropositions. We’lloftenuse suchBooleanvariablesinplaceofspecificpropositions. Thesearevariablesthatcantake ononlytwopossiblevalues,trueorfalse,justasthepropositionstheyrepresentcouldbe eithertrueorfalse. Hereanotherexampleofanimplication: “Ifpigsfly,thenyouwillunderstandtheChernoffBound.” This is no insult It’s a true proposition, even if you’re planning to sleep like a baby through the entire Chernoff Bound lecture. The reason is that the first part of the impli- cation (“pigs fly”) is false. And the last two lines of the truth table say that P ⇒ Q is always true whenP is false. This might not be the way you interpret if-then statements in everydayspeech,butit’stheacceptedconventioninmathematicaldiscussions. 2 Proposition8.∀n∈Z (n≥ 2)⇔ (n ≥ 4) ApropositionoftheformP⇔Qisread“P ifandonlyifQ”. (Sometimes“ifandonly if” is abbreviated “iff”.) This proposition is true provided P and Q are both true or both false. Putanotherway,P⇔ QistrueprovidedP⇒ Q andQ⇒ P are both true. Hereisa truthtablethatcomparesallthesekindsofimplication: P Q P⇒Q Q⇒P P⇔Q T T T T T T F F T F F T T F F F F T T T 2 The predicate (n≥ 2)⇔ (n ≥ 4) is true when n = 1 (because both sides are false) and truewhenn = 3(becausebothsidesaretrue)butfalsewhenn =− 3(becausetheleftside isfalse,buttherightsideistrue). Therefore,Proposition8asawholeisfalse.WhatisaProof? 19 1.2 Axioms An axiom is a proposition that is assumed to be true, because you believe it is somehow reasonable. Herearesomeexamples: Axiom1. Ifa =bandb =c,thena =c. Thisseemsveryreasonable But,ofcourse,thereisroomfordisagreementaboutwhat consitutesareasonableaxiom. Forexample,oneofEuclid’saxiomsforgeometryisequiv- alenttothefollowing: Axiom 2 (Parallel Postulate). Given a line l and a point p not on l, there is exactly one line throughpparalleltol. Inthe1800’sseveralmathematiciansrealizedthattheParallelPostulatecouldbereplaced withacouplealternatives. Thisaxiomleadsto“sphericalgeometry”: Axiom3. Givenalinel andapointpnotonl,thereisnolinethroughpparalleltol. Andthisaxiomgenerates“hyperbolicgeometry”. Axiom4. Givenalinelandapointpnotonl,thereareinfinitelymanylinesthroughpparallel tol. Arguably, no one of these axioms is really better than the other two. Of course, a different choice of axioms makes different propositions true. And axioms should not be chosen carelessly. In particular, there are two basic properties that one wants in a set of axioms: theyshouldbeconsistentandcomplete. Asetofaxiomsisconsistent ifnopropositioncanbeprovedbothtrueandfalse. This isanabsolutemust. Onewouldnotwanttospendyearsprovingapropositiontrueonly to have it proved false the next day Proofs would become meaningless if axioms were inconsistent. Asetofaxiomsiscompleteifeverypropositioncanbeprovedordisproved. Complete- ness is very desirable; we would like to believe that any proposition could be proved or disprovedwithsufficientworkandinsight. Surprisingly,makingacomplete,consistentsetofaxiomsisnoteasy. BertrandRussell andAlfredWhiteheadtriedduringtheirentirecareerstofindsuchaxiomsforbasicarith- meticandfailed. ThenKurtGodel ¨ provedthatnofinitesetofaxiomsforarithmeticcanbe bothconsistentandcomplete Thismeansthatanysetofconsistentaxiomsisnecessarily incomplete;therewillbetruestatementsthatcannotbeproved. Forexample,itmightbe thatGoldbach’sconjectureistrue,butthereisnoproof In this class, we will not dwell too much on the precise set of axioms underpinning our proofs. Generally, we’ll regard familiar facts from high school as axioms. You may20 WhatisaProof? find this imprecision regarding the axioms troublesome at times. For example, in the midst of a proof, you may find yourself wondering, “Must I prove this little fact or can I assumeit?” Unfortunately,thereisnoabsoluteanswer. Justbeupfrontaboutwhatyou’re assuming,anddon’ttrytoevadehomeworkandexamproblemsbydeclaringeverything anaxiom 1.3 LogicalDeductions Logicaldeductionsorinferencerulesareusedtocombineaxiomsandtruepropositionsin ordertoformmoretruepropositions. One fundamental inference rule is modus ponens. This rule says that if P is true and P ⇒ Q is true, then Q is also true. Inference rules are sometimes written in a funny notation. Forexample,modusponensiswritten: P P⇒Q Q Thissaysthatifyouknowthatthestatementsabovethelinearetrue,thenyoucaninfer thatthestatementbelowthelineisalsotrue. Modusponensiscloselyrelatedtotheproposition (P∧(P⇒ Q))⇒ Q. Bothinsome sense say, “if P and P ⇒ Q are true, then Q is true”. This proposition is an example of a tautology, because it is true for every setting of P and Q. The difference is that this tautology is a single proposition, whereas modus ponens is an inference rule that allows us to deduce new propositions from old ones. However, if we accept modus ponens, then a generaltheoremoflogicsaysthatforeachtautologicalimplicationthereisanassociated inference rule. For example, ((P⇒ Q)∧(Q⇒ R))⇒ (P⇒ R) and ((P⇒ Q)∧¬Q)⇒ ¬P are both tautologies, as one can verify with truth tables, and here are the analogous inferencerules: P⇒Q P⇒Q Q⇒R ¬Q P⇒R ¬P Aswithaxioms,wewon’tsayexactlywhatinferencerulesarelegalinthisclass. Each step in a proof should be clear and “logical”; in particular, you should make clear what previouslyprovedfactsareusedtoderiveeachnewconclusion. 1.4 ExamplesofProofs Let’sputtheseideastogetherandmakesomecompleteproofs.

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.