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.
- Base case: Prove P(1) is true
- Induction: Prove that if P(k) is true for every positive whole number k < n, then P(n) is also true.
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:
- Base case: Prove P(n) is true for certain arbitrarily large positive integer values of n
- Induction: P(n) (n > 1) implies P(n - 1).
Example: The sum of the powers of two from 2^0 up to 2^(n - 1) is (2^n) - 1
Proof:
- Base case: We begin by proving that this is true in the simplest case, that of n = 1. In this case, we are required to show that 2^0 = (2^1) - 1, which is clearly true.
- Induction: The objective is now to show that it's true in the general case. We have to show that the sum of powers of 2 from 2^0 up to 2^(n - 1) is (2^n) - 1, but in doing so we're allowed to assume that it's true in the simpler case of k where k is less than n. We set k = n - 1, so
- 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