
related topics 
{math, number, function} 
{theory, work, human} 
{day, year, event} 
{@card@, make, design} 
{car, race, vehicle} 
{water, park, boat} 

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers (nonnegative integers). It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one.
The method can be extended to prove statements about more general wellfounded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion.
Mathematical induction should not be misconstrued as a form of inductive reasoning, which is considered nonrigorous in mathematics (see Problem of induction for more information). In fact, mathematical induction is a form of rigorous deductive reasoning.
Contents
History
In 370 BC, Plato's Parmenides may have contained an early example of an implicit inductive proof.^{[1]} The earliest implicit traces of mathematical induction can be found in Euclid's ^{[2]} proof that the number of primes is infinite and in Bhaskara's "cyclic method".^{[3]} An opposite iterated technique, counting down rather than up, is found in the Sorites paradox, where one argued that if 1,000,000 grains of sand formed a heap, and removing one grain from a heap left it a heap, then a single grain of sand (or even no grains) forms a heap.
Full article ▸


related documents 
Groupoid 
Cauchy sequence 
Braket notation 
Addition 
Forcing (mathematics) 
Johnston diagram 
Principal components analysis 
List of trigonometric identities 
Inner product space 
Riemann zeta function 
Boolean satisfiability problem 
Nonstandard analysis 
Direct sum of modules 
Functor 
Pascal's triangle 
Integration by parts 
Cantor set 
Newton's method 
Russell's paradox 
Series (mathematics) 
Recursion 
Word problem for groups 
Wavelet 
Pythagorean theorem 
Finite field 
Inverse function 
Naive set theory 
Stone–Čech compactification 
XML 
Ruby (programming language) 
