Putnam and Beyond

Cover......Page 1
Putnam and Beyond......Page 2
Title: Putnam and Beyond......Page 3
e-ISBN-13: 978-0-387-68445-1......Page 4
Dedication......Page 5
Contents......Page 6
Preface......Page 10
A Study Guide......Page 13
Euclid’s theorem......Page 15
Induction principle......Page 17
Fermat’s little theorem......Page 18
Induction principle (strong form).......Page 21
Pigeonhole principle......Page 25
1.4 Ordered Sets and Extremal Elements......Page 28
1.5 Invariants and Semi-Invariants......Page 33
2.1.1 Algebraic Identities......Page 39
2.1.2 x^2 ≥ 0......Page 42
2.1.3 The Cauchy–Schwarz Inequality......Page 46
The Cauchy–Schwarz inequality......Page 47
2.1.4 The Triangle Inequality......Page 50
The arithmetic mean–geometric mean inequality......Page 53
Sturm’s principle......Page 56
2.2.1 AWarmup......Page 59
2.2.2 Viète’s Relations......Page 61
2.2.3 The Derivative of a Polynomial......Page 66
Lucas’ theorem......Page 68
2.2.5 Irreducible Polynomials......Page 70
2.2.6 Chebyshev Polynomials......Page 72
Chebyshev’s theorem......Page 73
2.3.1 Operations with Matrices......Page 75
2.3.2 Determinants......Page 77
2.3.3 The Inverse of a Matrix......Page 83
2.3.4 Systems of Linear Equations......Page 87
2.3.5 Vector Spaces, Linear Combinations of Vectors, Bases......Page 91
2.3.6 Linear Transformations, Eigenvalues, Eigenvectors......Page 93
The spectral mapping theorem......Page 94
The Cayley–Hamilton Theorem......Page 97
The Perron–Frobenius Theorem......Page 98
2.4.1 Binary Operations......Page 101
2.4.2 Groups......Page 104
2.4.3 Rings......Page 109
3 Real Analysis......Page 111
3.1.1 Search for a Pattern......Page 112
3.1.2 Linear Recursive Sequences......Page 114
Cauchy’s definition......Page 118
The squeezing principle......Page 119
Cauchy’s criterion for convergence......Page 123
3.1.4 More About Limits of Sequences......Page 125
The Cesàro–Stolz Theorem......Page 128
The Heine–Borel Theorem......Page 130
3.1.5 Series......Page 131
3.1.6 Telescopic Series and Products......Page 134
3.2.1 Limits of Functions......Page 139
3.2.2 Continuous Functions......Page 142
Peano’s theorem......Page 143
3.2.3 The Intermediate Value Property......Page 145
3.2.4 Derivatives and Their Applications......Page 148
L’Hôpital’s rule......Page 151
3.2.5 The Mean Value Theorem......Page 152
The mean value theorem (Lagrange).......Page 153
Hölder’s inequality......Page 156
Jensen’s inequality......Page 160
3.2.7 Indefinite Integrals......Page 161
3.2.8 Definite Integrals......Page 164
The Leibniz formula......Page 165
3.2.9 Riemann Sums......Page 167
3.2.10 Inequalities for Integrals......Page 170
Hölder’s inequality......Page 171
Chebyshev’s inequality......Page 172
3.2.11 Taylor and Fourier Series......Page 173
Stirling’s formula......Page 176
3.3.1 Partial Derivatives and Their Applications......Page 181
Euler’s theorem......Page 182
The Lagrange multipliers theorem......Page 185
3.3.2 Multivariable Integrals......Page 188
Tonelli’s theorem......Page 191
Stokes’ Theorem......Page 193
The Gauss–Ostrogradsky (Divergence) Theorem......Page 194
Cauchy’s theorem......Page 196
3.4.1 Functional Equations......Page 199
3.4.2 Ordinary Differential Equations of the First Order......Page 205
3.4.3 Ordinary Differential Equations of Higher Order......Page 209
3.4.4 Problems Solved with Techniques of Differential Equations......Page 212
4.1.1 Vectors......Page 215
4.1.2 The Coordinate Geometry of Lines and Circles......Page 220
4.1.3 Conics and Other Curves in the Plane......Page 226
4.1.4 Coordinate Geometry in Three and More Dimensions......Page 233
4.1.5 Integrals in Geometry......Page 239
Crofton’s theorem......Page 240
4.1.6 Other Geometry Problems......Page 242
4.2.1 Trigonometric Identities......Page 245
4.2.2 Euler’s Formula......Page 249
4.2.3 Trigonometric Substitutions......Page 252
4.2.4 Telescopic Sums and Products in Trigonometry......Page 256
5.1.1 Some General Problems......Page 259
5.1.2 Fermat’s Infinite Descent Principle......Page 262
Beatty’s theorem......Page 264
5.2.1 Factorization and Divisibility......Page 267
Euclid’s theorem......Page 268
Polignac’s formula......Page 271
5.2.3 Modular Arithmetic......Page 272
5.2.4 Fermat’s Little Theorem......Page 274
Fermat’s little theorem......Page 275
Wilson’s theorem......Page 278
5.2.6 Euler’s Totient Function......Page 279
Euler’s theorem.......Page 280
The Chinese Remainder Theorem......Page 282
5.3.1 Linear Diophantine Equations......Page 284
5.3.2 The Equation of Pythagoras......Page 288
Lagrange’s theorem......Page 290
5.3.4 Other Diophantine Equations......Page 293
6.1.1 Set Theory and Combinatorics of Sets......Page 294
6.1.2 Permutations......Page 296
Alternative problem......Page 299
Euler’s theorem......Page 302
6.1.5 Ramsey Theory......Page 304
6.2.1 Combinatorial Identities......Page 307
6.2.2 Generating Functions......Page 311
6.2.3 Counting Strategies......Page 315
6.2.4 The Inclusion–Exclusion Principle......Page 321
6.3.1 Equally Likely Case......Page 323
6.3.2 Establishing Relations Among Probabilities......Page 327
6.3.3 Geometric Probabilities......Page 331
SOLUTIONS......Page 334
Methods of Proof......Page 335
Algebra......Page 370
Real Analysis......Page 470
Geometry and Trigonometry......Page 613
Number Theory......Page 683
Combinatorics and Probability......Page 736
Index of Notation......Page 800
Index......Page 804