One of the Peano axioms for the natural numbers says : If a set contains zero and the successor of every number is in the set, then the set contains the natural numbers. This translates, after some work, to: If a set contains 1, and for any member n of the set contains n+1, then it contains all the natural numbers. This is used for making proofs by induction by proving 1. that the set of natural numbers for which the theorem is true contains 1. 2. Then, assuming that the set contains n you can prove the set of integers for which the theorem is true contains n+1, then the set of integers for which the theorem is true contains all the natural numbers. That is, that the theorem is true for all the natural numbers.
The idea is that if you can make a proof for 1, and then show that you can take one step forward, by the proof that if the theorem is true for n it is true for n+1, then starting at 1, which you show separately, the machine that you built to step from n to n+1 allows you to say the theorem is true for 2. That the theorem is true for 2, and the use of the machine to walk one step, you show it is true for 3. Keep going. ..............................................................................................
Example. The sum of the first n natural numbers is (n)(n+1)/2. The sum of the first 1 natural number is, of course, 1. Assume that the sum of the first n natural numbers is n(n+1)/2. The sum of the first n+1 natural numbers is then n(n+1)/2 +n+1=(n+1)(n/2+1)=(n+1)(n+2)/2 which is the same formula applied to
the first n+1 natural numbers. QED . ................................................................................................................
Example: The sum of the squares of the first natural numbers is n(n+1)(2n+1)/6 Proof: For n=1 this formula is 1(2)(3)/6=1 Assume the formula is true for n, and consider the first n+1 squares as (n)(n+1)(2n+1)/6 + (n+1)^2
=(n+1)[(n)(2n+1)+6(n+1)]/6=(n+1)(2n^2+7n+6)/6 =(n+1)(n+2)(2n+3)/6 which is the prior formula with n+1 in place of n.QED
