Induction

Induction is a method of proof which relies on a statement P(m) being true for a certain member of a sequence and seeks to prove the statementtrue for succeeding values with the aid of some relationship between consecutive terms of the sequence.

With the initial statement P(m), we take the induction step: Assumingis true for allfor some arbitraryprove

Sinceis arbitraryis true for all n.

It is important to realise that the statement need not be true for all terms in the sequence, only for all terms from some point in the sequence. The method is general. Some examples are useful.

Example: Prove(1)

Ifthen there is only one term in the sum and the left hand side equalsThe right hand side equalsBoth sides are equal sois true.

Suppose the statement is true for allthen

is the statement thatfor allWe need to prove

Henceis proved and the statement is true.

Example: Ifprove

andsois true.

Assume thatis true so thatfor allWe must prove thatis true.

Henceis proved and the statement is true.