E-Book, Englisch, 921 Seiten
Gunderson Handbook of Mathematical Induction
1. Auflage 2014
ISBN: 978-1-4200-9365-0
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
Theory and Applications
E-Book, Englisch, 921 Seiten
Reihe: Discrete Mathematics and Its Applications
ISBN: 978-1-4200-9365-0
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
Handbook 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.
Zielgruppe
Professionals and undergraduate and graduate students in mathematics and computer science; high school students in mathematics.
Autoren/Hrsg.
Fachgebiete
Weitere Infos & Material
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 - 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
Schröder 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
