Proof By Induction

Proof By Induction is a technique whereby we show that the desired fact is true for some initial set of circumstances, and then show that whenever it's true for simpler things it's also true for more complicated ones. Many people find it confusing because experienced practitioners appear to be assuming the very thing they're supposed to be proving, even when what they're doing is perfectly valid.

The validity of the method can be shown to be equivalent to the statement:
Every set of positive integers has a least element.

Strictly speaking, the first step ("Base case") can be omitted, because if the second step works then setting n=1 shows that P(1) is true, since there are no whole numbers less than 1 and hence the antecedent of the induction step is vacuously satisfied. (See http://en.wikipedia.org/wiki/Transfinite_induction.) But, if in doubt, check P(1) just to be sure! -- JasonGrossman

Alternative:


Example: The sum of the powers of two from 2^0 up to 2^(n - 1) is (2^n) - 1

Proof:

2^0 + 2^1 + ... + 2^(n-2) + 2^(n-1) = 2^0 + 2^1 + ... + 2^(k - 1) + 2^(n - 1)

Now we know that 2^0 + 2^1 + ... + 2^(k - 1) = (2^k) - 1, so

2^0 + 2^1 + ... + 2^(n - 2) + 2^(n - 1) = (2^k) - 1 + 2^(n - 1) = (2^(n - 1)) - 1 + 2^(n - 1) = 2 x 2^(n - 1) -1 = (2^n) - 1

and we're done.

As an alternative to the above, one could prove that P(n) is true for specific arbitrarily large values of n, and then prove that the truth of P(n) (where n > 1) implies that of P(n - 1).


Mathematical induction is sometimes confused with the more general term induction, which is not a valid proof in the general case. Induction (contrasted with deduction) is the extension of observations of a subset to conclusions about the entire set. Example: All the swans I've seen so far are white, therefore all swans are white. This concept is different from mathematical induction.


CategoryMath CatergoryProof?


EditText of this page (last edited November 23, 2014) or FindPage with title or text search