next up previous
Next: Some other examples Up: Introduction Previous: Example (definition to follow)

The formal definition

If $k$ is an integer, and $P$ is some property of integers (that is, for every integer $n$, $P(n)$ is a statement - meaning something that is either true or false - for instance, it could be the equation mentioned above). Then, if
``base case'':
$P(k)$ is true and
``induction step'':
whenever $P(n)$ is true, then $P(n+1)$ is also true.
then $P(n)$ is true for all integers $n \geq k$.

The antecedent of the induction step, (the temporary assumption that $P(n)$ is true), is also called the induction hypothesis.

I like to think of induction as sort of like climbing a ladder. The base case is the bottom rung of the ladder and the induction step shows you how to climb from one rung to the next. If you know how to get to the bottom rung, and you know how to climb from one rung to the next, you can climb to every rung above the bottom one! Some people prefer a domino metaphor.

Zvezdelina Stankova-Frenkel 2001-11-18