Mathematical Induction - Example

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:

\begin{align} \frac{k(k + 1)}{2} + (k+1) & = \frac {k(k+1)+2(k+1)} 2 \\ & = \frac{k^2+k+2k+2}{2} \\ & = \frac{(k+1)(k+2)}{2} \\ & = \frac{(k+1)((k+1) + 1)}{2} \end{align}

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. Q.E.D.

Read more about this topic:  Mathematical Induction

Famous quotes containing the word example:

    “Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
    —Marcel Proust (1871–1922)