next up previous
Up: Types of Proof Previous: Uniqueness Proofs

Mathematical Induction

A type of proof that deserves special attention is mathematical induction. Some of the statements of theorems which can be proved using mathematical induction involve an integer variable. An example of such a theorem is

displaymath399

Let p(n) denote the statement involving the integer variable n. The Principle of Mathematical Induction states

If p(1) is true and, for each integer tex2html_wrap_inline407 , p(k+1) is true whenever p(k) is true then p(n) is true for all tex2html_wrap_inline415 .

This principle is often compared to an infinite line of dominos. The inductive part of the principle (for each integer tex2html_wrap_inline415 , p(n+1) is true whenever p(n) is true) would say that the domino in the (n+1)st position falls whenever the nth domino falls. However, at that stage we still don't know if the line of dominos has fallen or is still upright. The base step in the principle (If p(1) is true) is analogous to saying the first domino has fallen. We would now realize that the complete line of dominos will fall. It is important to show that the base step and the inductive step in the principle are satisfied.

There are several variations in this principle. The first covers statements that are true for all integers beyond a certain value (such as tex2html_wrap_inline429 which is true for all tex2html_wrap_inline431 ).

If tex2html_wrap_inline433 is true and, for each integer tex2html_wrap_inline435 , p(k+1) is true whenever p(k) is true then p(n) is true for all tex2html_wrap_inline443 .

There is also a stronger form of mathematical induction which states the following:

If p(1) is true and, for each integer tex2html_wrap_inline407 the statements tex2html_wrap_inline449 imply the statement p(k+1) then p(n) is true for all tex2html_wrap_inline415 .

This principle of strong mathematical induction is used for example to prove the result that every positive integer is a prime number, a power of a prime or a product of primes. As with the principle of mathematical induction, there is a variation on this to cover those statements that are true for all integers beyond a certain value tex2html_wrap_inline457 .


next up previous
Up: Types of Proof Previous: Uniqueness Proofs

Peter Williams
Sun Sep 15 22:27:27 PDT 1996