Proof by Induction

• Property P(n) holds for every natural number n(0….N) or every between (x∈N…N)

The method of induction requires two cases to be proved.

• The base case (or, sometimes, the basis), proves that the property holds for the number 0. (This is easy to compute and check for the number n).
• The second case, called the induction step, proves that if the property holds for one natural number n, then it holds for the next natural number n+1.(This is a formal way of assigning n to be n+1, and arriving to the (base case +1) as a mathematical property).