Induction is a method of proof that is very useful in mathematics.
Here is
a simple proof by induction:
Statement:
A polygon has as many sides as it has angles.
Proof:
The polygon with the fewest number of sides and angles is a
triangle, which has three sides and three angles, so the
statement is true for triangles.
To make a 4-angled polygon from a triangle, an angle
must be added to the triangle, somewhere
between any two of the existing angles. A point can be
marked outside the boundary of the triangle to indicate
where the new angle will be placed. The line connecting
the points where these two angles are formed is removed,
and two new lines are added, connecting, in order, a point
from the existing triangle, the new point, and the other
point from the existing triangle. The net gain is one angle
and one line.
Step (2) didn't depend on the polygon you began with being a
triangle. It would actually work for any size polygon.
A proof by induction has two parts:
A demonstration of how the statement to be proved is true for the
smallest possible case (or cases), as in (1) above, and
A demonstration of how, if the statement is true for some number
n ,
(in the above example, n is equal to the number of sides and the
number of angles), it is also true for n+1 . In (2), above
n=3 ,
and the statement is proved for n+1=4 . This is generalized in
(3).
Many theorems in Graph Theory have been proved by induction. The
demonstration that uses string to show that maps drawn without lifting your
pencil or retracing lines relies on induction also. (See Making a 2-Colorable Map .)
