دانلود کتاب Handbook of Mathematical Induction: Theory and Applications

FeaturesPresents hundreds of classical theorems and proofs that span many areas, including basic equalities and inequalities, combinatorics, linear algebra, calculus, trigonometry, geometry, set theory, game theory, recursion, and algorithmsDerives many forms of mathematical induction, such as infinite descent and the axiom of choice, from basic principlesSupplies all necessary definitions and background, thereby requiring only a very modest amount of mathematical maturity to understand most results and proofsContains more than 750 exercises, with complete solutions to at least 500Includes nearly 600 bibliographic references, numerous cross references, and an extensive index of over 3,000 entriesHandbook of Mathematical Induction: Theory and Applications shows how to find and write proofs via mathematical induction. This comprehensive book covers the theory, the structure of the written proof, all standard exercises, and hundreds of application examples from nearly every area of mathematics.In the first part of the book, the author discusses different inductive techniques, including well-ordered sets, basic mathematical induction, strong induction, double induction, infinite descent, downward induction, and several variants. He then introduces ordinals and cardinals, transfinite induction, the axiom of choice, Zorn’s lemma, empirical induction, and fallacies and induction. He also explains how to write inductive proofs.The next part contains more than 750 exercises that highlight the levels of difficulty of an inductive proof, the variety of inductive techniques available, and the scope of results provable by mathematical induction. Each self-contained chapter in this section includes the necessary definitions, theory, and notation and covers a range of theorems and problems, from fundamental to very specialized.The final part presents either solutions or hints to the exercises. Slightly longer than what is found in most texts, these solutions provide complete details for every step of the problem-solving process.Bookmark MenuCoverHANDBOOK OF MATHEMATICAL INDUCTION: THEORY AND APPLICATIONSList of Publications of DISCRETE MATHEMATICS AND ITS APPLICATIONSCopyright © 2011 by Taylor and Frsncia Group, tLC ISBN 978-1-4200-9364-3 QA9.54.G86 2010 511.3'6--dc22Dedicated to Christine.ContentsForewordPreface The inception of this book Who is this book for? Structure of this book AcknowledgementsAbout the authorPart I Theory Chapter 1 What is mathematical induction? 1.1 Introduction 1.2 An informal introduction to mathematical induction 1.3 Ingredients of a proof by mathematical induction 1.4 Two other ways to think of mathematical induction 1.5 A simple example: Dice 1.6 Gauss and sums 1.7 A variety of applications 1.8 History of mathematical induction 1.9 Mathematical induction in modern literature Chapter 2 Foundations 2.1 Notation 2.2 Axioms 2.3 Peano's axioms 2.4 Principle of mathematical induction 2.5 properties of natural numbers 2.6 Well-ordered sets 2.7 Well-founded sets Chapter 3 Variants of finite mathematical induction 3.1 The first principle 3.2 Strong mathematical induction 3.3 Downward induction 3.4 Alternative forms of mathematical induction 3.5 Double induction 3.6 Fermat's method of infinite descent 3.7 Structural induction Chapter 4 Inductive techniques applied to the infinite 4.1 More on well-ordered sets 4.2 Transfinite induction 4.3 Cardinals 4.4 Ordinals 4.5 Axiom of choice and its equivalent forms Chapter 5 Paradoxes and sophisms from induction 5.1 Trouble with the language? 5.1.1 Richard's paradox 5.1.2 Paradox of the unexpected exam 5.2 Fuzzy definitions 5.2.1 No crowds allowed 5.2.2 Nobody is rich 5.2.3 Everyone is bald 5.3 Missed a case? 5.3.1 All is for naught 5.3.2 All horses are the same color 5.3.3 Non-parallel lines go through one point 5.4 More deceit? 5.4.1 A. new formula for triangular numbers 5.4.2 All positive integers are equal 5.4.3 Four weighings suffice Chapter 6 Empirical induction 6.1 Introduction 6.2 Guess the pattern? 6.3 A pattern in primes? 6.4 A sequence of integers? 6.5 Sequences with only primes? 6.6 Divisibility 6.7 Never a square? 6.8 Goldbach's conjecture 6.9 Cutting the cake 6.10 Sums of hex numbers 6.11 Factoring x^n - 1 6.12 Goodstein sequences Chapter 7 How to prove by induction 7.1 Tips on proving by induction 7.2 Proving more can be easier 7.3 Proving limits by induction 7.4 Which kind of induction is preferable? 7.4.1 When is induction needed? 7.4.2 Which kind of induction to use? Chapter 8 The written MI proof 8.1 A template 8.2 Improving the flow 8.2.1 Using other results in a proof 8.2.2 Clearly, it's trivial! 8.2.3 Pronouns 8.2.4 Footnotes 8.2.5 We, let's, our, will, now, must 8.3 Using notation and abbreviationsPart II Applications and exercises Chapter 9 Identities 9.1 Arithmetic progressions 9.2 Sums of finite geometric series and related series 9.3 Power sums, sums of a single power 9.4 Products and sums of products 9.5 Sums or products of fractions 9.6 Identities with binomial coefficients 9.6.1 Abel identities 9.6.2 Bernoulli numbers 9.6.3 Fauthaber's formula for power sums 9.7 Gaussian coefficients 9.8 Trigonometry identities 9.9 Miscellaneous identities Chapter 10 Inequalities Chapter 11 Number theory 11.1 Primes 11.2 Congruences 11.3 Divisibility 11.4 Numbers expressible as sums 11.5 Egyptian fractions 11.6 Farey fractions 11.7 Continued fractions 11.7.1 Finite continued fractions 11.7.2 Infinite continued fractions Chapter 12 Sequences 12.1 Difference sequences 12.2 Fibonacci numbers 12.3 Lucas numbers 12.4 Harmonic numbers 12.5 Catalan numbers 12.5.1 Introduction 12.5.2 Catalan numbers defined by a formula 12.5.3 Cn as a number of ways to compute a product 12.5.4 The definitions are equivalent 12.5.5 Some occurrences of Catalan numbers 12.6 Schröder numbers 12.7 Eulerian numbers 12.7.1 Ascents, descents, rises, falls 12.7.2 Definitions for Eulerian numbers 12.7.3 Eulerian number exercises 12.8 Euler numbers 12.9 Stirling numbers of the second kind Chapter 13 Sets 13.1 Properties of sets 13.2 Posets and lattices 13.3 Topology 13.4 Ultrafilters Chapter 14 Logic and language 14.1 Sentential logic 14.2 Equational logic 14.3 Well-formed formulae 14.4 Language Chapter 15 Graphs 15.1 Graph theory basics 15.2 Trees and forests 15.3 Minimum spanning trees 15.4 Connectivity, walks 15.5 Matchings 15.6 Stable marriages 15.7 Graph coloring 15.8 Planar graphs 15.9 Extremal graph theory 15.10 Digraphs and tournaments 15.11 Geometric graphs Chapter 16 Recursion and algorithms 16.1 Recursively defined operations 16.2 Recursively defined sets 16.3 Recursively defined sequences 16.3.1 Linear homogeneous recurrences of order 2 16.3.2 Method of characteristic roots 16.3.3 Applying the method of characteristic roots 16.3.4 Linear homogeneous recurrences of higher order 16.3.5 Non-homogeneous recurrences 16.3.6 Finding recurrences 16.3.7 Non-linear recurrence 16.3.8 Towers of Hanoi 16.4 Loop invariants and algorithms 16.5 Data structures 16.5.1 Gray codes 16.5.2 The hypercube 16.5.3 Red-black trees 16.6 Complexity 16.6.1 Landau notation 16.6.2 The master theorem 16.6.3 Closest pair of points Chapter 17 Games and recreations 17.1 Introduction to game theory 17.2 Tree games 17.2.1 Definitions and terminology 17.2.2 The game of NIM 17.2.3 Chess 17.3 Tiling with dominoes and trominoes 17.4 Dirty faces, cheating wives, muddy children, and colored hats 17.4.1 A parlor game with sooty fingers 17.4.2 Unfaithful wives 17.4.3 The muddy children puzzle 17.4.4 Colored hats 17.4.5 More related puzzles and references 17.5 Detecting a counterfeit coin 17.6 More recreations 17.6.1 Pennies in boxes 17.6.2 Josephus problem 17.6.3 The gossip problem 17.6.4 Cars on a circular track Chapter 18 Relations and functions 18.1 Binary relations 18.2 Functions 18.3 Calculus 18.3.1 Derivatives 18.3.2 Differential equations 18.3.3 Integration 18.4 Polynomials 18.5 Primitive recursive functions 18.6 Ackermann's function Chapter 19 Linear and abstract algebra 19.1 Matrices and linear equations 19.2 Groups and permutations 19.2.1 Semigroups and groups 19.2.2 Permutations 19.3 Rings 19.4 Fields 19.5 Vector spaces Chapter 20 Geometry 20.1 Convexity 20.2 Polygons 20.3 Lines, planes, regions, and polyhedra 20.4 Finite geometries Chapter 21 Ramsey theory 21.1 The Ramsey arrow 21.2 Basic Ramsey theorems 21.3 Parameter words and combinatorial spaces 21.4 Shelah bound 21.5 High chromatic number and large girth Chapter 22 Probability and statistics 22.1 Probability basics 22.1.1 Probability spaces 22.1.2 Independence and random variables 22.1.3 Expected value and conditional probability 22.1.4 Conditional expectation 22.2 Basic probability exercises 22.3 Branching processes 22.4 The ballot problem and the hitting game 22.5 Pascal's game 22.6 Local LemmaPart III Solutions and hints to exercises Chapter 23 Solutions: Foundations 23.1 Solutions: Properties of natural numbers 23.2 Solutions: Well-ordered sets 23.3 Solutions: Fermat's method of infinite descent Chapter 24 Solutions: Inductive techniques applied to the infinite 24.1 Solutions: More on well-ordered sets 24.2 Solutions: Axiom of choice and equivalent forms Chapter 25 Solutions: Paradoxes and sophisms 25.1 Solutions: Trouble with the language? 25.2 Solutions: Missed a case? 25.3 Solutions: More deceit? Chapter 26 Solutions: Empirical induction 26.1 Solutions: Introduction 26.2 Solutions: A sequence of integers? 26.3 Solutions: Sequences with only primes? 26.4 Solutions: Divisibility 26.5 Solutions: Never a square? 26.6 Solutions: Goldbach's conjecture 26.7 Solutions: Cutting the cake 26.8 Solutions: Sums of hex numbers Chapter 27 Solutions: Identities 27.1 Solutions: Arithmetic progressions 27.2 Solutions: Sums with binomial coefficients 27.3 Solutions: Trigonometry 27.4 Solutions: Miscellaneous identities Chapter 28 Solutions: Inequalities Chapter 29 Solutions: Number theory 29.1 Solutions: Primes 29.2 Solutions: Congruences 29.3 Solutions: Divisibility 29.4 Solutions: Expressible as sums 29.5 Solutions: Egyptian fractions 29.6 Solutions: Farey fractions 29.7 Solutions: Continued fractions Chapter 30 Solutions: Sequences 30.1 Solutions: Difference sequences 30.2 Solutions: Fibonacci number 30.3 Solutions: Lucas numbers 30.4 Solutions: Harmonic numbers 30.5 Solutions: Catalan numbers 30.6 Solutions: Eulerian numbers 30.7 Solutions: Euler numbers 30.8 Solutions: Stirling numbers Chapter 31 Solutions: Sets 31.1 Solutions: Properties of sets 31.2 Solutions: Posets and lattices 31.3 Solutions: Countable Zorn's lemma for measurable sets 31.4 Solutions: Topology 31.5 Solutions: Ultrafilters Chapter 32 Solutions: Logic and language 32.1 Solutions: Sentential logic 32.2 Solutions: Well-formed formulae Chapter 33 Solutions: Graphs 33.1 Solutions: Graph theory basics 33.2 Solutions: Trees and forests 33.3 Solutions: Connectivity, walks 33.4 Solutions: Matchings 33.5 Solutions: Stable matchings 33.6 Solutions: Graph coloring 33.7 Solutions: Planar graphs 33.8 Solutions: Extremal graph theory 33.9 Solutions: Digraphs and tournaments 33.10 Solutions: Geometric graphs Chapter 34 Solutions: Recursion andalgorithms 34.1 Solutions: Recursively defined sets 34.2 Solutions: Recursively defined sequences 34.2.1 Solutions: Linear homogeneous recurrences of order 2 34.2.2 Solutions: Applying the method of characteristic roots 34.2.3 Solutions: Linear homogeneous recurrences of higher order 34.2.4 Solutions: Non-homogeneous recurrences 34.2.5 Solutions: Non-linear recurrences 34.2.6 Solutions: Towers of Hanoi 34.3 Solutions: Data structures 34.4 Solutions: Complexity Chapter 35 Solutions: Games and recreation 35.1 Solutions: Tree games 35.1.1 Solutions: The game of NIM 35.1.2 Solutions: Ches 35.2 Solutions: Dominoes and trominoes 35.2.1 Solutions: Muddy children 35.2.2 Solutions: Colored hats 35.3 Solutions: Detecting counterfeit coin Chapter 36 Solutions: Relations and functions 36.1 Solutions: Binary relations 36.2 Solutions: Functions Chapter 37 Solutions: Linear and abstract algebra 37.1 Solutions: Linear algebra 37.2 Solutions: Groups and permutations 37.3 Solutions: Rings 37.4 Solutions: Fields 37.5 Solutions: Vector spaces Chapter 38 Solutions: Geometry 38.1 Solutions: Convexity 38.2 Solutions: Polygons 38.3 Solutions: Lines, planes, regions, and polyhedra 38.4 Solutions: Finite geometries Chapter 39 Solutions: Ramsey theory Chapter 40 Solutions: Probability and statisticsPart IV Appendices Appendix A: ZFC axiom system Appendix B: Inducing you to laugh? Appendix C: The Greek alphabetReferencesName indexSubject index