Mathematical induction

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers, or otherwise is true of all members of an infinite sequence. A somewhat more general form of argument used in mathematical logic and computer science shows that expressions that can be evaluated are equivalent; this is known as structural induction.

Related Topics:
Mathematical proof - Natural number - Mathematical logic - Computer science - Structural induction

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The first known proof by mathematical induction appears in Francesco Maurolico's Arithmeticorum libri fuo (1575). Maurolico proved that the sum of the first n odd integers is n^2.

Related Topics:
Francesco Maurolico's - 1575

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The simplest and most common form of mathematical induction proves that a statement holds for all natural numbers n and consists of two steps:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• The basis: showing that the statement holds when n = 0.
• The inductive step: showing that if the statement holds for n = m, then the same statement also holds for n = m + 1. (The proposition following the word "if" is called the induction hypothesis. Do not call step 2 as a whole the induction hypothesis.)

This method works by first proving the statement is true for a starting value, and then proving that the process used to go from one value to the next is valid. If these are both proven, then any value can be obtained by performing the process repeatedly. It may be helpful to think of the domino effect; if you have a long row of dominos standing on end and you can be sure that:

Related Topics:
Process - Valid - Domino effect

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• The first domino will fall.
• Whenever a domino falls, its next neighbor will also fall.

then you can conclude that all dominos will fall.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

 
Mathematical induction: Example ►