The wikipedia says about mathematical induction:
Mathematical induction is a method of
mathematical proof typically used to establish that a given statement is true for all
natural numbers (positive
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.
Example
Mathematical induction can be used to prove that the following statement, which we will call P(n), holds for all natural numbers n.
P(
n) gives a formula for the sum of the
natural numbers less than or equal to number
n. The proof that
P(
n) is true for each natural number
n proceeds as follows.
Basis: Show that the statement holds for n = 0.
P(0) amounts to the statement:
In the left-hand side of the equation, the only term is 0, and so the left-hand side is simply equal to 0.
In the right-hand side of the equation, 0·(0 + 1)/2 = 0.
The two sides are equal, so the statement is true for n = 0. Thus it has been shown that P(0) holds.
Inductive step: Show that if P(k) holds, then also P(k + 1) holds. This can be done as follows.
Assume P(k) holds (for some unspecified value of k). It must then be shown that P(k + 1) holds, that is:
Using the induction hypothesis that P(k) holds, the left-hand side can be rewritten to:
Algebraically:
thereby showing that indeed P(k + 1) holds.
Since both the basis and the inductive step have been proved, it has now been proved by mathematical induction that P(n) holds for all natural n
here is another example by me: