22May/080
Proof by Induction
A proof aims to establish a fact by taking a proposition - conjecture - and applying by the mathematical axioms (given truths) establish a proved theorum. Induction is a general method for establishing a proof, and is usually used to establish that a proposition is true for any natural number.
Proof by induction works on the premise that if you can prove that the first item in a sequence is true - a case
'n' - and that a further case is true in which you can then substitute n for n+1 and the sequence still hold true, then you can demonstrate that any value in the series is true by building upon the base case.
- We know P(1) is true by substituting in 1 for n.
- Since P(1) implies P(1 + 1), we get P(2).
- Similarly, since P(2) implies P(2 + 1), we get P(3).
- With P(3), P(4) follows.
- From P(4), we get P(5).
- Etc. (Here is where the axiom of mathematical induction comes in.)
- We may conclude that P(n) holds for any natural number n.