... which is a surprisingly complete survey of most of your basic undergraduate math, done very well.
Contents
1 What is a Proof? 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 Induction I 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 Induction II 35
3.1 GoodProofsandBadProofs............................ 35
3.2 APuzzle....................................... 36
3.3 Unstacking...................................... 40
3.3.1 StrongInduction .............................. 40
3.3.2 AnalyzingtheGame ............................ 41
4 Number Theory I 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 Number Theory II 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 Graph Theory 73
6.1 Introduction..................................... 73
6.1.1 Definitions.................................. 74
6.1.2 SexinAmerica ............................... 74
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 Graph Theory II 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 Communication Networks 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 ...................................106
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, and Asymptotics 119
10.1 The Value of an Annuity.............................. 119
10.1.1 TheFutureValueofMoney........................119
10.1.2 AGeometricSum..............................120
10.1.3 ReturnoftheAnnuityProblem......................121
10.1.4 InfiniteSums................................122
10.2 Variants of Geometric Sums............................ 123
10.3 Sums of Powers................................... 125
10.4 Approximating Sums................................ 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, and Asymptotics II 133
11.1 Block Stacking.................................... 133
11.1.1 HarmonicNumbers............................135
11.2 Products.......................................137
11.3 Asymptotic Notation................................ 138
12 Recurrences I 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 Merge Sort...................................... 149
12.2.1 TheAlgorithm...............................149
12.2.2 FindingaRecurrence............................150
12.2.3 SolvingtheRecurrence...........................150
12.3 More Recurrences.................................. 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 Recurrences II 159
13.1 AsymptoticNotationandInduction .......................159
13.2LinearRecurrences .................................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.4InhomogeneousRecurrences ...........................167
13.4.1 AnExample.................................168
13.4.2 HowtoGuessaParticularSolution ...................169
14 Counting I 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 Two Basic Counting Rules............................. 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 Counting II 187
15.1 The Generalized Product Rule........................... 188
15.1.1 DefectiveDollars..............................189
15.1.2 AChessProblem..............................189
15.1.3 Permutations................................190
15.2 The Division Rule.................................. 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 Counting III 201
16.1 The Bookkeeper Rule................................ 201
16.1.1 20-MileWalks................................201
16.1.2 BitSequences................................202
16.1.3 k-elementSubsetsofann-elementSet..................202
16.1.4 AnAlternativeDerivation.........................203
16.1.5 WordofCaution ..............................203
16.2 BinomialTheorem .................................203
16.3 Poker Hands..................................... 204
16.3.1 Hands with a Four-of-a-Kind....................... 205
16.3.2 HandswithaFullHouse.........................205
16.3.3 HandswithTwoPairs...........................206
16.3.4 HandswithEverySuit...........................208
16.4 Magic Trick...................................... 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 Generating Functions 217
17.1 Generating Functions................................ 217
17.2 Operations on Generating Functions....................... 218
17.2.1 Scaling....................................218
17.2.2 Addition...................................219
17.2.3 Right Shifting................................ 220
17.2.4 Differentiation................................221
17.3 TheFibonacciSequence ..............................222
17.3.1 FindingaGeneratingFunction ......................222
17.3.2 FindingaClosedForm...........................224
17.4 Counting with Generating Functions....................... 225
17.4.1 ChoosingDistinctItemsfromaSet....................225
17.4.2 BuildingGeneratingFunctionsthatCount............... 225
17.4.3 ChoosingItemswithRepetition.....................227
17.5 An“Impossible”CountingProblem .......................229
18 Introduction to Probability 231
18.1 Monty Hall...................................... 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 An Alternative Interpretation of the Monty Hall Problem....... 240
18.2 Strange Dice..................................... 240
18.2.1 AnalysisofStrangeDice..........................241
19 Conditional Probability 245
19.1 TheHaltingProblem ................................246
19.1.1 SolutiontotheHaltingProblem .....................246
19.1.2 WhyTreeDiagramsWork.........................248
19.2APosterioriProbabilities ..............................250
19.2.1 ACoinProblem...............................251
19.2.2 AVariantoftheTwoCoinsProblem...................252
19.3MedicalTesting ...................................254
19.4ConditionalProbabilityPitfalls ..........................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 Independent Events................................. 261
20.1.1 Examples..................................261
20.1.2 WorkingwithIndependence.......................262
20.1.3 SomeIntuition...............................262
20.1.4 AnExperimentwithTwoCoins.....................263
20.1.5 AVariationoftheTwo-CoinExperiment................ 264
20.2 MutualIndependence...............................266
20.2.1 DNATesting................................267
20.2.2 PairwiseIndependence..........................268
20.3TheBirthdayParadox...............................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 Random Variables 277
21.1 Random Variables.................................. 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 Probability Distributions.............................. 282
21.2.1 BernoulliDistribution...........................284
21.2.2 UniformDistribution............................284
21.2.3 TheNumbersGame............................285
21.2.4 BinomialDistribution...........................287
21.2.5 Approximating the Cumulative Binomial Distribution Function... 290
21.3 Philosophy of Polling................................ 291
22 Expected Value I 293
22.1 Betting on Coins................................... 293
22.2 EquivalentDefinitionsofExpectation......................296
22.2.1 MeanTimetoFailure............................297
22.2.2 MakingaBabyGirl.............................298
22.3 AnExpectationParadox ..............................298
22.4 LinearityofExpectation ..............................300
22.4.1 ExpectedValueofTwoDice........................301
22.4.2 TheHat-CheckProblem..........................302
22.4.3 TheChineseAppetizerProblem .....................303
23 Expected Value II 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 Expected Value of a Product............................ 309
23.3.1 TheProductofTwoIndependentDice..................309
23.3.2 TheProductofTwoDependentDice...................310
23.3.3 Corollaries..................................310
24 Weird Happenings 315
24.1 The New Grading Policy.............................. 316
24.1.1 Markov’sInequality............................316
24.1.2 LimitationsoftheMarkovInequality..................317
24.2 The Tip of the Tail.................................. 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.4Hashing .......................................324
24.4.1 TheFirstCollision .............................325
24.4.2 NRecordsinNBins ............................325
24.4.3 AllBinsFull.................................326
25 Random Walks 327
25.1 ABug’sLife.....................................327
25.1.1 ASimplerProblem.............................328
25.1.2 ABigIsland.................................329
25.1.3 LifeExpectancy...............................332
25.2TheGambler’sRuin................................334
25.2.1 FindingaRecurrence............................335
25.2.2 SolvingtheRecurrence...........................335
25.2.3 InterpretingtheSolution..........................337
25.2.4 SomeIntuition...............................337
25.3 Pass the Broccoli................................... 338
Locked
