AS/A2 Pure 4 Pure 5

P6 Topic 6: Proof
Proof by induction
1 + 2 + 3 + ... + n = ½n(n+1)
Clearly this statement is true when n=1. The display below will allow you to verify that the above formula is true for values of n from 2 up to 12.

The formula is true for all values of n up to 12, and if you tried further values of n you would find it remained true. In fact, substitute any value you like into the formula and it will be true. But does this prove that the statement is true for every value of n from 1 to infinity? Unfortunately not. Mathematics requires a logical general proof of any statement. However, the above formula can be proved by using proof by induction. The following lines show such a proof step by step
1	Proposition Pn: 1 + 2 + 3 + ... + n = ½n(n+1)
2	Initial case: Prove P1 is true Substitute n = 1: LHS = 1, RHS = 1, therefore P1 is true
3	Induction hypothesis: Assume Pn is true for an arbitrary value k, ie., assume Pk is true. Therefore: 1 + 2 + 3 + ... + k = ½k(k+1)
4	Induction step: Add the next term (k+1) to both sides: 1 + 2 + 3 + ... + k + (k+1)= ½k(k+1) + (k+1) Therefore 1 + 2 + 3 + ... + k + (k+1)= ½(k+1)(k+2) But this statement is Pk+1 Therefore we have proved that, if Pk is true then Pk+1 must also be true, ie., Pk => Pk+1
5	We have shown that P1 is true and that Pk => Pk+1 Therefore Pn must be true for all n.

Summary In general a proof by induction with have three parts: initial step, induction hypothesis and induction step. It is usually the induction step which requires the most thought, particularly concerning the algebra involved. This page uses HotEqn.