A proof by induction is just like an ordinary proof
in which every step must be justified. However it employs a neat trick
which allows you to prove a statement about an arbitrary number n by
first proving it is true when n is 1 and then assuming it is true for
n=k and showing it is true for n=k+1.
OR 