Today’s theme is the principle of mathematical induction.

Recall that induction is a proof technique used to prove that a property *P(n)* holds for every natural number *n*, i.e. for *n* = 1, 2, 3,…

It consists of two parts:

(I) The **base case**: proving the property for *n*=1.

(II) The **induction step**: assuming that we already know the property holds for *n=k*, we prove it for *n=k+1*.

There are slight variations of this technique, the most common one being **strong induction**: for the step, we assume that the property holds for all *n* less than or equal to *k*, and then prove it for *n=k+1*.

Click here for the worksheet.

## No Comments