## 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 statement  true 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: Assuming is true for all for some arbitrary prove Since is arbitrary is 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)

If then there is only one term in the sum and the left hand side equals The right hand side equals Both sides are equal so is true.

Suppose the statement is true for all then is the statement that for all We need to prove  Hence is proved and the statement is true.

Example: If prove  and so is true.

Assume that is true so that for all We must prove that is true. Hence is proved and the statement is true. 