Ok, there are three main steps in an induction proof
Preliminary : state the induction property
This is mostly for yourself, to clear out the view. 1st step
: the basis.
You have to check that this is true for the very first term. 2nd step
: the inductive step. Induction hypothesis
: assume that the property is true for a rank n.
that if this is verified for a rank n, it will be for the following rank, n+1.
In most of the induction exercises, this proof will require you to go back to the recursive definition of