Handbook of Mathematical Induction

THEORY What Is Mathematical Induction? Introduction An informal introduction to mathematical induction Ingredients of a proof by mathematical induction Two other ways to think of mathematical induction A simple example: dice Gauss and sums A variety of applications History of mathematical induction Mathematical induction in modern literature Foundations Notation Axioms Peano's axioms Principle of mathematical induction Properties of natural numbers Well-ordered sets Well-founded sets Variants of Finite Mathematical Induction The first principle Strong mathematical induction Downward induction Alternative forms of mathematical induction Double induction Fermat's method of infinite descent Structural induction Inductive Techniques Applied to the Infinite More on well-ordered sets Transfinite induction Cardinals Ordinals Axiom of choice and its equivalent forms Paradoxes and Sophisms from Induction Trouble with the language? Fuzzy definitions Missed a case? More deceit? Empirical Induction Introduction Guess the pattern? A pattern in primes? A sequence of integers? Sequences with only primes? Divisibility Never a square? Goldbach's conjecture Cutting the cake Sums of hex numbers Factoring xn ae' 1 Goodstein sequences How to Prove by Induction Tips on proving by induction Proving more can be easier Proving limits by induction Which kind of induction is preferable? The Written MI Proof A template Improving the flow Using notation and abbreviations APPLICATIONS AND EXERCISES Identities Arithmetic progressions Sums of finite geometric series and related series Power sums, sums of a single power Products and sums of products Sums or products of fractions Identities with binomial coefficients Gaussian coefficients Trigonometry identities Miscellaneous identities Inequalities Number Theory Primes Congruences Divisibility Numbers expressible as sums Egyptian fractions Farey fractions Continued fractions Sequences Difference sequences Fibonacci numbers Lucas numbers Harmonic numbers Catalan numbers Schroder numbers Eulerian numbers Euler numbers Stirling numbers of the second kind Sets Properties of sets Posets and lattices Topology Ultrafilters Logic and Language Sentential logic Equational logic Well-formed formulae Language Graphs Graph theory basics Trees and forests Minimum spanning trees Connectivity, walks Matchings Stable marriages Graph coloring Planar graphs Extremal graph theory Digraphs and tournaments Geometric graphs Recursion and Algorithms Recursively defined operations Recursively defined sets Recursively defined sequences Loop invariants and algorithms Data structures Complexity Games and Recreations Introduction to game theory Tree games Tiling with dominoes and trominoes Dirty faces, cheating wives, muddy children, and colored hats Detecting a counterfeit coin More recreations Relations and Functions Binary relations Functions Calculus Polynomials Primitive recursive functions Ackermann's function Linear and Abstract Algebra Matrices and linear equations Groups and permutations Rings Fields Vector spaces Geometry Convexity Polygons Lines, planes, regions, and polyhedra Finite geometries Ramsey Theory The Ramsey arrow Basic Ramsey theorems Parameter words and combinatorial spaces Shelah bound High chromatic number and large girth Probability and Statistics Probability basics Basic probability exercises Branching processes The ballot problem and the hitting game Pascal's game Local lemma SOLUTIONS AND HINTS TO EXERCISES Foundations Empirical Induction Identities Inequalities Number Theory Sequences Sets Logic and Language Graphs Recursion and Algorithms Games and Recreation Relations and Functions Linear and Abstract Algebra Geometry Ramsey Theory Probability and Statistics APPENDICES ZFC Axiom System Inducing You to Laugh? The Greek Alphabet References Index